# Math Help - Divisibility Proofs

1. ## Divisibility Proofs

Can anyone help me confirm if I've solved this correctly?

Many thanks.

Q.
$7^n+4^n+1$ is divisible by 6 for n $\in \mathbb{N}$

Attempt: Step 1: For n = 1...
$7^1+4^1+1=12$, which can be divided by 6.
Therefore, n = 1 is true...

Step 2: For n = k...
Assume $7^k+4^k+1$ can be divided by 6,
i.e. $7^k+4^k+1=6Z$, where Z is an integer...1
Show that n = k + 1 is true...
i.e. $7^{k+1}+4^{k+1}+1$ can be divided by 4
$7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1$ => $7(7^k+4^k)+4^k(7-4)+1$...from 1 above => $7(6Z-1)+4^k\cdot3+1$ => $42Z-7+4^k\cdot3+1$ => $42Z+4^k\cdot3-6$ => $84Z+4^k\cdot6-12$ => $6(14Z+4^k-2)$
Thus, assuming n = k, we can say n = k + 1 is true and true for n = 2, 3,... and all n $\in \mathbb{N}_0$

2. ## Re: Divisibility Proofs

The idea is correct, but there are several small flaws.

Originally Posted by GrigOrig99
Therefore, n = 1 is true...
Rather, P(1) is true where P(n) is " $7^n+4^n+1$ is divisible by 6."

Originally Posted by GrigOrig99
Show that n = k + 1 is true...
Should be: "Show that P(k + 1) is true."

Originally Posted by GrigOrig99
i.e. $7^{k+1}+4^{k+1}+1$ can be divided by 4
By 6.

Originally Posted by GrigOrig99
$7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1$ => $7(7^k+4^k)+4^k(7-4)+1$
(7 - 4) should be (4 - 7).

Originally Posted by GrigOrig99
...from 1 above => $7(6Z-1)+4^k\cdot3+1$ => $42Z-7+4^k\cdot3+1$ => $42Z+4^k\cdot3-6$ => $84Z+4^k\cdot6-12$ => $6(14Z+4^k-2)$
What exactly does => mean here? Especially, what is the relationship between $42Z+4^k\cdot3-6$ and $84Z+4^k\cdot6-12$?

Originally Posted by GrigOrig99
Thus, assuming n = k, we can say n = k + 1 is true
Assuming n = k, the fact that n = k + 1 is obviously false.

3. ## Re: Divisibility Proofs

Originally Posted by GrigOrig99
Can anyone help me confirm if I've solved this correctly?

Many thanks.

Q.
$7^n+4^n+1$ is divisible by 6 for n $\in \mathbb{N}$

Attempt: Step 1: For n = 1...
$7^1+4^1+1=12$, which can be divided by 6.
Therefore, n = 1 is true...

Step 2: For n = k...
Assume $7^k+4^k+1$ can be divided by 6,
i.e. $7^k+4^k+1=6Z$, where Z is an integer...1
Show that n = k + 1 is true...
i.e. $7^{k+1}+4^{k+1}+1$ can be divided by 4
$7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1$ => $7(7^k+4^k)+4^k(7-4)+1$...from 1 above => $7(6Z-1)+4^k\cdot3+1$ => $42Z-7+4^k\cdot3+1$ => $42Z+4^k\cdot3-6$ => $84Z+4^k\cdot6-12$ => $6(14Z+4^k-2)$
Thus, assuming n = k, we can say n = k + 1 is true and true for n = 2, 3,... and all n $\in \mathbb{N}_0$
You have a sign error.

\displaystyle \begin{align*} 7^{k + 1} + 4^{k + 1} + 1 &= 7^{k + 1} + 7 \cdot 4^k - 7 \cdot 4^k + 4^{k + 1} + 1 \\ &= 7\left(7^k + 4k\right) - 4^k\left(7 - 4\right) + 1 \\ &= 7\left(6Z - 1\right) - 3\cdot 4^k + 1 \\ &= 42Z - 7 - 3\cdot 4^k + 1 \\ &= 42Z - 3\cdot 4^k - 6 \\ &= 42Z - 3\cdot 4 \cdot 4^{k - 1} - 6 \\ &= 6\left(7Z - 2\cdot 4^{k - 1} - 1\right) \end{align*}

4. ## Re: Divisibility Proofs

Ok, thanks guys,

5. ## Re: Divisibility Proofs

Another way to do it:

$7^n \equiv 1^n \equiv 1 (\mod 6)$

$4^n \equiv 4 (\mod 6)$ (this is a little hard to prove, but checking the first few cases you will see that it always works).

Therefore, $7^n + 4^n + 1 \equiv 1 + 4 + 1 \equiv 0 (\mod 6)$, therefore it is always divisible by 6.