What is the least positive integer?
1 answer:
You might be interested in
Use the Euclidean algorithm to express 1 as a linear combination of and
.
a. because
77 = 1*52 + 25
52 = 2*25 + 2
25 = 12*2 + 1
so we can write
1 = 25 - 12*2 = 25*25 - 12*52 = (77 - 52)(77 - 52) - 12*52 = 77^2 - 2*52*77 + 52^2 - 12*52
Taken modulo 77 leaves us with
b. First, , so really we're looking for the inverse of 25 mod 52. We've basically done the work in part (a) already:
1 = 25*25 - 12*52
Taken modulo 52, we're left with
c. The EA gives
71 = 1*53 + 18
53 = 2*18 + 17
18 = 1*17 + 1
so we get
1 = 18 - 17 = 3*18 - 53 = 3*71 - 4*53
so that taken module 71, we find
d. Same process as with (b). First we have , and we've already shown that
1 = 3*18 - 53
which means, taken modulo 53, that