System of congruences with variable

Question

I am looking over 2013 AMC 10B Problem 25, and I came across a solution containing this:

Problem Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer $S$. For example, if $N = 749$, Bernardo writes the numbers $10,\!444$ and $3,\!245$, and LeRoy obtains the sum $S = 13,\!689$. For how many choices of $N$ are the two rightmost digits of $S$, in order, the same as those of $2N$?

$\textbf{(A)}\ 5 \qquad\textbf{(B)}\ 10 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 20 \qquad\textbf{(E)}\ 25$

Solution 1 First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities.

Say that $N \equiv a \pmod{6}$

also that $N \equiv b \pmod{5}$

Substituting these equations into the question and setting the units digits of $2N$ and $S$ equal to each other, it can be seen that $b < 5$ (because otherwise $a$ and $b$ will have different parities), and thus $a=b$. $N \equiv a \pmod{6}$, $N \equiv a \pmod{5}$, $\implies N=a \pmod{30}$, $0 \le a \le 4$

Therefore, $N$ can be written as $30x+y$ and $2N$ can be written as $60x+2y$

Just keep in mind that $y$ can be one of five choices: $0, 1, 2, 3,$ or $4$, ; Also, we have already found which digits of $y$ will add up into the units digits of $2N$.

Now, examine the tens digit, $x$ by using $\mod{25}$ and $\mod{36}$ to find the tens digit (units digits can be disregarded because $y=0,1,2,3,4$ will always work) Then we take $N=30x+y$ $\mod{25}$ and $\mod{36}$ to find the last two digits in the base $5$ and $6$ representation.[N \equiv 30x \pmod{36}][N \equiv 30x \equiv 5x \pmod{25}]Both of those must add up to[2N\equiv60x \pmod{100}]

$N\equiv{30x\mod{36}}\\N\equiv{30x}\equiv{5x\mod{25}}$

Both of these must add up to

$2N\equiv{60x\mod{100}}$
[...]

I'm not really sure which modular arithmetic rule to apply in the final three congruences, or where to start. How would I go about understand this?

Answer 1

You do not necessarily use modular arithmetic rules to reason such results, because this is sometimes hard. In fact, you can use the definition of modular relation directly: $36|(N-30x)$ and $25|(N-30x)$ lead to $100|(N-30x)$, so $$N\equiv{30x\mod{100}}.$$

Answer 2

You could invoke the Chinese remainder theorem:

$\text{given: }N\equiv30x\bmod36\implies N\equiv2x\bmod4\tag1$

$\text{given: }N\equiv5x\bmod 25\tag2$

$25\times(1)\implies25N\equiv50x\mod100 \tag3$

$4\times(2)\implies4N\equiv20x\bmod100\tag4$

$\text{Bezout: }25-6\times4=1\tag5$

$6\times(4)\implies24N\equiv20x\bmod100\tag6$

$(3)-(6)\implies N\equiv30x\bmod100\tag7$

$2\times(7)\implies2N\equiv60x\bmod100.\tag8$

In short, $N\equiv 2x\times25-5x\times4\times6\equiv30x\bmod100,$ so $2N\equiv60x\bmod100$.

Answer 3

In this problem it follows immediately from the hypotheses. Namely at that point they have $n = 30x+y\,$ so $\,2n = 60x+y,\,$ where $\, 0\le y\le 4,\,$ so, by hypothesis, adding the tens digits from radix $\,5\,$ & $\,6\,$ must yield the tens digits of $\,2n\,$ in radix $10$, which is exactly the cited "must add up to" claim. We can also directly verify this claim using modular arithmetic as below.

---

Notice $\ 5^2,6^2\mid 30x\!-\!n\iff \overbrace{{\rm lcm}(5^2,6^2)}^{\textstyle \!\!\!30^2\! = 5^2\cdot 6^2}\mid 30x\!-\!n,\ $ by the LCM Universal property.

Or, equivalently, we can apply CCRT = Constant case of CRT

$$ 30x\equiv n\!\!\!\pmod{\!5^2\ \&\ 6^2}\iff 30x\equiv n\!\!\!\pmod{5^2\cdot 6^2}\qquad$$

And, of course, $\ 10^2\mid 30^2\mid x\,\Rightarrow\, 10^2\mid x\ $ by transitivity of "divides" (or, equivalently,since congruences persist mod factors of the modulus).

Hence $\bmod 10^2\!:\,\ 30x\equiv n\,\overset{\large \times\ 2}\Longrightarrow\, 60x\equiv 2n\ $ by the Congruence Product Rule.