1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ First of all, those two statements ate not the same. The second is only true if $p$ does not divide $a$, while the first is true for any $a$. $\endgroup$ – Thomas Andrews Aug 2 '15 at 22:59
  • $\begingroup$ @Thomas Andrews Right, I was reading a source online that explained that you can get from the first to the second by dividing both sides by a, if "a and p are coprime". However, it did not explain why this is the case? $\endgroup$ – b_pcakes Aug 2 '15 at 23:04
  • $\begingroup$ For what it's worth, the names of the theorems in the title are confusing people - you are using Euler's theorem in a non-standard way. See: en.wikipedia.org/wiki/Euler%27s_theorem $\endgroup$ – Thomas Andrews Aug 2 '15 at 23:12
  • $\begingroup$ The "necklace proof" of fermat's little theorem is worth a read if you haven't already $\endgroup$ – user256916 Aug 2 '15 at 23:13
  • $\begingroup$ @Thomas: What makes you conclude he's "using Euler's theorem in a non-standard way"? Note that he's asking two questions separated by "and also", not one question phrased in two different ways. $\endgroup$ – hmakholm left over Monica Aug 2 '15 at 23:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Kudos and +1 for the simplicity of the explanation, just as the OP asked. Not enough people here heed such requests when they're made. $\endgroup$ – wltrup Aug 2 '15 at 23:50
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please expand on the last part? How do you combine a^{(p-1)k+1}= a mod p and a^{(q-1)k+1}= a mod q to get a^((p-1)(q-1)+1)= a mod both p and q? $\endgroup$ – b_pcakes Aug 2 '15 at 23:44
  • $\begingroup$ @SimonZhu: Please think just a little bit for yourself. If you have $a^{(p-1)k+1}\equiv a\pmod p$ and want $a^{(p-1)(q-1)+1}\equiv a\pmod p$, then at least start by comparing the two equations and find out what the difference is. The difference is that one says $k$ where the other says $q-1$. Was $k$ arbitrary? Yes it was. Is $q-1$ a possible value for an aribitrary integer? Yes it is. $\endgroup$ – hmakholm left over Monica Aug 3 '15 at 1:53
1
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The link is expired. $\endgroup$ – Bingyan Liu Oct 17 '18 at 6:33
1
$\begingroup$

(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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.