MHB Multiple consists of only 6's and 7's

[I like Serena]

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]

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.

Spoiler

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

-

 

[I like Serena]

Thank you kaliprasad for a correct solution!

Just a nitpick:

Spoiler

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.

 

[SatyaDas]

Spoiler

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]

Thank you kaliprasad for a correct solution!

Just a nitpick:

Spoiler

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.

Spoiler

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.

 

[I like Serena]

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]

I don't think the case of $C*2^n$ is covered where C is a composite number.

Spoiler

My mistake. I should have said p is odd in place of prime. corrected the same

 

[topsquark]

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

 

[I like Serena]

I'm going to sue you for deliberately trying to hurt my brain... (Sweating)

-Dan

Easily fixed. Just get your brain into gear lol.

 

[kaliprasad]

I would like to have a solution from OP/Satya.

 

[I like Serena]

Spoiler

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

 

[SatyaDas]

I would like to have a solution from OP/Satya.

Our solution is very much like yours.

Spoiler

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. :)