Often textbook solutions to induction problems like this are magically "pulled out of a hat" - completely devoid of intuition. Below I explain the intuition behind the induction in this proof. Namely, I show that the proof easily reduces to the completely trivial induction that $\rm\ 1^n\ \equiv\ 1\:$.
Since $\rm\ 15^n + 6 = 15^n-1 + 7\:,\: $ it suffices to show that $\rm\ 7\ |\ 15^n - 1\:.\: $ The base case $\rm\ n=1\ $ is clear. The inductive step, slightly abstracted, is simply the following
$\quad\quad\quad\quad\quad\rm\ \ \ \ 7\ |\ \ c\ -1,\ \ \ d\ \:-\ 1\ \ \Rightarrow\ \ 7\ |\ cd-1 = (c-1)\ d + (d-1)$
$\quad$ thus $\quad\ \ \ 7\ |\ 15-1,\ 15^n-1\ \ \Rightarrow\ \ 7\ |\ 15^{n+1}-1$
Said $\rm\ mod\ 7,\ \ 15\equiv 1\ \Rightarrow\ 15^n\equiv 1^n\equiv 1\ $ by inductively multiplying ("powering") using this:
LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)\quad\quad$ (product rule for congruences)
Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $
Notice how this transformation from divisibility form to congruence arithmetic form has served to reduce the induction to the triviality $\rm\: 1^n \equiv 1$. Many induction problems can similarly be reduced to trivial inductions by appropriate conceptual preprocessing. Always think before calculating!