# Proof Verification - divisibility through induction

I'm studying for a final and was wondering if this proof is correct. I've seen several variants but they all seem less logical, so I want to make sure I'm not overlooking something.

The proof is essentially: Prove, using induction that $$5 | 11^{n} - 6$$, for all positive integers n

Here is my proof: Base case, n = 1

$$11^1 - 6 = 5$$ which is divisible by 5.

Inductive hypothesis:: Assume the proposition is true for some $$k \in Z^{+}$$, or 5|$$11^k - 6$$

Inductive step: Prove, using the assumption made in the previous step that $$5 | 11^{k+1} - 6$$ From our inductive hypothesis we know that there exists some positive integer a such that 5a = $$11^{k} - 6$$

$$5 | 11^{k+1} - 6$$

$$11^{k+1} - 6$$ = $$11^k * 11^1 - 6$$ but, we know that 5a = $$11^k - 6$$, so substituting, we get: $$11*5a = 55a$$, which is a factor of 5.

Thus, the proposition holds.

• Why do you say $5|11^{k+1} - 6\cdot 11^{k+1} - 6$? And why do you say $11^{k+1} - 6\cdot 11^{k+1} - 6 = 11^k*11^k - 6$? And what does that have to do with $11*5a = 55a$? Which is a multiple of $5$; not a factor of $5$. – fleablood Dec 5 '19 at 1:54
• sorry, that was a typo, I've edited my solution. – Evan Dec 5 '19 at 2:08
• also, if something is a multiple of 5, then it is a factor of 5, I thought – Evan Dec 5 '19 at 2:09
• Not following your substitution step. Seems to me easiest approach is to use the fact that $11^k$ always ends in 1 and therefore $11^k-6$ always ends in 5. – Goldbug Dec 5 '19 at 2:28
• ah yes you're right, I have a mistake there, thanks! – Evan Dec 5 '19 at 2:42

An easier solution for the induction step may be that if $$11^k-6=5m$$ for some integer $$m$$,
i.e. $$11^k=5m+6$$
then $$11^{k+1}=11(5m+6)=55m+66 = 5(11m+12)+6$$
i.e. $$11^{k+1}-6=5(11m+12)$$
or in other words, if $$11^k-6$$ is a multiple of $$5$$ then $$11^{k+1}-6$$ is also a multiple of $$5$$