Ask Question
29 May, 13:45

Using the Extended Euclidean Algorithm, find integers x and y such that 26x + 9y = 1.

+4
Answers (1)
  1. 29 May, 15:47
    0
    The solution is: x=-1 and y=3.

    Step-by-step explanation:

    Let's find the solution, but first let's remember the following:

    A / B = C + R where:

    A=dividend, B=divisor, C=quotient, and R=remainder. This can be express as follows:

    A = (C * B) + R, which is the structure we are going to use next.

    Using the Euclidian Algorithm we need to find the highst common factor (HCF) between the coefficients from your equation, this means:

    The original equation: 26x+9y=1 is in the form Ax+By=C, so A=26, B=9 and C=1.

    We need to find the HCF of 'A' and 'B'. Using the Euclidan Algorithm (EA), so we have:

    A = (C * B) + R, using our values:

    26 = (2 * 9) + 8, look that the divisor (B) is 9 and the remainder (R) is 8.

    Now using the (EA) we divide the divisor (B=9) by the obtained remainder (R=8). And we do the same for each obtained result until the las remainder (R) is equal to 0, like this:

    A = (C * B) + R

    9 = (8 * 1) + 1

    using the divisor (B=8) and the remainder (R=1) we obtain:

    A = (C * B) + R

    8 = (1 * 8) + 0, look that the remainder is now 0, so in summary we can use the method as follows:

    26 = (2 * 9) + 8

    9 = (8 * 1) + 1

    8 = (1 * 8) + 0; and this equations are the ones we are going to use in order to find a solution.

    Next step is to use the equation before R=0, so:

    9 = (8 * 1) + 1, which is:

    9 - (8 * 1) = 1; but if you consider the first obtained equation: 26 = (2 * 9) + 8, we can write:

    26 - (2 * 9) = 8, and we can use this expression in the previous one, so:

    9 - (8 * 1) = 1, is:

    9 - ((26 - (2 * 9)) * 1) = 1, simplifying:

    9 - 26 + (2*9) = 1

    9 - 26 + (9 + 9) = 1

    -26 + (9 + 9 + 9) = 1

    -26 + (3 * 9) = 1

    26 * (-1) + 9 * (3) = 1; if you compare the last expression with the original equation, which is: 26x+9y=1, you can see the similarity, where x=-1 and y=3.

    So, the solution is: x=-1 and y=3.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Using the Extended Euclidean Algorithm, find integers x and y such that 26x + 9y = 1. ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers