# Math Help - Divisibility Proofs

1. ## 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 $\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 $\in \mathbb{N}_0$

2. ## Re: Divisibility Proofs

Slight error with your induction step - if n = k, then $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

$(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 $13^n \equiv (-1)^n (\mod 7)$ and $6^{n-2} \equiv (-1)^{n-2} (\mod 7)$. Then our expression is equivalent to

$(-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.

3. ## 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 $\mathbb{N}}_0$. it holds for $\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 $\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.

4. ## Re: Divisibility Proofs

Great. Thank you very much!!

5. ## Re: Divisibility Proofs

Hello, GrigOrig99!

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

This can be written

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

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

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

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

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

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

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

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

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

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

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

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

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