2

Prove that: $$\forall n \in \mathbb{N}, \ 6\mid 7^n - 1$$

My Attempt:

I first let $n = 1$. $$6\mid 7^1 - 1$$ $$\implies 6\mid 6 \ \ \ \color{green}{\checkmark}$$ Now I let $n = 2$. $$6\mid 7^2 - 1$$ $$\implies 6\mid 48 \ \ \ \color{green}{\checkmark}$$ And now I let $n = 3$. $$6\mid 7^3 - 1$$ $$\implies 6\mid 342 \ \ \ \color{green}{\checkmark}$$ So now I try and find a pattern by dividing the $RHS$ by the $LHS$. $$6/6 = 1$$ $$48/6 = 8$$ $$342/6 = 57$$ There is a pattern on the $RHS$, where if you start from $1$, you multiply by $7$ and then add $1$. According to the pattern, this implies that $7^4 - 1 = 2400$ and thus $6\mid 2400$ which is true.

And it also seems that

$$8\mid \bigg(\frac{7^n - 1}{6} + \frac{7^{n + 1} - 1}{6} - 1\bigg)$$

So now I have run into another problem and don't know how to prove this. Could somebody please help me? Surely there must be some special way of proving things like these, right? Hopefully it isn't too ugly to prove. I came up with this question by figuring it out, and I do believe that it is correct because it seems like it. I have tested for $n$ up to $100$ and it still looks true. Why is this?

Thank you in advance.

Mr Pie
  • 9,459

4 Answers4

1

$$7^n-1 = (6+1)^n-1= \sum_{i=0}^n \binom{n}{i} 6^i-1= 6 \sum_{i=1}^{n} \binom{n}{i} 6^{i-1} +1-1 \equiv 1-1 \equiv 0 \pmod{6}$$

For the second part, it would be sufficient to prove that $16 \mid 7^n-1+7^{n+1}-1-6$

$$1+7^{n+1}-1-6=7^n(7+1)-8 = 8(7^n-1)$$

Since $7^n-1$ is even, $\exists k \in \mathbb{Z} : 2k=(7^n-1)$. Then,

$$1+7^{n+1}-1-6=8(7^n-1)= 16k \equiv 0 \pmod{16}$$

Which makes your conjecture true.

Sofía Marlasca Aparicio
  • 3,238
  • I am sorry. I don't understand what the big brackets are (with $n$ and $i$). Could you please explain? – Mr Pie Sep 23 '17 at 23:50
  • I used Newton's binomial. However, there is a simpler explanation. If we are mod 6, we can say $7=1$ because they give the same remainder when dividing by 6. So $7^n-1 \equiv 1^n-1 \pmod{6}$. @user477343 – Sofía Marlasca Aparicio Sep 23 '17 at 23:52
  • Ok. I did a little bit of research. $\text{mod}$ means "modulo" and finds the reminder a number after some division. Ok I'm getting the hang of it. Thank you. – Mr Pie Sep 24 '17 at 00:00
1

This can be proved with induction. First, show that it holds for $n=0$. Then, suppose it holds for some $n=k \in \mathbb N$ and show that if so, it must hold for $k+1$.

We have $7^0-1=0$, and $6\ |\ 0$. Now, suppose $6\ | 7^k-1$ and given that, prove $6\ |\ 7^{k+1}-1$.

Douglas Molin
  • 1,270
1

The simplest remains using congruences.

  • $6\mid 7^n-1\iff 7^n\equiv 1\mod 6$.

This is obvious since $7\equiv 1\mod 6$, hence $7^n\equiv 1^n=1\mod 6$.

  • Similarly, we have to prove $\;\dfrac{7^n-1}6+\dfrac{7^{n+1}-1}6\equiv 1\mod8$.

Now, $\begin{aligned}\dfrac{7^n-1}6&=\dfrac{7^n-1}{7-1}=7^{n-1}+7^{n-2}+\dots+7+1\\&\equiv (-1)^{n-1}+(-1)^{n-2}+\dots-1+1\equiv\begin{cases}0&\text{if }n\;\text{is even,}\\1&\text{if }n\;\text{is odd.}\end{cases}\end{aligned}$

Thus exactly one of $\;\dfrac{7^n-1}6$ and $\;\dfrac{7^{n+1}-1}6$ is congruent to $1$ mod. $8$, the other is congruent to $0$. The result follows.

Bernard
  • 175,478
1

$$►7^n=(6+1)^n=6M+1\Rightarrow7^n-1=6M$$

$$►►\big(\frac{7^n - 1}{6} + \frac{7^{n + 1} - 1}{6} - 1\big)=\frac{7^n(1+7)-2}{6}-1=\frac{7^n\cdot8-8}{6}=8\left(\frac{7^n-1}{6}\right)=8M$$

Piquito
  • 29,594