Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
A generalisation of Fermat's little theorem en.wikipedia.org/wiki/Euler%27s_theorem –  George1811 Apr 1 at 14:52

2 Answers 2

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.

share|improve this answer
    
Was beaten to it... –  George1811 Apr 1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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