Here's a generalisation
Given a prime for every natural number we have: (Fermat's little Theorem)
Let us show it by induction as well.
The assertion is obvious for
Now suppose it holds for (1), we'll show it's also true for
By the Binomial Theorem:
But now note that: whenever (k natural) indeed is a natural number, but since then doesn't divide so it must be that
Thus we have:
And by (1) we have: so that