• ↑
  • MAT102 Lecture 18B

Fermat's Little Theorem

• mcs.utm.utoronto.ca/~tholden/SET.pdf
• If $p$ is prime and $p\nmid a$ then $a^{p-1}=1(\mathrm{mod}p)$
• L2
  • $gcd(p,a)=1$
  • Coprime
  • Then that implies that $ma\equiv na(\mathrm{mod}p)$
  • Linearity of mod means $m\equiv n(\mathrm{mod}p)$
• L3
  • See that $S$ and ${\mathbb{Z}}_p$ have the same Cardinality.
• L4
  • If we do $(a)(2a)\dots ((p-1)(a))\equiv (1)(2)\dots (p-1)(\mathrm{mod}p)$
  • Then we can factor out $a^{p-1}$ and get the factorial of $(p-1)$
• Example to prove line 1:
  • Try this for some $a,p$
    • $a=3$
    • $p=5$
    • ${\mathbb{Z}}_5=\{[0],[1],[2],[3],[4]\}$
    • If we multiply these by $3$ (or $a$) we get the same numbers, but maybe in a different order
    • $S=\{0\cdot 3,1\cdot 3,2\cdot 3,3\cdot 3,4\cdot 3\}$
    • $S=\{0,3,1,4,2\}$
  • Consider $p$ not prime
    • Then one of the elements won't have a multiplicative inverse
    • We could get two of the same elements?
    • $p=6$
    • ${\mathbb{Z}}_6=\{0,1,2,3,4,5\}$
    • $a=3$
    • $S=\{0\cdot 3,1\cdot 3,2\cdot 3,3\cdot 3,4\cdot 3,5\cdot 3\}$
    • $S=\{0,3,0,3,0,3\}=\{0,3\}$
    • When you are not prime, you don't get back the same numbers
    • See that $a=5$ works but not any other.
    • This is because $gcd(5,6)=1$, they're coprime.
    • If $p$ is prime, then it's coprime to basically everything. If we say $p\nmid a$, then it's coprime to everything.
• Line 2:
  • This is the proof for the claim in line 1.
  • Indeed the statement $ma\equiv na(\mathrm{mod}p)⟹m\equiv n(\mathrm{mod}p)$ does the trick to prove 'no two elements from $S$ lie in the same equivalence class$(\mathrm{mod}p)$'
  • $m\equiv n$ must've been the same number
  • Same like an injectivity proof
  • This is an injective function basically.
  • Define $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$
  • Where $[x]\mapsto [ax]$
  • This is an injective map
  • Because they're the same cardinality, it's injective $⟹$it's bijective.

  ---

  • Prove $gcd(p,a)=1$ if $p\nmid a$
  • Since $p$ is prime, the only two divisors are $1$ and $p$
  • Then either $gcd(a,p)=1$ or $p$
  • For the sake of contradiction suppose it's $p$
    • $gcd(a,p)=p$
    • This means $a$ is a multiple of $p$
    • So then $p\mid a$ which is a contradiction of our assumption $p\nmid a$

  ---

  • You can cancel out the $a$s if they're coprime.
  • Proving that $ma\equiv na(\mathrm{mod}p)$
    • By assumption $ma\equiv na(\mathrm{mod}p)$
    • So $p\mid ma-na$
    • $p\mid a(m-n)$
    • If $p$ and $a$ are coprime, then $p$ must divide $m-n$ because $p\nmid a$
    • So $a$ is a multiple of $m-n$
    • So then $p\mid m-n$ which prove $m\equiv n(\mathrm{mod}p)$
• Line 3:
  • $S$ has $p$ elements, ${\mathbb{Z}}_p$ has $p$ elements
  • Then $S={\mathbb{Z}}_p$
  • We can use the fact that $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ is injective, same Cardinality, so it's bijective, so same cardinality.
  • So multiplying non-zero elements together will give the same result.
• Line 4:
  • Multiply $S$ on the left side
  • Multiply ${\mathbb{Z}}_p$ on the right side
  • Example:
    • When $a=3,p=5$
    • Multiply the non-zero
    • $1(3)2(3)3(3)4(3)\equiv (1)(2)(3)(4)(\mathrm{mod}5)$
    • $3^4(1\cdot 2\cdot 3\cdot 4)\equiv (1)(2)(3)(4)(\mathrm{mod}5)$
• Line 5:
  • $(p-1)!a^{p-1}=(p-1)!(\mathrm{mod}p)$
  • To divide by $(p-1)!$, the $gcd(p,(p-1)!)=1$
  • For the sake of contradiction, suppose $gcd(p,(p-1)!)=p$
    • Then $p\mid (p-1)!$
    • $p\mid (1)(2)(3)\dots (p-1)$
    • Since $p$ divides the product, it must divide one of those numbers.
    • So $p\mid k$ for some $k\in \{1,\dots ,p-1\}$
    • This is a contradiction because $p$ is prime and everything in $k$ is less than $p$