5
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Was beaten to it... $\endgroup$ – George1811 Apr 1 '14 at 14:52
4
$\begingroup$

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

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