Multiple consists of only 6's and 7's

  • Context:
  • Thread starter Thread starter I like Serena
  • Start date Start date
  • Tags Tags
    Multiple
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
11 replies · 3K views
I like Serena
Science Advisor
Homework Helper
MHB
Messages
16,335
Reaction score
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.
 

Discussion

Mathematics news on Phys.org
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:
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.
 
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.
 
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.
 
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
 
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
 
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
 
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.
 
I would like to have a solution from OP/Satya.
 
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$.
 
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:

Similar threads

Can a number that ends in 3 have a multiple consisting of only 1's?

  • I like Serena
  • · Replies 4 ·
  • General Math
Replies
4

Graduate Why does adding three spin-1/2 particles give only 6 eigenvectors?

  • Nikratio
  • · Replies 42 ·
  • Quantum Physics
2
Replies
42