prove that $a^{25}-a$ is divisible by 30 I'm trying to prove that $30|a^{25}-a$.
First of all I said that it equals
$a(a^3-1)(a^3+1)(a^6+1)(a^{12}+1)$, so that it must be divisible by 2.
Now I want to show it can be divided by $3,6$ using Fermat's little theorem.
I need a bit of direction since I'm kind of lost.
 A: You need divisibility by $2,3,5$.
$a$ and $a^3-1$ are of different parity, so one of them is odd, one is even. Thie product is of course even.
$a^3\equiv a\pmod{3}$, so one of numbers $a^3-1$, $a$, $a^3+1$ is always divisible by $3$.
Now, for $5$.


*

*The case $5|a$ is trivial.

*$a\equiv 1\pmod{5}\implies a^3\equiv 1\pmod{5}\implies 5|a^3-1$

*$a\equiv 2\pmod{5}\implies a^6+1\equiv 65\equiv 0\pmod{5}\implies 5|a^6+1$

*$a\equiv 3\pmod{5}\implies a^6\equiv 9^3\equiv (-1)^3\equiv -1\pmod{5}\implies 5|a^6+1$

*$a\equiv 4\pmod{5}\implies a\equiv -1\pmod{5}\implies a^3\equiv -1\pmod{5}\implies 5|a^3+1$
A: Hint. By Fermat's little theorem, for any prime $p$,
$a^{p}-a$ is divisible by $p$. Moreover, the polynomial $P(a)=a^{25}-a$ is divisible by $(a^r-a)$ for $r=2,3,5$.
A: As $(a^n-a)$ divides $a^{25}-a$ for $n=2,3,5,7,13$. For Little Fermat Theorem we know that $p$ divides $a^p-a$ for primes $p$, so $a^{25}-a$ is divisible by $2730$ for any integer $a>1$
Hope this helps
A: Since nobody mentioned Euler theorem here is another answer. 
If $\gcd(a,30)=1$ then $a^{\varphi(30)} \equiv 1 \pmod{30}$ and $\varphi(30)=8$. Or $30 \mid a^8-1$ and $a^{25}-a=a(a^{24}-1)=a(a^8-1)(a^{16}+a^8+1)$. Thus $30 \mid a\cdot(a^{24}-1)$
If $\gcd(a,30)=d \in \{2,3,5,6,10,15,30\}$ then


*

*$d=30$ then $30 \mid a \Rightarrow 30 \mid a\cdot (a^{24}-1)$

*in all the other cases $30=d\cdot d_1$, $d \mid a$ and $\gcd(d_1,a)=1$  then $$a^{\varphi(d_1)} \equiv 1 \pmod{d_1} \tag{1}$$ or $30=d\cdot d_1 \mid a\cdot (a^{\varphi(d_1)}-1)$. But $d_1 \in \{2,3,5,6,10,15\}$ as well and $\varphi(2)=1,\varphi(3)=2,\varphi(5)=4, \varphi(6)=2, \varphi(10)=4, \varphi(15)=8$ all are factors of $24$. Or $24=\varphi(d_1)\cdot q$ and from $(1)$ $$a^{24}\equiv a^{\varphi(d_1)\cdot q} \equiv 1^{q} \equiv 1 \pmod{d_1}$$ Thus $30=d\cdot d_1 \mid a\cdot (a^{24}-1)$ too.

A: Perhaps a direct proof would be to express the Chinese remainder theorem as an isomorphism of rings $\mathbf Z/30 \cong  \mathbf Z/2 \times \mathbf Z/3 \times \mathbf Z/5$. Write $[a_{30}]=([a_2], [a_3], [a_5])$ (obvious notation) and apply FLT to the 3 factors, using  $25 = 1+2^3.3 = 1+ 3.2^3 = 5^2$, so that $[a_2]^{25}=[a_2].([a_2]^8)^3=[a_2].[a_2]^3=[a_2]$, and $[a_3]^{25}=[a_3].([a_3]^3)^8=[a_3]^9=[a_3]$, and $[a_5]^{25}=([a_5]^5)^5=[a_5]$ .
