Taken from a set of exam practice problems with no solution

1. Recall the following denition.

Denition. Let d be a positive integer. The relation congruence modulo d on the set Z is dened by: for all a,b Z, a b mod d if and only if d|(ab).

(a) Use the Euclidean Algorithm to compute gcd(271,99) and use that to nd integers x and y so that gcd(271,99) = 271x + 99y.

(b) Use part (a) to nd an inverse r of 99 modulo 271 so that 0 < r < 271; that is, nd an integer r so that 0 < r < 271 and 99r 1 mod 271. Make sure to verify that r is an inverse of 99 modulo 271 by using the denition of congruence modulo 271.

(c) Use part (b) to nd an integer s so that 99s 113 mod 271 and 0 < s < 271. Make sure to verify that s satises the condition that 99s 113 mod 271 by using the denition of congruence modulo 271.