Deriving Euler's theorem from Fermat's little theorem

Question

I would like to know why $a^p \equiv a \pmod p$ is the same as $a^{p-1} \equiv 1 \pmod p$, and also how Fermat's little theorem can be used to derive Euler's theorem, or vice versa.

Please keep in mind that I have little background in math, and I am trying to understand these theorems to understand the math behind RSA encryption, so I would appreciate it if the explanation could be as simple as possible (i.e. not using too much mathematical notation). I have had trouble finding resources online to explain these theorems that explain it in simple enough terms that I can understand.

Answer 1

The statement that $a^p\equiv a\mod p$ is the same as $a^{p-1}\equiv 1\mod p$ when $a$ and $p$ are relatively prime, because in this case we can divide both sides of the congruence by $a$, and obtain one from the other.

Euler's theorem says that

$$a^{\phi(m)}\equiv 1\mod m,$$

where $\phi(m)$ is the number of integers less than $m$ and relatively prime to $m$. For a prime, this is exactly $p-1$, so Fermat's Little Theorem is a special case of Euler's theorem.

Answer 2

It is not obvious how to derive Euler's theorem in its full generality from Fermat's little theorem -- if the modulus has a non-trivial square factor, then Fermat's little theorem doesn't seem to provide enough.

Fortunately, for RSA you don't need Euler's theorem in its full generality; it is enough to know:

If $p$ and $q$ are two different primes, then $a^{(p-1)(q-1)+1}\equiv a\pmod{pq}$ for all $a$.

Here you can start by Fermat's little theorem and then prove $$ a^{(p-1)k+1}\equiv a \pmod p $$ for all $k$, by induction on $k$. Then do then same for $q$, and we have that $ a^{(p-1)(q-1)+1}\equiv a $ modulo both $p$ and $q$. The Chinese Remainder Theorem now concludes the claim above.

Answer 3

If $a^{k-1}\equiv 1\pmod{m}$, then $a^k\equiv a\pmod{m}$. For $a^{k-1}\equiv 1\pmod{m}$ says that $m$ divides $a^{k-1}-1$. And if $m$ divides $a^{k-1}-1$, then $m$ divides $a(a^{k-1}-1)$, that is, $m$ divides $a^k-a$, and therefore $a^k\equiv a \pmod{m}$.

However, the converse does not necessarily hold. If $a^k\equiv a\pmod{m}$, we cannot necessarily conclude that $a^{k-1}\equiv 1\pmod{m}$. But everything goes well if $a$ and $m$ are relatively prime. For suppose that $m$ divides $a^k-a$. Then $m$ divides $a(a^{k-1}-1)$. If $m$ and $a$ are relatively prime, then we can conclude that $m$ divides $a^{k-1}-1$.

Even in the special case where $m$ is the prime $p$, and $k=p$, we cannot conclude from $a^{p-1}\equiv a \pmod{p}$ that $a^{p-1}\equiv 1\pmod{p}$. For let $p=7$ and $a=14$. Then $14^7\equiv 14\equiv 0\pmod{7}$, but $14^{6}$ is not congruent to $1$ modulo $7$.

For primes we can say that if $a^p\equiv a\pmod{p}$, and $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$.

Answer 4

(For the first part.)

More generally, if $b\mid ac$ and $b$ and $a$ are relatively prime, then $b\mid c$. In this case, $b=p$ and $c=a^{p-1}-1$.

This more general theorem can be seen by "unique factorization," also known as the fundamental theorem of arithmetic. But it can also be proved first as a lemma for proving unique factorization.

It uses something called Bézout's identity, that says that if $a,b$ are relatively prime, then there is an integer solution to $ax+by=1$. Then multiplying by $c$ you get: $acx + bcy=c$. $acx$ is divisible by $b$, by assumption, and $bcy$ is obviously divisible by $b$, so $c$ is divisible by $b$.

Answer 5

They are not the same, if $\gcd(a,p)>1$, that is, if $p\mid a$, then $a^p\equiv a\pmod p$ is true while $a^{p-1}\equiv 1\pmod p$ is false. It follows that the first is always true for any $a\in\mathbb{Z}$, but the second only in the case where $\gcd(a,p)=1$.

As for the second question, assume $\gcd(a,p)=1$, thus provided that Fermat's little theorem is true as you ask, we know that $a^{\phi(m)}\equiv 1\pmod m$ when $m=p$, since the definition of Euler's totient function $\phi(x)$ says $\phi(p)=p-1$. In particular, $\phi(p^b)=(p-1)p^{b-1}$.

Thus, write $m=2^kp_1^{b_1}\cdot\ldots\cdot p_n^{b_n}$ for given $k,b_i>0$. Since

$$\phi(m)=2^{k-1}(p_1-1)p_1^{b_1-1}\cdot\ldots\cdot(p_n-1) p_n^{b_n-1}$$

you know that

\begin{array}{ll} a^{\phi(m)}&\equiv 1\pmod 2\\ a^{\phi(m)}&\equiv 1\pmod{p_1}\\ &\vdots\\ a^{\phi(m)}&\equiv 1\pmod{p_n}\\ \end{array}

because for each case $p_i-1$ is in the exponent for a given $i-th$ prime (for 2 it is trivial).

The last step is to show that $a^{(p-1)p^{b-1}}\equiv 1\pmod{p^b}$. Notice that by showing this we can conclude that

\begin{array}{ll} a^{\phi(m)}&\equiv 1\pmod 2\\ a^{\phi(m)}&\equiv 1\pmod{p_1^{b_1}}\\ &\vdots\\ a^{\phi(m)}&\equiv 1\pmod{p_n^{b_n}}\\ \end{array}

and from the fact that all divide $a^{\phi(m)}-1$ it would be safe to conclude that $a^{\phi(m)}\equiv 1\pmod m$ for all $m\in\mathbb{N}_{>0}$.

So, to prove that $a^{(p-1)p^{b-1}}\equiv 1\pmod{p^b}$ is the tricky part. We know that $a^{p-1}\equiv 1\pmod{p}$, but that a power $p^b$ must divide $a^{(p-1)p^{b-1}}-1$ is not trivial. To prove this fact, I use an old friend called Lifting the Exponent Lemma -- LTE (link: Lifting the Exponent Lemma).

It says: let $\gcd(x, p)=\gcd(y, p)=1$ for a prime $p$ and given whole numbers $x,\ y$, where $v_p$ is the maximum exponent $b$ such that $p^b\mid\ell$, for $\ell\in\mathbb{Z}$, then $v_p(x^n\pm y^n)=v_p(x\pm y)+v_p(n)$ for $n\in\mathbb{N}$.

From that we conclude that $v_p(a^{(p-1)p^{b-1}}-1^{(p-1)p^{b-1}})=v_p(a^{p-1}-1^{p-1})+v_p(p^{b-1})$, so clearly $a^{(p-1)p^{b-1}}\equiv 1\pmod{p^b}$.

I should say that the proof given by Euler is more economic and elegant. We don't need to actually use Fermat's little theorem to get Euler's theorem only because one is a particular case of the other.