1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

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

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.