1. Find the multiplicative inverse of n modulo m if

    1. n = 2 and m = 19

      2 × 10 = 20, and 20 ≡ 1 (mod 19).

      So the inverse of 2 (mod 19) is 10.

    2. n = 34 and m = 89

      55

    3. n = 144 and m = 233

      89

    4. n = 200 and m = 1001

      996

      200 × 5 = 1000 = 1001 − 1. So 200 × 5 ≡ −1 (mod 1001)

      Negating both sides gives 200 × (−5) ≡ 1 (mod 1001).

      So the inverse of 200 (mod 1001) is −5. But −5 ≡ 1001 − 5 ≡ 996 (mod 1001).

  2. Solve the following congruences for x using the inverses found in the preceding question.

    1. 34x ≡ 77 (mod 89)

      55 × 34x ≡ 55 × 77 (mod 89).

      Since 55 × 34 ≡ 1 (mod 89), x ≡ 55 × 77 ≡ 4235 ≡ 52 (mod 89).

    2. 144x ≡ 4 (mod 233)

      89 × 144x ≡ 89 × 4 (mod 233). Since 89 × 144 ≡ 1 (mod 233), x ≡ 89 × 4 ≡ 356 ≡ 123 (mod 233)

    3. 200x ≡ 13 (mod 1001)

      (− 5) × 200x ≡ (−5) × 13 (mod 1001).

      Since (− 5) × 200 ≡ 1 (mod 1001), x ≡ (−5) × 13 (mod 1001) ≡ −65 ≡ 1001 − 65 ≡ 936 (mod 1001).

  3. Use Fermat's Little Theorem to compute 3302 mod 5. (Hint. What is 34 mod 5?)

    By Fermat's Little Theorem, 34 ≡ 1 (mod 5). 3302 ≡ 32 × (34)75 ≡ 32 ≡ 4 (mod 5).

  4. Prove that 7 is a divisor of n7 − n for every positive integer n. (Hint. Use Fermat's Little Theorem.)

    Proof. There are two cases.

    1. Suppose n is divisible by 7. Then n7 − n ≡ n(n6 − n), which is clearly divisible by 7.

    2. Suppose that n is relatively prime to 7 (the only other possibility, since 7 is prime).

      Choose a value m where 0 ≤ m < 7 and m ≡ n (mod 7). By Fermat's Little Theorem, m6 ≡ 1 (mod 7).

      So n7 − n ≡ n(n6 − 1) ≡ m(m6 − 1) ≡ m(1 − 1) ≡ 0 (mod 7). That is, n7 − n is divisible by 7.