1
$\begingroup$

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$.

My question is whether this is true for all primes $p$ and $n\in\mathbb{Z}$ and if so, how to prove it. Also, are there any non-primes for which the relation holds?

It might be a very basic fact I've forgotten.

$\endgroup$
4
$\begingroup$

This is exactly Fermat's Little Theorem.

$\endgroup$
3
$\begingroup$

"Also, are there any non-primes for which the relation holds?"

Yes.

It is called Euler's Theorem, and is basically a generalization of Fermat's Little Theorem.

It states the following:

Let $\gcd(a,n)=1$

Then $$a^{\phi(n)} \equiv 1 \pmod{n}$$

Proof:

Let $a_1,a_2,a_3,\dots a_{\phi(n)}$ be the reduced canonical residues modulo $n$. As $(a,n)=1$ $aa_1,aa_2,\dots,aa_{\phi(n)}$ are also a complete set of incongruent reduced residues.

Thus,

$$aa_1\cdot aa_2\cdots aa_{\phi(n)} \equiv a_1a_2\cdots a_{\phi(n)} \pmod{n}$$

$$a^{\phi(n)}a_1a_2\cdots a_{\phi(n)}\equiv a_1a_2\cdots a_{\phi(n)}$$

Since, $\gcd(a_1a_2\cdots a_{\phi(n)},n)=1$ we may cancel it out of both sides,

$$a^{\phi(n)} \equiv 1 \pmod{n}$$


If $n$ is prime, then $\phi(n)=n-1$ and if $\gcd(a,n)=1$. Then we have,

$$a^{n-1}\equiv 1 \pmod{n} \iff a^n\equiv a\pmod{n}$$

On the other hand, if $\gcd(a,n)\ne1$, then $n|a$ since $n$ is prime, and both sides are congruent to $0$ modulo $n$.

Thus Fermat's little theorem is a special case of Euler's Theorem.


Note: $\phi(n)$ denotes Euler's totient function.

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