Find all $7$-digit numbers which use only the digits $5$ and $7$ and are divisible by $35$

Question

Find all $7$-digit numbers which use only the digits $5$ and $7$ and are divisible by $35$.

Attempt

It is easy to see that all numbers of this form must be of the form _ _ _ _ _ _ 5. Working with the divisible by $35$ condition seems a little hard so since we immediately know it is divisible by $5$ we just have to work on divisibility by $7$. I would use the divisibility test then for the rest of the digits $\overline{abcdef}$. We must have that $\overline{abcdef}-10$ is divisible by $7$. This is equivalent to testing divisibility by $7$ for $100000a+10000b+1000c+100d+10e+f-10$. Taking this all mod $7$ we get $2a+4b+c+2d+3e+f \equiv 3 \mod 7.$ Now how do I find all such pairs $(a,b,c,d,e,f)$?

Answer 1

Let $M$ be the number where you replace the $7$s by $0$s, and the $5$s by $1$s. Then $N=5M+70k$ for some number $k$. The equation becomes $5a+4b+6c+2d+3d+f=2\pmod7$ with all digits $0$ or $1$. In other words, subsets of the numbers $1,2,3,4,5,6$ that sum to $2,9$ or $16$.

Answer 2

Hint By Fermat Little Theorem $$555555=5 \cdot \frac{10^6-1}9$$

Is divisible by $7$.

Therefore $$5555555 \equiv 5 \pmod{7}$$

Now your numbers are of this form plus twice sums of powers of 10. You have $$2 \cdot 10 \equiv -1 \pmod{7} \\ 2 \cdot 10^2 \equiv 3 \pmod{7} \\ 2 \cdot 10^3 \equiv 2 \pmod{7} \\ 2 \cdot 10^4 \equiv -1 \pmod{7} \\ 2 \cdot 10^5 \equiv 3 \pmod{7} \\ 2 \cdot 10^6 \equiv 2 \pmod{7} $$

and you have to figure out which numbers from this set you need to add to get $2 \pmod{7}$. You can reduce the problem to solving $$-a+3b+2c \equiv 2 \pmod{7}$$ where $$a,b,c \in \{0 ,1, 2 \}$$