# Prove a number is divisible by a number?

• MHB
• TinaSprout
In summary, the problem is to prove that 6 is divisible by 7n-6. The approach used is correct, but there are a couple of mistakes made.
TinaSprout
I am attempting to solve the problem to prove 6 is divisible by 7n-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 71-1 True! We can continue

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

6 | 7k+1 -1
6 | 7 * 7k -1
6 | 7 * 6m + 1 - 1 (substitute 7k 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!

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

Hey Tina! ;)

It's just that I see a couple of mistakes in there.

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

TinaSprout said:
Proof by induction:
Base case 6 is divisible by 71-1 True! We can continue

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

6 | 7k+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 '7k+1 -1' and try to rewrite this expression such that is becomes obvious that it's divisible by 6.

TinaSprout said:
6 | 7 * 7k -1
6 | 7 * 6m + 1 - 1 (substitute 7k for 6m+1)

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

TinaSprout said:
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 7n-1.

Another approach would be to use the binomial theorem:

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

MarkFL said:
Another approach would be to use the binomial theorem:

$$\displaystyle 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):

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

I like Serena said:
$$\displaystyle 7^n - 1 \equiv 1^n -1 \equiv 0 \pmod 6$$

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

greg1313 said:
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:

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

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

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

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

$$\displaystyle 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.

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

greg1313 said:
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. ;))

## 1. How do I prove that a number is divisible by another number?

To prove that a number is divisible by another number, you can use the division algorithm or long division method. Divide the first number by the second number and if there is no remainder, then the first number is divisible by the second number.

## 2. Can I use the remainder when dividing to prove divisibility?

Yes, the remainder when dividing two numbers can be used to prove divisibility. If the remainder is 0, then the first number is divisible by the second number.

## 3. What is the divisibility rule for numbers ending in 0 and 5?

A number is divisible by 10 if it ends in 0. A number is divisible by 5 if the last digit is either 0 or 5.

## 4. How do I prove that a number is divisible by 3?

A number is divisible by 3 if the sum of its digits is also divisible by 3. You can use this rule to prove divisibility by 3 for any number.

## 5. Is there a shortcut for proving divisibility by 2?

Yes, a number is divisible by 2 if its last digit is even. This can also be extended to larger numbers, where a number is divisible by 2 if its last digit is divisible by 2.

• General Math
Replies
7
Views
3K
• General Math
Replies
5
Views
2K
• Precalculus Mathematics Homework Help
Replies
17
Views
1K
• General Math
Replies
2
Views
2K
• General Math
Replies
55
Views
4K
• General Math
Replies
17
Views
2K
• General Math
Replies
22
Views
3K
• General Math
Replies
11
Views
5K
• General Math
Replies
2
Views
1K
• General Math
Replies
2
Views
1K