Question

Show that he gcd of 63 and 40 is 1 and find all integer solutions: 63s + 40t = 1. Use the Euclidean algorithm to find the gcd. Then back solve to find s and t.

To get full credit, use the format shown in the post below titled Bezout's Theorem. (See the example where we find the gcd of 18 and 5.)

Bézout's theorem says

"If  d is the gcd of m and n then we can find integers s and t such that ms + nt = d."

To find s and t we first compute d using the Euclidean algorithm. Then we can backsolve to express d in terms of m and n.

Example: Find all integer solutions to 18s + 5t = 1. (So 18 is m, 5 in n and 1 is d in Bézout's Theorem.)

18 =3(5) + 3

5 = 1(3) + 2

3 = 1(2) + 1.

2 = 2(1) + 0.

Since 1 is the last nonzero remainder, it's the gcd of 18 and 5.

Now we can back solve to find a linear combination of 18 and 5 that equals 1:

1 = 3 - 2

= 3 - (5 - 3)

= -5 + 2(3)

= -5 + 2(18 - 3(5))

= 2(18) - 7(5).

In this example 18 and 5 are m and n. So s = 2 and t = -7.

Call the initial two solutions s₀ and t₀.

To get all solutions use s = s₀ + (n/d)k and t = t₀ - (m/d)k.

In the example above we get s = 2 + 5k and t = -7 - 18k.

For example, taking k = -1 gives s = -3 and t = 11. We can check that these values work: -3(18) + 11(5) = -54 + 55 = 1.

Or taking k = 2, gives s = 12 and t = -43. Again we can check that the values work: 12(18) - 43(5) = 216 - 215 = 1.

Answer 1

Show that he gcd of 63 and 40 is 1 and find all integer solutions: 63s + 40t = 1.

Comparing the given equation with ms + nt = d , we get  63 is m, 40 is n and 1 is d (Bézout's Theorem)

63 =1(40) + 23

40 = 1(23) + 17

23 = 1(17) + 6

17 = 2(6) + 5

6 = 1(5) + 1

5 = 5(1) + 0

Since 1 is the last nonzero remainder, it's the gcd of 63 and 40.

Now we can back solve to find a linear combination of 63 and 40 that equals 1:

1 = 6 - 5

= 6 - [ 17 - 2(6) ]

= -17 + 3 (6)

= -17 + 3 [ 23 - 17 ]

= - 4(17) + 3 (23)

= -4 [ 40-23 ] + 3 (23)

= -4(40) +7(23)

= -4(40) +7[ 63 - 40 ]

= -11(40) + 7(63)

In this example 63 and 40 are m and n. So s = 7 and t = -11.

Call the initial two solutions s₀ and t₀.

To get all solutions use s = s₀ + (n/d)k and t = t₀ - (m/d)k.

In the example above we get s = 7 + 40k and t = -11 - 63k.

For example, taking k = 1 gives s = 47 and t = -74. We can check that these values work: 47(63) - 74(40) = 2961 - 2960 = 1.

Or taking k = 3, gives s = 127 and t = -200. Again we can check that the values work: 127(63) - 200(40) = 8001 - 8000 = 1.