# Fermat's little theorem special case

I am trying to prove a special case of Fermat's little theorem, but i am new to number theory, so i am stuck with this exercise...may i ask you for a little help?

Let $k\in \mathbb{N}$, given are three prime numbers $p_{1}=6k+1, p_{2}=12k+1, p_{3}=18k+1$ and let $m=p_{1}\cdot p_{2}\cdot p_{3}$. Prove that $a^{m-1}\equiv1(modm)$ for all $gcd(a,m)=1$.

How can i start with this proof? I have a classical proof of Fermat's little theorem, but somehow i can't use it for this case... Thank you in advance!

## 1 Answer

It is enough to show that $a^{m-1}\equiv 1 \pmod{p_i}$ for $i=1$, $2$, and $3$.

The case $i=1$ is too easy, so we do $i=2$. Note that by Fermat's Theorem we have $a^{12k}\equiv 1\pmod{p_2}$, so for any integer $n$ we have $a^{12kn}\equiv 1\pmod{p_2}$.

So it is enough to show that $m-1$ is a multiple of $12k$.

Calculate. We have $$\small m-1=(12k+1)(6k+1)(18k+1)-1=12k(6k+1)(18k+1)+(6k+1)(18k+1)-1.$$ Expand a little more. We get $$\small m-1=12k(6k+1)(18k+1) + 108k^2 +24k.\tag{A}$$ The number on the right-hand side of (A) is clearly divisible by $12k$, so we are finished with $p_2$.

As was mentioned earlier, dealing with $p_1$ in more or less the same way will be very easy, and dealing with $p_3$ is much like dealing with $p_2$. We leave dealing with these to you.

Remark: The problem is not a special case of Fermat's Theorem. Fermat's Theorem says that if $m$ is prime and $a$ and $m$ are relatively prime, then $a^{m-1}\equiv 1\pmod{m}$. But our $m$ is definitely not prime.

• Thank you very much! Now i got it :) it was actually a simple question. but thanks again! – Lullaby Jun 25 '13 at 11:33
• You are welcome. It is technically straightforward, but connected with important matters, pseudoprimes, Carmichael numbers. – André Nicolas Jun 25 '13 at 12:05