# Prove that for any odd integer a, $a^{33} \equiv a \pmod {4080}$

Use Euler's theorem to prove that:

For any odd integer a, $$a^{33} \equiv a \pmod {4080}.$$

The hint given in the book is that $$4080 = 15 \times 16 \times 17$$, but I do not know how to use Euler's theorem to deal with $$n = 15,17$$,the condition $$gcd (a,n) =1$$ is not satisfied in those cases, could anyone clarify this for me please?

• Why did you tag your question under "convergence"? – uniquesolution May 31 '19 at 5:45
• I am sorry it was a mistake@uniquesolution – Secretly May 31 '19 at 5:52

Euler's theorem for primes (Also known as Fermat's little theorem) tells you that $$a^{p-1}\equiv 1\mod p$$ if $$\gcd(p,a)=1$$.

For $$p=3$$ you have

$$a^2\equiv 1\mod 3$$ if $$\gcd (a,3)=1$$. So, $$a^{33}\equiv (a^2)^{16}a\equiv a\bmod 3$$ if$$\gcd (a,3)=1$$. But note that $$a^{33}\equiv a\bmod 3$$ also in the case when $$3|a$$ (in that case $$a^{33}\equiv a\equiv 0\bmod 3$$.)

So, $$a^{33}\equiv a\mod 3$$ for all $$a$$.

Do the same for $$p=5$$, $$p=17$$ and prove that $$a^{33}\equiv a\mod 5$$ and $$a^{33}\equiv a\mod 17$$.

Finally, since $$a$$ is odd, $$\gcd(16,a)=1$$. So, Euler's theorem tells you that $$a^8\equiv 1\mod 16$$. Conclude from here that $$a^{33}\equiv a\mod 16$$.

If you have $$a^{33}\equiv a$$ mod 3,5,16,17. Then you have your result.

Short answer: Since $$\varphi(3)$$,$$\varphi(5)$$,$$\varphi(17)$$,$$\varphi(16)$$ are divisors of $$32$$. Then $$a^{33}\equiv a\mod(3\times 5\times 17\times 16).$$

Using Fermat's Little Theorem

$$17$$ divides $$a^{16m+1}-a$$

$$3$$ divides $$a^{2n+1}-a$$

$$5$$ divides $$a^{4p+1}-a$$

So, we need $$16m=2n=4p\implies n=8m,p=4m$$

Using Carmichael Function as $$a$$ is odd $$a^{2^n}\equiv1\pmod{2^{n+2}}$$ for $$n\ge2$$

If $$n=4\implies2^{4+2}$$ divides $$a^{16}-1$$ which again divides $$(a^{16})^r-1^r$$

$$\implies2^6$$ divides $$a^t-1$$ if $$16|t$$

So, $$a^{16m+1}-a$$ will be divisible by lcm of $$(3,5,17,2^6)$$

Here $$16m+1=33$$