Welcome to our community

Be a part of something great, join today!

Multiple consists of only 6's and 7's

  • Thread starter
  • Admin
  • #1

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713
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.
 

kaliprasad

Well-known member
Mar 31, 2013
1,283
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/challeng...ltiple-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:
  • Thread starter
  • Admin
  • #3

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713
Thank you kaliprasad for a correct solution!

Just a nitpick:
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.
 

Satya

New member
Sep 13, 2019
11
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.
 

kaliprasad

Well-known member
Mar 31, 2013
1,283
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.
 
  • Thread starter
  • Admin
  • #6

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713
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
 

kaliprasad

Well-known member
Mar 31, 2013
1,283
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
 

topsquark

Well-known member
MHB Math Helper
Aug 30, 2012
1,120
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
 
  • Thread starter
  • Admin
  • #9

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713

kaliprasad

Well-known member
Mar 31, 2013
1,283
I would like to have a solution from OP/Satya.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713
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$.
 

Satya

New member
Sep 13, 2019
11
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: