Fermat's little theorem

Consider modular arithmetic under modulo $m$. We fix number $a$ so that ${\sf gcd}(a,m)=1$. Let us write a function $f_a: [m-1] \rightarrow [m-1]$ where $f_a(x) = a \cdot x \pmod{m}$. We argued before (when we proved that the inverse exists) that $f_a$ is a bijection. Therefore,

$\prod_{x\in[m-1]\setminus \{0\}} x \equiv \prod_{x \in [m-1]\setminus \{0\}}a\cdot x \pmod{m}$

This gives us $(a^{m-1}-1)(m-1)! \equiv 0 \pmod{m}$. Equivalently, $m$ divides $(a^{m-1}-1)(m-1)!$. When $m$ is prime, we know that $m$ divides $a^{m-1} -1$.

Theorem 18 (Fermat's little theorem (F$\ell$T))

For any prime $p$ and number $a$ that is not divisible by $p$, we have $a^{p-1} \equiv 1 \pmod{p}$.

Remark the distinction between the elementary F$\ell$T and the much-more-difficult-to-prove Fermat's Last Theorem (FLT). The correctness of RSA follows from a simple application of F$\ell$T.

Theorem 19 (Correctness of RSA)

We have that $x^{e\cdot d} \equiv x \pmod{N}$.

Proof:

Since $e \cdot d \equiv 1 \pmod{(p-1)(q-1)}$, we can write $e \cdot d = 1+ k (p-1)(q-1)$ for some integer $k$. Therefore,

$x^{e \cdot d} \equiv x^{1+k(p-1) (q-1)} \pmod{N}$

We argue that $x^{1+k(p-1)(q-1)} \equiv x \pmod{p}$ and $x^{1+k(p-1)(q-1)} \equiv x \pmod{q}$, which would imply the desired result (do you see why?). We only prove the former claim (the latter case is symmetrical). To prove $x^{1+k(p-1)(q-1)} \equiv x \pmod{p}$, we consider two cases:

• If $x$ is divisible by $p$, notice that $x^{1+k(p-1)(q-1)} - x$ is also divisible by $p$.
• If $x$ is not divisible by $p$, we can apply F$\ell$T to obtain $x^{p-1} \equiv 1 \pmod{p}$ and therefore $x^{1+k(p-1)(q-1)} \equiv x \pmod{p}$.

Exercise 49

Prove that $x^{10} \not\equiv -1 \pmod{31}$ for all integer $x$. Your proof should be at most a few lines (in particular, do not list all possible choices of $x$).