# Prove 7 divides $15^n+6$ with mathematical induction

Prove that for all natural numbers statement n, statement is dividable by 7

$$15^n+6$$

Base. We prove the statement for $n = 1$

15 + 6 = 21 it is true

Inductive step.

Induction Hypothesis. We assume the result holds for $k$. That is, we assume that

$15^k+6$

is divisible by 7

To prove: We need to show that the result holds for $k+1$, that is, that

$15^{k+1}+6=15^k\cdot 15+6$

and I don't know what to do

• If you have a problem actually writing down the inductive argument, take a look at Arturo's good general advice in this post and try and apply it to your problem: math.stackexchange.com/questions/19370/… – Derek Jennings Feb 16 '11 at 12:41
• @Derek Jennings: Like this? – Templar Feb 16 '11 at 12:55
• @Templar: Let's say it's heading in the right direction but it would not be accepted as a full answer as you have not finished off the inductive step using the induction hypothesis, though no doubt you can do this since you've accepted Apostolos's answer. Remark: induction is overkill for this problem since $15 \equiv 1 \pmod{7}$ and so $15^n \equiv 1 \pmod{7}.$ – Derek Jennings Feb 16 '11 at 18:45
• @Derek: I agree that congruence considerations give a shorter and more insightful solution than induction. Whether induction is overkill depends upon how comfortable the student is with congruence arguments (and, for instance, whether s/he knows the concept of congruence at all). I recently taught a "transitions" course that covered both of these topics, and a lot of my students were -- surprisingly to me -- more comfortable with the induction argument. – Pete L. Clark Feb 16 '11 at 22:59
• (The point, I guess, is that congruences are more abstract than induction. Some people are better at problem solving than thinking abstractly; others the reverse...) – Pete L. Clark Feb 16 '11 at 23:00

Observe that $14$ is divisible by 7. Then let $15^k\cdot 15+6=15^k\cdot 14+ 15^k+6$.

By induction hypothesis, you have $15^k=7t-6$.

• Could you explain more about it? – Templar Feb 16 '11 at 12:46
• @Templar: $15^{k+1}+6=15^k\cdot 15+6 = (7t-6)\cdot 15+6=7\cdot 15t-90+6=7(15t-12)$ – lhf Feb 16 '11 at 12:49
• So you just guess that $15^k=7t-6$ and then prove that is true, right? – Templar Feb 16 '11 at 13:02
• @Templar: No, the induction hypothesis says that $15^k+6$ is a multiple of $7$. So $15^k+6=7t$ for some integer $t$. – lhf Feb 16 '11 at 13:04
• Ah, I got it, thanks – Templar Feb 16 '11 at 13:07

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!