8
$\begingroup$

Given a $54$-digit number consisting of only ones and zeros. Prove that the remainder when dividing this number by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$.

The number can be written as $\sum_{i\in S} 10^i$ where $S\subseteq\{0,1,2,\ldots,53\}$ and $53\in S$. The number $33\cdot 34\cdot\ldots\cdot 39$ is equal to $77519922480$. How might it be possible to determine the remainder when dividing $10^i$ by this number?

$\endgroup$
  • $\begingroup$ I suppose that $53\in S$, otherwise you would have a 53 digits number? Try to approximate with $\log_{10}$ perhaps. $\endgroup$ – Asaf Karagila Dec 20 '14 at 14:14
  • $\begingroup$ The prime factors here are interesting - $2,3,5,7,11,13, 17,19,37$. Note that the largest prime factor $37$ is a factor of $999$, for example. $\endgroup$ – Mark Bennet Dec 20 '14 at 14:17
  • $\begingroup$ @AsafKaragila Yes, thanks $\endgroup$ – Alexi Dec 20 '14 at 14:19
2
$\begingroup$

Since $7\cdot11\cdot13=1001$ and $3^3\cdot37=999$, we have

$$d=33\cdot34\cdot35\cdot36\cdot37\cdot38\cdot39=2^4\cdot3\cdot5\cdot17\cdot19\cdot999\cdot1001=77520\cdot999999\;.$$

Let $n$ be a $54$-digit number. Divide $n$ into nine $6$-digit chunks, $n_0,\ldots,n_8$ from right to left. Think of each chunk as a digit base $10^6$: then

$$n=\sum_{k=0}^810^{6k}n_k\;.$$

Let $m=\sum_{k=0}^8n_k$; $n\ge 10^{53}$, so $n_8\ge 100000$, and $100000\le m\le 999999$. Moreover, it’s not hard to show that $n\equiv m\pmod{999999}$. (This is just the test for divisibility by $9$ kicked up from base ten to base one million.)

Let $n=dq+r$, where $0\le r<d$. Then $n=999999(77520q)+r$, so $r\equiv n\equiv m\pmod{999999}$, and it follows immediately that $r\ge 100000$.

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