2019/011) 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.

This question I have solved at https://mathhelpboards.com/challenge-questions-puzzles-28/multiple-consists-only-6s-7s-26532.html#post116812

I am providing a structured solution for the same. (not same as in the link above)

There are 2 cases:
1) The number is odd
2) The number is even

 Now we provide solution for both cases to make the solution complete

1) The number is odd say k

The number is not ending with 5 so the number is not divisible by 5

We take numbers $a_1=1, a_2=11, a_3= 111$  so on upto a number with k 1's that is $a_k = 1111....1111$ (k times) that is $a_n$ is a number with n 1's.
Divide the k numbers by k
We have k remainder 0 and so either one remainder is zero or 2 remainder are same (as there are maximum k remainders 0 to k-1)
We assert that one of the remainders is zero.

If that is not the case then 2 remainders are same say for $a_n$ and $a_m$ with $n > m $ so $a_n-a_m = a_{n-m} * 10^m$ divided by k is zero so $a_{n-m}$ divided by k is zero which is a contradiction

so one of the remainders is zero let it be $a_m$ . which is divisible by k. multiply the number bu 6 or 7 so that all the digits are 6 or 7 and it is a multiple of k which is true

case 2: The number is even that is $k*2^n$ Where k  is odd and m is $>0$

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$

Note: there my be a smaller number satisfying the criteria with m digits (say y) may be $m < n$

So let is consider the number y with p digits ( digits are 6 or 7) which is divisible by $2^n$

Now we choose k numbers $x_1=1 $, $x_2 = 10^p + 1$,$x_3= 10^{2p}+10^p + 1$, $x_4=10^{3p} + 10^{2p} + 10^p + 1 $  so on $x_{k} = 10^{(k-1)p} + 10^{(k-2)p} \cdots + 1 $

By using same argument as in case 1 we can show that

So one of the $x$ above is divisible by k. multiplying by  y we get a number consisting of 7 and 6 which is a multiple of given number

Proved




-