(c) hence, or otherwise, find solutions of the following equations or explain why a solution does not exist. (i) a = 273−1 mod 3019 (ii) 273b ≡ 15 (mod 3019) (iii) 16c ≡ 1 (mod 273) (iv) d ≡ 1 (mod 273) and d ≡ 15 (mod 3019)

will have a solution if and only if (coprime), which is true since 3019 is prime. So we can apply Euclid's algorithm:










- - -



We can start off by finding the inverse of 15 via Euclid's algorithm. Let be an integer such that



Then











Now, multiplying both sides of the equivalence by 2214, we have





Using Euclid's algorithm, you'd end up with .

- - -



will have a solution so long as , which is true. Use Euclid's algorithm and you should get .

- - -



If , then surely , but the second equation is not satisfied. Similarly, if , we do get , but then the first condition is not met.

So suppose we take



Now . To get a remainder of 1, we can use the result from part (iii) and multiply the first term by 256.



Now . From part (i), we have , so we can multiply the second term by 188 to get the right remainder.

So finally,



The smallest positive integer that satisfies this equation would then be