# Divisibility Proofs

• Aug 18th 2012, 07:16 AM
GrigOrig99
Divisibility Proofs
I think I have this one right. Can anyone help confirm if I've solved this correctly?

Many thanks.

Q. 13n - 6n-2 is divisible by 7 for n $\displaystyle \in \mathbb{N}_0$

Attempt: Step 1: For n = 1,
131 - 61-2 = 13 - 6-1 = 13 - 0.166 = 12.833, which cannot be divided by 7.
However, if n = n + 1: 13n - 6n-2 = 13n+1 - 6n-1
Now, for n = 1,
132 - 60 = 169 - 1 = 168, which can be divided by 7.

Step 2:
Assume the statement is true for n = k,
i.e. assume 13k+1 - 6k-1 can be divided by 7
13k+1 - 6 k-1 = 7Z, where Z is an integer...1
We must now show that the statement is true for n = k + 1,
i.e. 13k+2 - 6 can be divided by 7.
13k+2 - 13(6k-1) + 13(6k-1) - 6k = 13(13k+1 - 6k-1) - 6k-1(6 - 13)...from 1 above = 13(7Z) - (-7)(6k-1) = 91Z + 7(6k-1) = 7[13Z + 6k-1], which can be divided by 7.

Therefore, the statement is true for n = k + 1, assuming it is true for n = k.
Thus the statement is true for n = 2, 3... & all n $\displaystyle \in \mathbb{N}_0$
• Aug 18th 2012, 08:24 AM
richard1234
Re: Divisibility Proofs
Slight error with your induction step - if n = k, then $\displaystyle 13^k - 6^{k-2} \equiv 0 (\mod 7)$. I think you replaced k with k+1 or something. Also, n = 2 yields 168.

Assuming the n = k case is true, you can show that n = k+1 works by showing that

$\displaystyle (13^{k+1} - 6^{k-1}) - (13^{k} - 6^{k-2}) \equiv 0 (\mod 7)$, and proceed from there.

------------------------

A simpler solution would be to write $\displaystyle 13^n \equiv (-1)^n (\mod 7)$ and $\displaystyle 6^{n-2} \equiv (-1)^{n-2} (\mod 7)$. Then our expression is equivalent to

$\displaystyle (-1)^n - (-1)^{n-2} (\mod 7)$

Clearly, if n is odd or n is even, by substitution we obtain 0 mod 7, and we're done.
• Aug 18th 2012, 08:31 AM
Deveno
Re: Divisibility Proofs
some technical fusses:

n is never equal to n+1, if you want to consider something equal to n+1, you should write:

n' = n+1, or something similar.

since the statement does not hold for n = 0, OR n = 1, it does not hold for $\displaystyle \mathbb{N}}_0$. it holds for $\displaystyle \mathbb{N}_0 - \{0,1\}$, or:

"all natural numbers ≥ 2". mathematical statements should be true. one tiny exception can have devastating results.

you're missing a "k" in the exponent after the 6 in your statement of the n = k+1 case. this is probably just a typo, but someone will read your proof, you want it to make sense.

i would add this equation at the start of your proof of the n = k+1 case:

13k+2 - 6k = 13k+2 - 13(6k-1) + 13(6k-1) - 6k

again, your concluding statement is not quite correct, it should probably end with: "....and therefore for all n ≥ 2 in $\displaystyle \mathbb{N}_0$."

other than that, it looks good.

EDIT: in light of richard1234's comments, yes: he is correct, if you are now inducting over n' = n+1, your statements should reflect this:

"for the n' = k case: ...."

"for the n' = k+1 case: ...."

*********

if you are being asked to give an induction proof, then i suppose you will have to give an induction proof. if you are proving something "by hook or by crook" (that is, you can use any method that works), then modular arithmetic *can* simplify things. the key observation here, is that (mod 7) 13 and 6 are the same number: -1.
• Aug 18th 2012, 09:58 AM
GrigOrig99
Re: Divisibility Proofs
Great. Thank you very much!!
• Aug 18th 2012, 11:56 AM
Soroban
Re: Divisibility Proofs
Hello, GrigOrig99!

Quote:

$\displaystyle 13^n - 6^{n-2}\,\text{ is divisible by 7 for }n \ge 2.$

This can be written

. . $\displaystyle S(n)\!:\;13^{n+1} - 6^{n-1}\,\text{ is divisible by 7 for }n \in N.$

$\displaystyle \text{Verify }S(1)\!:\;13^2 - 6^0 \:=\:169 - 1 \:=\:168 \:=\:7\cdot24\;\hdots \text{ True.}$

$\displaystyle \text{Assume }S(k)\!:\;13^{k+1} - 6^{k-1} \:=\:7a\,\text{ for some integer }a.$

$\displaystyle \text{We must prove that }\,13^{k+2} - 6^k\,\text{ is multiple of 7.}$

$\displaystyle \text{We have: }\:13^{k+2} - 6^k$

. . . . . $\displaystyle =\;13\!\cdot\!13^{k+1} - 6^k$

. . . . . $\displaystyle =\;(7+6)13^{k+1} - 6^k$

. . . . . $\displaystyle =\;7\!\cdot\!13^{k+1} + 6\!\cdot\!13^{k+1} - 6^k$

. . . . . $\displaystyle =\;7\!\cdot\!13^{k+1} + 6\!\cdot\!13^{k+1} - 6\cdot6^{k-1}$

. . . . . $\displaystyle =\;7\!\cdot\!13^{k+1} + 6\underbrace{\left(13^{k+1} - 6^{k-1}\right)}_{\text{This is }7a}$
. . . . . $\displaystyle =\;7\!\cdot\!13^{k+1} + 6(7a)$

. . . . . $\displaystyle =\;7\left(13^{k+1} + 6a\right)$

$\displaystyle \text{Hence, }13^{k+2} - 6^k\text{ is a multiple of 7.}$

$\displaystyle \text{The inductive proof is complete.}$