Number theory section 2

• Fermat's Little Theorem


  A theorem in number theory that describes the behavior of powers modulo some fixed m
• Proof of Fermat's Little Theorem

  1. Check that if a = b, then gcd(a, m) = 1 implies gcd(b, m) = 1

  2. Recall that multiplication in Z/mZ is associative, with 1 as the multiplicative identity

  3. Show that (Z/mZ)* is closed under multiplication and is a group under multiplication
• The quotient of Z/mZ is actually a ring, with a sum and product satisfying certain properties
• Powers modulo m


  Behavior of ak modulo m for k = 1, 2, ...
• Digits


  • 10n ≡ 1 (mod 9), so every number is congruent to the sum of its digits modulo 9
  • 3456 ≡ 18 ≡ 9 ≡ 0 (mod 9), proving the classical test that 9 divides a number if and only if it divides the sum of its digits
• Decimal expansion of 1/7


  • Start with r0 = 1, the numerator of 1/7

  Inductively, divide 10rk by 7 and find quotient qk+1, remainder rk+1
• Fermat's Little Theorem


  Let p be a prime and a ∈ Z such that p ∤ a. Then ap−1 ≡ 1 (mod p).
• Proof of Fermat's Little Theorem (Group theoretic)

  1. By Corollary 2.1.11, the congruence classes of 1, ..., p-1 form a group under multiplication

  2. Its size is p-1 by Exercise 2.1.10

  3. By Lagrange's theorem, ap-1 ≡ 1 (mod p) for every element of the group
• Proof of Fermat's Little Theorem (Combinatorial)

  1. The numbers a, 2a, 3a, ..., (p-1)a are not divisible by p, so they are not congruent to 0 modulo p

  2. If ra ≡ sa (mod p), then r ≡ s (mod p) by Lemma 2.1.8, since gcd(a, p) = 1

  3. The numbers a, 2a, 3a, ..., (p-1)a are just some permutation of 1, 2, ..., (p-1) modulo p

  4. ap-1(p-1)! ≡ (p-1)! (mod p)

  5. (p-1)! is not divisible by p, so ap-1 ≡ 1 (mod p)
• Fermat did not prove this theorem either
• Fermat's Little Theorem


  If p is prime and a ∈ Z, then ap ≡ a (mod p)
• Proof of Fermat's Little Theorem

  1. If p | a, then a ≡ 0 and ap ≡ 0

  2. Otherwise p ∤ a, thus ap−1 ≡ 1, hence ap ≡ a just by multiplying both sides by a
• The length of the period is the least k such that 10k ≡ 1 (mod p) (provided p ∤ 10)
• 10p−1 ≡ 1 (mod p) (provided p ∤ 10)
• Proof of k | p - 1

  1. Divide p - 1 by k, that is write p - 1 = qk + r where 0 ≤ r < k

  2. Then 1 ≡ 10p−1 = (10k)q10r ≡ 10r (mod p)

  3. By minimality of k, we must have r = 0, that is k | p - 1
• If 2r - 1 is prime, then r is prime
• The condition "if 2r - 1 is prime, then r is prime" is not sufficient
• Mersenne prime


  2r - 1 is prime
• Mersenne primes


  • 22 - 1 = 3
  • 23 - 1 = 7
  • 25 - 1 = 31
  • 27 - 1 = 127
  • 211 - 1 is divisible by 23
• The largest known prime number (as of January 2024) is 2282,589,933 - 1, a Mersenne prime
• Proof of Proposition 2.2.8


  1. Suppose that p | 2r - 1 for some prime p

  2. 2r ≡ 1 (mod p)

  3. 2p−1 ≡ 1 (mod p) by Fermat's Little Theorem

  4. If r ∤ p - 1, then (p - 1)b ≡ 1 (mod r) for some b ∈ Z

  5. 1 = 1b ≡ 2(p−1)b = 21+rk = 2 · (2k)r ≡ 2 (mod p), a contradiction

  6. Therefore, r | p - 1, and p = 2kr + 1 for some k ∈ Z
• 223 - 1
• Wilson's Theorem


  If p is prime, then (p - 1)! ≡ -1 (mod p)
