2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$
    – fleablood
    Dec 5 '19 at 1:54
  • $\begingroup$ sorry, that was a typo, I've edited my solution. $\endgroup$
    – Evan
    Dec 5 '19 at 2:08
  • $\begingroup$ also, if something is a multiple of 5, then it is a factor of 5, I thought $\endgroup$
    – Evan
    Dec 5 '19 at 2:09
  • $\begingroup$ 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. $\endgroup$
    – Goldbug
    Dec 5 '19 at 2:28
  • $\begingroup$ ah yes you're right, I have a mistake there, thanks! $\endgroup$
    – Evan
    Dec 5 '19 at 2:42
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.