Divisibility Proofs

**GrigOrig99** · August 18th 2012, 07:16 AM

I think I have this one right. Can anyone help confirm if I've solved this correctly?

Many thanks.

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

Attempt: Step 1: For n = 1,
13¹- 6^1-2 = 13 - 6^-1 = 13 - 0.166 = 12.833, which cannot be divided by 7.
However, if n = n + 1: 13ⁿ - 6^n-2= 13ⁿ⁺¹ - 6^n-1
Now, for n = 1,
13² - 6⁰ = 169 - 1 = 168, which can be divided by 7.

Step 2: Assume the statement is true for n = k,
i.e. assume 13^k+1 - 6^k-1can be divided by 7
13^k+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. 13^k+2 - 6 can be divided by 7.
13^k+² - 13(6^k^-1) + 13(6^k-1) - 6^k = 13(13^k+1 - 6^k-1) - 6^k-1(6 - 13)...from 1 above = 13(7Z) - (-7)(6^k-1) = 91Z + 7(6^k-1) = 7[13Z + 6^k-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$

**richard1234** · August 18th 2012, 08:24 AM

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.

**Deveno** · August 18th 2012, 08:31 AM

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:

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

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.

**GrigOrig99** · August 18th 2012, 09:58 AM

Great. Thank you very much!!

**Soroban** · August 18th 2012, 11:56 AM

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

Thread: Divisibility Proofs

LinkBack

Thread Tools

Display