• Proof of Wilson's Theorem

  1. For every a ∈ {1, ..., p - 1}, there is a unique b ∈ {1, ..., p - 1} such that ab ≡ 1 (mod p)

  2. Whenever a ≠ b, both a and b appear in (p - 1)!, and we can cross them off

  3. (p - 1)! = Π(a=1 to p-1) a ≡ Π(a=1 to p-1, a^2≡1) a

  4. a^2 ≡ 1 means p | (a + 1)(a - 1), so a ≡ ±1

  5. (p - 1)! = Π(a=1 to p-1, a≡±1) a = 1 * (p - 1) = p - 1
• Wilson only stated Wilson's Theorem as a problem in 1770, but did not prove it
• If p = 2, then x = 1 is a solution, so let us focus on p > 2, in particular p odd and p − 1 even.
• Suppose there is a solution a. By Fermat's Little Theorem, 1 ≡ ap−1 = (a2)p−1/2 ≡ (−1)p−1/2. Since 1 ̸≡ −1 (mod p), the number (p−1)/2 must be divisible by 2, thus 4 | (p − 1).
• Conversely, suppose that p ≡ 1 (mod 4). We have (p − 1)! = 1 · 2 · · · (p − 1)/2 · (p + 1)/2 · · · (p − 2) · (p − 1) ≡ 1 · 2 · · · (p − 1)/2 · (−(p − 1)/2) · · · (−1) · (−1) = ((p − 1)/2)! · (−1)(p−1)/2 · ((p − 1)/2)! = ((p − 1)/2)! 2 · (−1)(p−1)/2.
• By Wilson's Theorem, the left hand side is congruent to −1, while (p−1)/2 is even by assumption, thus (−1)(p−1)/2 ≡ 1. It follows that x = ((p − 1)/2)! satisfies x2 ≡ −1 (mod p).
• Chinese Remainder Theorem


  If m1, . . . , mk are pairwise coprime and a1, . . . , ak ∈ Z, then the simultaneous congruences x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ ak (mod mk) have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m1 · · · mk.
• Chinese Remainder Theorem


  A theorem that describes the structure of the solutions of a system of linear congruences with respect to different moduli
• The solution is unique up to congruence modulo m1 · · · mk
• Proof of Chinese Remainder Theorem (k=2)

  1. Take x of the form x = m1y1 + m2y2

  2. x ≡ m1y1 (mod m2) and x ≡ m2y2 (mod m1)

  3. Use Lemma 2.1.8 to find b, c such that m1b ≡ 1 (mod m2) and m2c ≡ 1 (mod m1)

  4. Take y1 = ba2 and y2 = ca1

  5. x = m1ba2 + m2ca1 ≡ (m1b)a2 ≡ a2 (mod m2)
• Proof of Chinese Remainder Theorem (k>2)


  1. Conclude by induction

  2. Set x = (m2 · · · mk)b1a1 + (m1m3 · · · mk)b2a2 + · · · + (m1 · · · mk−1)bkak where (m1 · · · c

  mi · · · mk)bi ≡ 1 (mod mi)
• If x and y are two solutions, then x ≡ y (mod m1 · · · mk)
• Euler's totient function


  For n ≥ 1, the totient of n, written ϕ(n), is the number of integers k such that 1 ≤ k ≤ n which are coprime with n (that is, gcd(k, n) = 1)
• Euler's totient function


  • ϕ(10) = 4: the set of numbers between 1 and 10 which are coprime with 10 is {1, 3, 7, 9}
  • ϕ(1) = 1
  • ϕ(p) = p - 1 if and only if p is prime
• The number ϕ(n) is exactly the size of the group (Z/nZ)×
• If a is coprime with n, then aϕ(n) ≡ 1 (mod n)
• Proof of Lemma 3.1.4

  1. Consider the mapping F: {0, 1, ..., mn - 1} → {0, 1, ..., m - 1} × {0, 1, ..., n - 1} defined by F(k) = (a, b), where a is the remainder of k modulo m and b the remainder of k modulo n

  2. By the Chinese Remainder Theorem, the map F is both onto and injective

  3. The map Z/mnZ → Z/mZ × Z/nZ defined as above is a bijection