Given is a natural number $a$ with $54$ digits, each digit equal to $0$ or $1$. Prove the remainder of $a$ when divide by $ 33\cdot 34\cdots 39 $ is larger than $100000$.
HIDE: Click to reveal hidden text (It's mean: $a \equiv r \pmod{33\cdot 34\cdots 39 }$ with $ 0<r<33\cdot 34\cdots 39 $ then prove that $r>100000$ )
The key idea is to note that $33\cdot 34\cdots 39$ is a multiple of $33 \cdot 37 \cdot 39 \cdot 21 = 10^6-1$.
Since
$$a = \overline{a_{54}a_{53}\cdots a_1}\equiv \sum_{i=1}^9 \overline{a_{6i}a_{6i-1}\cdots a_{6i-5}} \pmod{10^6-1}$$and evidently $a_{54}$ must be $1$, $a$ leaves a remainder of at least $100000$ when divided by $10^6-1$.
Therefore, $a$ leaves a remainder of at least $100000$ when divided by $33\cdot 34\cdots 39$.
The problem asks to prove that this remainder is strictly more than $100000$, so we need to show that exactly $100000$ is not possible.
Going back to the above formula, the remainder of $100000$ can only happen when $a=10^{53}$.
However, $\nu_3 (10^{53}-100000) = 3$ by LTE, so $10^{53}-100000$ is not divisible by $81$, which divides $33\cdot 34\cdots 39$.
Funny problem A lot of us got confused when we got this problem.
Problem wrote:
Let $N$ be a natural number with $54$ digits, all of which are $0$ and $1$. Suppose that the remainder of $N$ divided by $33 \cdot 34 \cdots 39$ is $r$. Prove that $r > 10^5$.
First Thoughts and Main Inspiration
My first thought when I read this problem is: Why $54$? Why $33 \cdot 32 \cdots 39$? Why $10^5$? These things seem to have nothing in common. What's so special about these numbers after all?
Immediately after thinking about the questions above. I remembered the following problem:
Problem wrote:
A calculator can square a number or add $1$ to it. It cannot add $1$ two times in a row. By several operations it transformed a number $x$ into a number $S > x^n + 1$. Prove that $S \ge x^n + x - 1$.
Okay, the main question is what's so similar about these two problems. They look totally different!
These two numbers involve a vague understanding of $N$ (in which the second problem, we have a vague understanding on the order of operation pressed.) Yet, we are asked a similar result: the bound of the size of something.
Yes, suppose that a particular integer $n$ must satisfy $n \equiv a \ (\text{mod} \ b)$, if $n > k$, then we could strengthen this to be $n \ge x$ where $x$ is the least integer greater than $k$ such that $x \equiv a \ (\text{mod} \ b)$. This is the basic usage of these type of problem. This is more involved.
Execution
Okay, this problem has actually spoiled some hint on "Modulo" part already: but it gave us mod $33 \cdot 34 \cdot 35 \cdot 36 \cdot 37 \cdot 38 \cdot 39$ instead. Why?
Here's the thing. Consider this useful fact:
\[ x \ (\text{mod} \ ab) \ge x \ (\text{mod} \ a) \]Basically, if $x = \ell a b + na + m$, where $m < a, n < b$. we have LHS being equal to $na + m$, and RHS being equal to $m$, but since $na \ (\text{mod} \ ab) \ge 0$, for obvious reasons, then the inequality is true.
Now, consider $D = 7 \cdot 11 \cdot 13 \cdot 27 \cdot 37 = 999999 = 10^6 - 1$ is a divisor of $D' = 33 \cdot 34 \cdot 35 \cdot 36 \cdot 37 \cdot 38 \cdot 39$.
Since $N$ has $54$ digits, it must begin with $10^{53}$. So, we can let $A \subseteq \{ 0, 1, 2, \dots, 52 \}$, and we can represent $N$ as
\[ N = 10^{53} + \sum_{a \in A} 10^a \]Now, we want to consider $N$ modulo $D$, in which, we have
\[ N \equiv 10^5 + \sum_{a \in A} 10^a \ (\text{mod} \ D) \]Now, we can group the elements in $A$ into $6$ subsets, according to their relations modulo $6$. Define $A_k = k \ (\text{mod} \ 6)$.
This is when $54 = 9 \times 6$ is used. You can see that having $N$ would maximal have $9$ elements each in $A_0, A_1, \dots, A_6$.
Thus, we have
\[ N \equiv 10^5 + \sum_{i =0}^5 \sum_{a_i \in A_i} 10^{a_i} \ (\text{mod} \ D) \equiv 10^5 + \sum_{i = 0}^5 10^i \cdot | A_i | \ (\text{mod } \ D)\]Now, we consider $N \ (\text{mod} \ D)$,
\[ 10^5 \le N \ (\text{mod} \ D) \le \sum_{i = 0}^5 9 \cdot 10^{i} = 999999 \]Now, we know that since $D = 999999 = 10^6 - 1$, we would be in trouble if $N \ (\text{mod} \ D) = 999999 \equiv 0 \ (\text{mod} \ D)$, this means that $D \mid N$.
However, this forces that
\[ N = \underbrace{111 \dots 1}_{54 \ \text{number of } 1's}\]But we notice that $D'$ is even, and therefore by considering $N \ (\text{mod} \ 2D)$, we will have
\[ N \ (\text{mod} \ 2D) = 999999 \]Therefore, since $2D \mid D'$, we have
\[ N \ (\text{mod} \ D') \ge N \ (\text{mod} \ 2D) \ge 999999 > 10^5 \]
Otherwise, we know that
\[ 10^5 \le N \ (\text{mod} \ D) \le 10^6 - 2 = D - 1\]Therefore, we can conclude that
\[ N \ (\text{mod} \ D') \ge N \ (\text{mod} \ D) \ge 10^5\]To check that equality cannot hold, notice that equality holds if and only if
\[ N = 10^{53} \]Now, suppose that $10^{53} \equiv 10^5 \ (\text{mod} \ D')$, this forces $D' \mid 10^5 (10^{48} - 1)$.
But luckily for us, $19$ divides $D'$. Since $\gcd(19, 10^5) = 1$, then this must forces $19 \mid 10^{48} - 1$. However, $o_{19}(10) = 18$ since $19 \mid 10^9 + 1$. Therefore, $o_{19}(10) \mid 48$, a big contradiction.