Question. Find the greatest common divisor d of 159 and 51, and find integers x and y solving the equation 159 x + 51 y = d .
Answer. d = 3. The extended Euclidean algorithm gives x = 9 and y = -28. (There are other solutions for x and y; these are not unique.)
plz show step and help plz
159/51=3(51)+6
51/6=8(6)+3
6/3=2(3)+0
answer: d=3
on the second,
It is messy to type out. Look at the sample on this link:
http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html
To find the greatest common divisor (GCD) of 159 and 51, as well as the integers x and y that solve the equation 159x + 51y = d, we can use the extended Euclidean algorithm. This algorithm allows us to find the GCD and the coefficients x and y that satisfy the equation.
Step 1: Start with the two given numbers, 159 and 51.
Step 2: Divide the larger number by the smaller number and find the remainder.
159 ÷ 51 = 3 remainder 6
Step 3: Replace the larger number with the smaller number and the smaller number with the remainder.
51 ÷ 6 = 8 remainder 3
Step 4: Repeat step 3 until the remainder is 0.
6 ÷ 3 = 2 remainder 0
Step 5: The GCD is the last non-zero remainder, which is 3. So, d = 3.
Step 6: Now, we can work backward to find the coefficients x and y.
Working backward from step 4, we can write each remainder as a linear combination of the two original numbers:
3 = 51 - 8 * 6
6 = 159 - 3 * 51
Step 7: Substitute these expressions into their previous equations:
3 = 51 - 8 * (159 - 3 * 51) => 3 = 51 - 8 * 159 + 24 * 51
3 = 25 * 51 - 8 * 159
From the final equation, we can see that x = -8 and y = 25.
Therefore, the GCD is 3, and one solution for x and y that satisfy the equation is x = -8 and y = 25.
Note: The values of x and y are not unique. You might find different values of x and y that also satisfy the equation.