# Remainder when dividing by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$

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?

• I suppose that $53\in S$, otherwise you would have a 53 digits number? Try to approximate with $\log_{10}$ perhaps. – Asaf Karagila Dec 20 '14 at 14:14
• 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. – Mark Bennet Dec 20 '14 at 14:17
• @AsafKaragila Yes, thanks – Alexi Dec 20 '14 at 14:19

## 1 Answer

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