3

Show that for every $n$, there exists a number with $0$'s and $7$'s such that $n$ divides it.

My proof goes as follows:

Consider the set of integers $\{10^0, 10^1, 10^2, \cdots, 10^n\}$. It's fairly obvious by $\textbf{PHP}$ that $\exists \text { distinct } x,y ~ \ni ~ n\mid10^x-10^y$. Note that $v_3[10^{\vert x-y\vert}-1]=v_3[\vert x-y \vert]+2$. Hence, $n\mid \frac{10^x - 10^y}{9}$ only if $v_3[\vert x-y \vert]\geq v_3[n]$. Just to ensure this fact, the desired integer be $\boxed{\frac {10^{3^kx}-10^{3^kb}}{9}\times7}$

Is it correct?

Mathejunior
  • 3,344
  • How do you know there exist $10^x\equiv 10^y\mod n $? – fleablood Nov 18 '17 at 07:10
  • @fleablood When we consider the integers ${10^0, 10^1, \cdots, 10^n}$, we can have a maximum of $n+1$ distinct remainders which isn't possible. So, at least two of them must have same remainders. And that means they are congruent modulo $n$. Right? – Mathejunior Nov 18 '17 at 07:14
  • Ah, you said that in your second sentence. I misread and didn't see what you were referring to with the pigeonhole principal. – fleablood Nov 18 '17 at 07:17
  • @fleablood Yes sure :). I edited the proof-write-up. I hope it is better understood now. – Mathejunior Nov 18 '17 at 07:17

0 Answers0