MHB Prove a number is divisible by a number?

[TinaSprout]

I am attempting to solve the problem to prove 6 is divisible by 7ⁿ-6 Is my logic all correct If it is, i can use it on similar problems!

Proof by induction:
Base case 6 is divisible by 7¹-1 True! We can continue

Step 2: Assume n=k is true, prove k+1 is true.
Since n=k is true, 6m = 7^k-1
therefore, 7^k = 6m+1

6 | 7^k+1 -1
6 | 7 * 7^k -1
6 | 7 * 6m + 1 - 1 (substitute 7^k for 6m+1)
6 | 6m * 7
Any multiple of 6 must be divisible by 6.

I feel like I am mistaken somewhere, so feel free to correct me if I'm going on the wrong direction,
Thank You!

 

[I like Serena]

I am attempting to solve the problem to prove 6 is divisible by 7ⁿ-6 Is my logic all correct If it is, i can use it on similar problems!

Hey Tina! ;)

Your general approach is correct.
It's just that I see a couple of mistakes in there.

For starters, isn't it '6 divides 7ⁿ-1' that you want to prove instead of '6 is divisible by 7ⁿ-6'?

Proof by induction:
Base case 6 is divisible by 7¹-1 True! We can continue

Step 2: Assume n=k is true, prove k+1 is true.
Since n=k is true, 6m = 7^k-1
therefore, 7^k = 6m+1

6 | 7^k+1 -1

This is what we want to prove, so we cannot write it as if we already know it's true.
Instead we should write '7^k+1 -1' and try to rewrite this expression such that is becomes obvious that it's divisible by 6.

6 | 7 * 7^k -1
6 | 7 * 6m + 1 - 1 (substitute 7^k for 6m+1)

I'm missing a couple of parentheses here when doing the substitution.
Shouldn't it be 7 * (6m + 1) - 1? (Wondering)

6 | 6m * 7
Any multiple of 6 must be divisible by 6.

I feel like I am mistaken somewhere, so feel free to correct me if I'm going on the wrong direction,
Thank You!

What we should have is:
$$7^{k+1} -1 = 7 \cdot 7^k -1 = 7 \cdot (6m + 1) - 1 = 7\cdot 6m + 6 = 6(7m + 1)$$
Since this is divisible by 6, it completes the induction step.

Therefore 6 divides 7ⁿ-1.

 

[MarkFL]

Another approach would be to use the binomial theorem:

$$7^n-1=(6+1)^n-1=6\sum_{k=1}^{n}\left({n \choose k}6^{k-1}\right)$$

 

[I like Serena]

Another approach would be to use the binomial theorem:

$$7^n-1=(6+1)^n-1=6\sum_{k=1}^{n}\left({n \choose k}6^{k-1}\right)$$

Ah, but we can also calculate modulo 6 (which admittedly relies on the binomial theorem):

$$7^n - 1 \equiv 1^n -1 \equiv 0 \pmod 6$$

 

[Greg]

$$7^n - 1 \equiv 1^n -1 \equiv 0 \pmod 6$$

Hi I like Serena. Could you give a detailed explanation?

 

[I like Serena]

Hi I like Serena. Could you give a detailed explanation?

It's part of Modular Arithmetic.

We write $a\equiv b \pmod n$ if there is some integer $k$ such that $a=b+kn$.
That is, $a$ and $b$ are the same except possibly for a multiple of $n$.

This equivalency has a number of properties.
The most notable ones are:

$$a \equiv 0 \pmod n \quad\Leftrightarrow\quad n \mid a \qquad \text{(that is, }n\text{ divides }a\text{)}$$

$$a + b \equiv (a \bmod n) + (b \bmod n) \pmod n$$

$$a \cdot b \equiv (a \bmod n) \cdot (b \bmod n) \pmod n$$

$$a^m \equiv (a \bmod n)^m \pmod n$$

$$a^m \equiv a^{m \bmod \phi(n)} \pmod n\quad$$ if $\gcd(a,n)=1$ and where $\phi(n)$ is Euler's totient function.There are more advanced theorems like the Chinese Remainder Theorem and the Quadratic Residue with the corresponding Legendre symbol $\left(\frac ap\right)$.
But those are quite a bit harder to grasp.

 

[Greg]

Ah, so in general $(x^k-1)\equiv0\pmod{x-1}$.

 

[I like Serena]

Ah, so in general $(x^k-1)\equiv0\pmod{x-1}$.

Yep! (Nod)

(And I guess you've noticed that $\LaTeX$ is chockful with support for modulo operations like \pmod and \bmod. ;))