1 Use the Euclidean Algorithm to:
(a) Use the Euclidean Algorithm to show that (153−1 mod 909) does not exist.
(b) Use the Euclidean Algorithm to show that (153−1 mod 908) does exist.
(c) Find (153−1 mod 908) using your previous Euclidean work. You must find the modular inverse using the Extended Euclidean algorithm. When you are done then use an
appropriate modular multiplication to confirm that your answer is correct.
2 Consider the integer n = 527.
(a) Show it is not prime by using the primality testing method from the last homework.
(b) Use Fermat’s Primality Test to show that n = 527 is not prime. You can use Wolframalpha.com or similar software to do the modular exponentiation for you.
(c) In (2a) you found the factorization of 527. Use Fermat’s Little Theorem to find a value
of x such that
12x ≡ 1 mod 527
(d) Use fast modular exponentiation to confirm that this is true.
(e) Use Fermat’s Little Theorem, as stated above, to find
122402 mod 527
(f) Why can’t Fermat’s Little Theorem be used to find the following?
342402 mod 527
3 Use Fermat’s Primality Test to show that 1063 + 19 is not prime.