1
$\begingroup$

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)$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about $25,32$ etc.? $\endgroup$ – user19405892 Feb 12 '16 at 16:39
  • $\begingroup$ The highest sum on the left-hand side is 5+4+6+2+3+1. $\endgroup$ – Empy2 Feb 12 '16 at 16:40
  • $\begingroup$ Also shouldn't it be congruent to $3$ mod $7$ not $2$? $\endgroup$ – user19405892 Feb 12 '16 at 16:46
  • $\begingroup$ When you multiply by $5$, the right-hand side becomes $2*5=3\pmod7$ $\endgroup$ – Empy2 Feb 12 '16 at 16:51
  • $\begingroup$ I see. So you are really forming a one-to-one correspondence between $N$ and $M$? $\endgroup$ – user19405892 Feb 12 '16 at 17:01
0
$\begingroup$

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 \}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.