# In Fermat's little theorem, if mod is not prime?

Today I learned about Fermat's little theorem

It says -

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as $a^p \equiv a \mod p$

It considers "p" as a prime numbers. But what if "p" is not prime? Then if those cases how to solve this type of problems?

There is a generalised form of Fermat, often known as the Fermat-Euler theorem.

Normally we write Fermat as $a^{p-1}\equiv 1 \mod p$

Then the generalised form is $a^{\phi(n)}\equiv 1 \mod n$ for $(a,n)=1$ i.e. $a$ is coprime to $n$

$\phi(n)$ is known as the Euler Totient Function and counts the number of integers between $1$ and $n-1$ which are coprime to $n$. For a prime $p$ this is all $p-1$ of them. In the general case, various proofs including a version of inclusion-exclusion say that if $$n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$$ where the $p_i$ are the distinct prime divisors of $n$ then $$\phi(n)=n\left(1-\frac 1{p_1} \right) \left(1-\frac 1{p_2} \right)\dots \left(1-\frac 1{p_r} \right)$$

One way to see the generalised result is to note that the numbers having $0\lt r\lt n$ and $(r,n)=1$ form group under multiplication $\mod n$ - it is easy to see that they include $1$ and they inherit associativity from the integers. They are closed under multiplication, and a counting argument shows that inverses must exist. $\phi(n)$ is the order of this group.

• Was beaten to it... – George1811 Apr 1 '14 at 14:52

There is the Carmichael Theorem, which provides results stronger than Euler's Theorem, which generalizes Fermat's Little Theorem to non-prime modulo.