Multiple consists of only 6's and 7's

  • MHB
  • Thread starter I like Serena
  • Start date
  • Tags
    Multiple
In summary: We can prove that any number that does not end in 0 or 5 has a multiple that consists of only 6's and 7's by using the following method:1. Take the given number and multiply it by 2.2. If the resulting number ends in 0 or 5, multiply it again by 2.3. Repeat this process until the resulting number does not end in 0 or 5.4. The resulting number will consist of only 6's and 7's.Therefore, in summary, any number that does not end in 0 or 5 has a multiple that consists of only 6's and 7's by following the above method.
  • #1
I like Serena
Homework Helper
MHB
16,336
258
Given a number that does not end in 0 or 5, prove that it has a multiple that consists of only 6's and 7's.

For instance 12 has the multiple 7776.
 
Mathematics news on Phys.org
  • #2
Klaas van Aarsen said:
Given a number that does not end in 0 or 5, prove that it has a multiple that consists of only 6's and 7's.

For instance 12 has the multiple 7776.

The number can be represented by $p * 2^q$ where p is an odd number not divisible by 5 and q is $>=0$
if q is 0 then we need not bother
for q =1 we have 6 divisible by 2(other numbers also but we are not bothered)
for q = 2 we have 76 divisible by $2^2$
we shall prove by induction that there is a sequence of 6 and 7 (not necessarily any order that is divisible by $2^n$
Before that we prove the following
We have $10^n \equiv 2^n \pmod {2^{n+1}}\cdots(1)$
Proof:
$10^n = 5^n * 2^n = \frac{5^n-1}{2} *2^{n+1} + 2^n\equiv = 2^n \pmod {2^{n+1}} $ as $\frac{5^n-1}{2}$ is integer
Now 6 is divisible by 2 and 76 by ${2^2}$
If a number is divisible by $2^n$ then either it divisible by $2^{n+1}$ or remainder when divided by $2^{n+1}$ is $2^n$
if it is divisible by $2^{n+1}$ then add $6*10^{n+1}$ to it to make is divisible by$ 2^{n+1}$ as both terms are divisible by $2^{n+1}$
if it is not divisible by $2^{n+1}$ that is remainder is $2^n$ then add $7*10^{n+1}$ to it to make is divisible by$ 2^{n+1}$ as both terms leave a remainder $2^n$ and sum zero divisible by $2^{n+1}$
so in both cases we have a number consisting of 7 and 6 (n digits) which is divisible by $2^n$
Now coming to the original problem
if it is odd number say p ( that is there is no power of 2) it is not divisible by 5 either(given) then we can have a repunit as solved in https://mathhelpboards.com/challenge-questions-puzzles-28/multiple-consists-only-1s-26528.html#post116789
which is divisible by p . multiplying by 7 or 6 we get the number
if it is even number that is $p*2^n$ where p is odd
we have a number of n digits say m consisting of digits 7 and 6 which is divisible by $2^n$. we have proved the same above
now we choose p numbers $x_1=1 $, $x_2 = 10^n + 1$,$x_3= 10^{2n}+10^n + 1$, $x_4=10^{3n} + 10^{2n} + 10^n + 1 $ so on $x_{p-1} = 10^{p} + 10^{p-1} \cdots + 1 $
dividing by p either one of the remainders shall be 0 say $x_t$ or 2 numbers say $x_a$ and $x_b$ ( with $a > b $shall have same remainder
so $x_a-x_b$ shall be $x_{a-b} * 10^ b$ so $x_{a-b}$ is divisible by p
so one of the $x$ above is divisible by p. multiplying by m we get a number consisting of 7 and 6 which is a multiple of given number

-
 
Last edited:
  • #3
Thank you kaliprasad for a correct solution!

Just a nitpick:
kaliprasad said:
If a number is divisible by $2^n$ then either it divisible by $2^{n+1}$ or remainder when divided by $2^{n+1}$ is $2^n$
if it is divisible by $2^{n+1}$ then add $6*10^{n+1}$ to it to make is divisible by$ 2^{n+1}$ as both terms are divisible by $2^{n+1}$
if it is not divisible by $2^{n+1}$ that is remainder is $2^n$ then add $7*10^{n+1}$ to it to make is divisible by$ 2^{n+1}$ as both terms leave a remainder $2^n$ and sum zero divisible by $2^{n+1}$
so in both cases we have a number consisting of 7 and 6 (n digits) which is divisible by $2^n$

It is instrumental that it has n digits, so I think that should be mentioned beforehand rather than as an afterthought. There are smaller numbers. It's just that the proof by induction won't work on them.
 
  • #4
kaliprasad said:
if it is even number that is $p*2^n$ where p is a prime
-

I don't think the case of $C*2^n$ is covered where C is a composite number.
 
  • #5
Klaas van Aarsen said:
Thank you kaliprasad for a correct solution!

Just a nitpick:
It is instrumental that it has n digits, so I think that should be mentioned beforehand rather than as an afterthought. There are smaller numbers. It's just that the proof by induction won't work on them.

It is not. In case a smaller number satisfies the case m digit number is is divisible by $2^n$ we can take 1, $10^m+1$, $10^{2m} + 10^m +1$ so on. So n is incidental and not mandatory.
 
  • #6
For the record, Satya provided this problem and my previous challenge as well, which he remembered from an old math journal.

Satya, welcome to MHB! :D
 
  • #7
Satya said:
I don't think the case of $C*2^n$ is covered where C is a composite number.

My mistake. I should have said p is odd in place of prime. corrected the same
 
  • #8
Klaas van Aarsen said:
Given a number that does not end in 0 or 5, prove that it has a multiple that consists of only 6's and 7's.

For instance 12 has the multiple 7776.
I'm going to sue you for deliberately trying to hurt my brain... (Sweating)

-Dan
 
  • #9
topsquark said:
I'm going to sue you for deliberately trying to hurt my brain... (Sweating)

-Dan

Easily fixed. Just get your brain into gear lol.
 
  • #10
I would like to have a solution from OP/Satya.
 
  • #11
Let $N_k$ be a k-digit number that consists only of 6's and 7's, and that is divisible by $2^k$.

Lemma. $N_k$ exists for every $k\ge 1$.
Proof by induction
$N_1=6$ satisfies the condition.
Suppose $N_k$ exists implying that $2^k$ divides $N_k$. Then $N_k \bmod 2^{k+1}$ is either $0$ of $2^k$.
Let
$$N_{k+1}=\begin{cases}6\cdot 10^k + N_k&\text{if } N_k\bmod 2^{k+1}=0\\
7\cdot 10^k + N_k&\text{if } N_k\bmod 2^{k+1}=2^k
\end{cases}$$
Then $N_{k+1}$ consists of only 6's and 7's.
We have that $2^{k+1}$ divides $6\cdot 10^k$.
We also have that $7\cdot 10^k \bmod 2^k =0$. And since $7$ is odd, we must have that $7\cdot 10^k \bmod 2^{k+1} =2^k$.
Therefore $N_{k+1}$ is divisible by $2^{k+1}$.
QED

The actual number can be written as $2^k m$ where $m$ is co-prime with $10$.
Take the $N_k$ from before and additionally define $N_0=6$ (which is divisible by $2^0=1$).
Let $M_n$ be the number formed by repeating $N_k$ $n$ times.
Then $M_n$ is divisible by $2^k$ because $N_k$ is.
If we look at the first $m+1$ numbers $M_n$, by the pigeon hole principle, there must be at least 2 of them with the same remainder modulo $m$, since there are only $m$ different remainders possible.
The difference of those 2 numbers begins with only 6's and 7's, and ends with only 0's.
That is, it is one of the $M_n$ followed by 0's.
So for some $n$ and $\ell$ we have that $M_n \cdot 10^\ell$ has remainder $0$ modulo $m$.
Since $m$ is co-prime with $10^\ell$, we must have that $M_n$ is divisible by $m$.
So this $M_n$ is divisible by both $2^k$ and $m$.
Therefore $M_n$ is a number that consists of only 6's and 7's, and it is divisible by the actual number $2^k m$.
 
  • #12
kaliprasad said:
I would like to have a solution from OP/Satya.

Our solution is very much like yours.
We divided the numbers into 3 categories:
(1) Odd numbers. Use Pigeon hole theorem to prove every such numbers have a multiple that contains only $7$s.
(2) Numbers of the form $2^n$. Use induction. Exactly as yours.
(3) Numbers of the form $C*2^n$. Where $C$ is coprime with $2$ and $5$. From (2) we do know that $2^n$ has such a multiple. Let's say it is $m$. Then prove that at least one of the number from $m$, $mm$, $mmm$, ... $m$ (repeated $C*2^n+1$ times) is multiple of $C*2^n$. This too can be proved using pigeon hole theorem.

These $3$ cases cover all numbers that are not multiple of $5$.

Hence proved. :)
 
Last edited:

FAQ: Multiple consists of only 6's and 7's

What is a "Multiple consists of only 6's and 7's"?

A "Multiple consists of only 6's and 7's" is a number that is divisible by both 6 and 7, and only contains the digits 6 and 7 in its decimal representation.

How do you find the first few "Multiple consists of only 6's and 7's"?

The first few "Multiple consists of only 6's and 7's" are 42, 66, 72, 77, 84, 126, 132, 136, 144, and so on. They can be found by multiplying 6 and 7 together, and then adding or subtracting multiples of 6 and 7.

Are there infinitely many "Multiple consists of only 6's and 7's"?

Yes, there are infinitely many "Multiple consists of only 6's and 7's". This is because the numbers 6 and 7 are relatively prime, meaning they do not share any common factors other than 1. Therefore, their multiples will never repeat in a predictable pattern.

Can any number be a "Multiple consists of only 6's and 7's"?

No, not every number can be a "Multiple consists of only 6's and 7's". For a number to be a multiple of 6 and 7, it must be divisible by both 6 and 7. Therefore, numbers that are not divisible by both 6 and 7 cannot be "Multiple consists of only 6's and 7's".

What is the largest known "Multiple consists of only 6's and 7's"?

The largest known "Multiple consists of only 6's and 7's" is 446,744,073,709,551,616, which is equal to 7^15 * 6^15. This number was found in 2016 by a team of mathematicians using a distributed computing project called GIMPS (Great Internet Mersenne Prime Search).

Similar threads

Replies
6
Views
2K
Replies
2
Views
993
Replies
1
Views
10K
Replies
3
Views
809
Replies
4
Views
1K
Replies
3
Views
3K
Replies
12
Views
2K
Replies
1
Views
833
Back
Top