<s>[INST] 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$$
 [/INST] 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.
</s>