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?
Best Answer
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.