Prove that there is an natural number consisting of digits 0 and 7 which is divisible by $359$

Question

How can I approach this kind of question ? I thought about Euler's totient function and gcd but i dont know if they are related to this question

Answer 1

Hint: Use the pigeonhole principle to argue that among the sequence $7,77,777,7777,\dots$, there exist (at least) two numbers that have the same remainder upon division by $359$.

Answer 2

Allowable numbers look like "$70077770777070777700$", i.e., a sum of $7*10^n$ for a handful of $n$. We could also write such a number as "$7\times10011110111010111100$". The numbers $359$ and $7$ are coprime, so $359$ will only divide $70077770777070777700$ if it divides $10011110111010111100$.

I'll assume you know a little modular arithmetic, which is quite useful for such problems. The short version is: because $10$ is coprime to $359$, the number $10$ generates the multiplicative group of integers modulo $359$. That means, in particular, that $10^m = 1$ for some $m$. So one solution is \begin{equation} 7\sum_{i=1}^{359} 10^{mi} \equiv 7\sum_{i=1}^{359} 1 \equiv 0 \pmod{359}\,. \end{equation}

Answer 3

As suggested by Peter in comments, by Fermat's little theorem,

we have that $359$ divides $10^{358}-1=\sum\limits_{n=0}^{357}9\times10^n.$

Since $359$ and $9$ are relatively prime, this means $359$ divides $\sum\limits_{n=0}^{357}10^n$ and therefore $\sum\limits_{n=0}^{357}7\times10^n,$

which is a number whose digits are all $7$.

(If a $0$ digit is required, multiply it by $10$.

Also, it happens to be that $359$ divides $10^{179}-1$.)