An Example of GCD, and Extended Euclidean Algorithm In Finding the Bezout Coefficients
Vložit
- čas přidán 10. 09. 2024
- gcd (5083, 345) = 23
Find x, y such that 5083x+345y = gcd(5083,345)
check out an earlier video on the subject:
GCD, Euclidean Algorithm and Bezout Coefficients
• GCD, Euclidean Algorit...
Thank you
Thank you so much
What is q
Still didn't get it 😢
it is not easy to explain the details with Shorts. I will consider a longer video on the Extended Euclidean algorithm. For now, please refer this wiki page en.wikipedia.org/wiki/Extended_Euclidean_algorithm
*Euclidean Algorithm (For GCD):* 🌟 🤯
Another efficient way to find the greatest common divisor (and thus derive common factors) is using the Euclidean algorithm:
Step 1:
Divide the larger number by the smaller one and take note of the *remainder.*
Step 2:
Replace the larger number with the smaller one and repeat this process until you reach a remainder of zero.
Step 3:
The last non-zero remainder will be your GCD.
*For example:*
For numbers 12 and 18:
“18 ÷ 12 = 1 remainder *6* ”
{12 * 1 = 12 (so this is why the 1 is there. 👆)
and
12 + 6 = 18 (so this is why the 6 is there. 👆)}
[If using calculator *Do 18 divided by 12 so 18/12 is 1.5,*
*next round the number down to have NO DECIMALS so 1.5 becomes 1,*
*then multiply that whole number to 12 so 1 times 12 is 12,*
*lastly subtract 18 by 12 so 18 - 12 is 6 the answer.* ]
“12 ÷ 6 = 2 remainder 0”
Thus, GCD (12,18) = *6* , confirming our earlier findings. ✔️ 👍
*”Steps to Use the Euclidean Algorithm with a Calculator”*
*Step 1: Divide the Larger Number by the Smaller Number*
• Input the larger number (18) divided by the smaller number (12) into your calculator.
• Record the integer part of the quotient.
For example, 18 ÷ 12 = 1.5, so take 1.
*Step 2: Multiply and Subtract*
• Multiply the integer part from Step 1 by the smaller number: 1 × 12 = 12.
• Subtract this result from the larger number to find the remainder: 18 − 12 = 6.
*Step 3: Replace and Repeat*
• Now replace the larger number with the smaller number (12) and use the remainder (6) as your new smaller number.
• Repeat Step 1: Calculate 12 ÷ 6 = 2. The integer part is 2.
*Step 4: Final Calculation*
• Multiply again: 2 × 6 = 12.
• Subtract to find a new remainder: 12 − 12 = 0.
*Conclusion*
• When you reach a remainder of zero, the last non-zero remainder is your GCD. In this case, GCD(12,18) = *6*
I can't understand
dummy
🤯