The Problem
Prove that for any integer $a, a^{15}-a^3$ is divisible by $455$.
Hint: $455=5*7*13$. We proved that if $n$ is divisible by $x$, and $n$ is divisible by $y$, and $\gcd(x,y) = 1$, then $n$ is divisible by $x*y$. The upshot of this is that if $a^{15}-a^3$ is divisible by $5$, and by $7$, then it is divisible by $5*7=35$. And if $a^{15}-a^3$ is divisible by $5$, $7$, and $13$, then it is divisible by $5*7*13$. So you need to prove that $a^{15}-a^3$ is divisible by $5$, by $7$, and by $13$.
Confusion
My first guess was to try induction, although I wasn't sure if induction can even be used here since we are dealing with integers instead of natural numbers, so perhaps that is my first issue. Even if this were a statement about natural numbers, I was still unable to figure out how induction could work here.
Secondly, the hint my instructor provided for this problem makes sense to me, but I haven't the slightest clue as to how to prove what's being asked. For instance, how do we prove that $5|a^{15}-a^3$? Induction seems to get us nowhere because you end up with $(k+1)^{15}-(k+1)^3$, and that seems like an insane amount of algebra. There has to be something I'm missing here.
Any thoughts?
Note that if we set $a^3=t$, $$a^{15}-a^{3} \equiv t^{5}-t \equiv 0 \pmod {5}$$ By Fermat's Little Theorem, which says that $a^{p} \equiv a \pmod {p}$ if $p$ is prime. Furthermore, we notice that $$a^{15}-a^{3}=\color{blue}{(a^{7}-a)}(a^{8}+a^2) \equiv 0 \pmod {7}$$ Using Fermat's Little theorem when $p=7$, and similarly $$a^{15}-a^{3}=a^2 \times \color{orange}{(a^{13}-a)} \equiv 0 \pmod {13}$$ Hence, $a^{15}-a^{3}$ is divisible by $5$, $7$, and $13$, which implies that it is divisible by $5 \times 7 \times 13=455$. We are done.
If you truly want to use induction, see the proof of Fermat's little theorem by Euler using induction. You don't really need that much calculations, but it does require knowledge of the binomial theorem.