prove that $2^{15} - 2^3 $ divides $ a^{15} - a^3$ Prove that $$2^{15} - 2^3 $$ divides $$ a^{15} - a^3$$ for any integer $a$.
Hint: $$ 2^{15} - 2^3 = 5\cdot7\cdot8\cdot9\cdot13$$
 A: Hint: If $13\mid a$, then $13$ divides $a(a^{14}-a^2)=a^{15}-a^3$.  Otherwise, by Euler's theorem, $13$ divides $a^{12}-a^0$, hence also $a^3(a^{12}-a^0)=a^{15}-a^3$.
A: Hint:
Use Fermat or Euler theorem to prove that
$a^{15}-a^{3}$ is congruent to 0 mod 5, 7, 8, 9 and 13 respectively.
A: Hint $\ $ If $\,3\mid a\,$ then $\,3^2\mid a^3\mid a^3(a^{12}-1).\,$ Else $\,a\,$ is coprime to $\,3\,$ and $\,\phi(3^2) = \color{#c00}6,\,$ so  by Euler, $\,{\rm mod}\ 3^2\!:\ a^{\color{#c00}{6}}\equiv1\,\overset{\rm square}\Rightarrow\,a^{12}\equiv 1^2\equiv 1.\,$  Therefore  $\, 3^2\mid a^3(a^{12}-1)\,$ for all $\,a\in\Bbb Z.$
The same idea works for all other the other factors $\,p^n$ since $\,n\le 3\,$ so $\,p\mid a\Rightarrow p^n\mid a^3;$ otherwise $\,a\,$ is coprime to $\,p,$ so by Euler $\,p^n\mid a^{12}-1\,$ since $\,\phi(p^n)\mid 12\,$ in all cases. Therefore, generally
Theorem $ \!\!\!\!\! \underbrace{\,p_1^{n_1}\cdots p_j^{n_j}}_{\large p_i\, \rm distinct\ primes\ \ \ }\!\!\!\!\!\!\!\!\!\mid a^n(a^\phi-1)\ $ for all $\,a\,$ when $ $ all $\,n_i\le n\,$ and all $\,\phi(p^{n_i})\mid \phi\,$
See here for the simple proof, and links to many worked examples.
A: Apply  Carmichael function,
to find $\lambda(8)=2,\lambda(5)=\phi(5)=4, \lambda(9)=\phi(9)=6$ etc.
Then, for $9, F=a^{15}-a^3=a^3(a^{12}-1)=a^3(a^6-1)(a^6+1)$
As $3$ is prime, ether $(i)\ 3|a\implies 3^3|F$ or $(ii)\ (3,a)=1\implies 9|(a^6-1)$
For $8, F=a^{15}-a^3=a^3(a^{12}-1)$
As $2$ is prime, ether $(i)\ 2|a\implies 2^3|F$ or $(ii)\ (2,a)=1\implies 8|(a^2-1)$
For $5, F=a^{15}-a^3=a^3(a^{12}-1)=a^3\{(a^4)^3-1\}=a^3(a^4-1)(a^8+a^4+1)$
As $5$ is prime, ether $(i)\ 5|a\implies 5|F$ or $(ii)\ (5,a)=1\implies 5|(a^4-1)$
Similarly for $7,13$
A: Use the hint. Show that 5,7,8,9 and 13 divide any $a^{15}-a^3$. Also, the factorization of $a^{15}-a^3$ is $a^3(a^{12}-1)$. If $a$ is divisible by any member of $\{5,7,8,9,13\}$, then $a^{15}-a^3$ is also divisible by that number. If it's not, then by Fermat little theorem $$a^p-1 \equiv 0\mod p$$ for the primes in the set. Then show that $a^p-1$ divides $a^{12}-1$. Now for $8$ and $9$, you'll have to go the more traditional way, but they're easy to show.
A: We can factor:
$$a^{15}-a^3=a^3(a-1)(a+1)(a^2+1)(a^2+a+1)(a^2-a+1)(a^4-a^2+1)$$
Now, we just need to prove that this is divisible by $2^3\cdot3^2\cdot5\cdot7\cdot13$.
If $a$ is odd, $(a-1)(a+1)(a^2+1)$ is the product of three even numbers, and is divisible by 8.  If $a$ is even, $a^3$ is divisible by 8.
If $a$ is a multiple of 3, $a^3$ is divisible by $9$.  Otherwise, one of $(a-1)$ and $(a+1)$ is divisible by 3, as is one of $(a^2-a+1)$ and $(a^2+a+1)$, and therefore $a^2(a-1)(a+1)(a^2-a+1)(a^2+a+1)$ is divisible by 9.
If $a$ is a multiple of 5, obviously so is our product.  If not, $a^2$ is either 1 more or one less than a multiple of 5, so $a(a-1)(a+1)(a^2+1)$ is divisible by 5.
Consider $a\mod7$.  If it's 0, then $a$ is divisible by 7.  If it's 1, $(a-1)$ is divisible by 7.  If it's 2 or 4, $(a^2+a+1)$ is divisible by 7.  If it's 3 or 5, $(a^2-a+1)$ is divisible by 7.  If it's 6, $(a+1)$ is divisible by 7.  Regardless, our product is divisible by 7.
Consider $a\mod13$.  If it's 0, then $a$ is divisible by 13.  If it's 1, $(a-1)$ is divisible by 13.  If it's 2 or 6 or 7 or 11, $(a^4-a^2+1)$ is divisible by 13.  If it's 3 or 9, $(a^2+a+1)$ is divisible by 13.  If it's 4 or 10, $(a^2-a+1)$ is divisible by 13.  If it's 5 or 8, $(a^2+1)$ is divisible by 13.   If it's 12, $(a+1)$ is divisible by 13.  Regardless, our product is divisible by 13, and we're done.
A: This is meant mostly as a joke, but partly not:
We clearly have $2^{15}-2^3=32{,}760$ divides $a^{15}-a^3$ when $a=0$, $\pm1$, and $\pm2$, so that leaves only $32{,}755$ other cases to check....
(The part that's not meant as a joke is the implicit question, where do you draw the line between proving something by brute force computation versus spending time looking for a clever theory.)
