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?
 A: 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).$
A: 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$
