What is the smallest positive integer N for which
\((12{,}500{,}000)\cdot n\)
leaves a remainder of 111 when divided by 999,999,999?
1.
\(\begin{array}{|rcll|} \hline (12~500~000)\cdot n & \equiv & 111 \pmod{999~999~999} \quad & | \quad :(12~500~000) \\ n & \equiv & 111\cdot \dfrac{1}{12~500~000} \pmod{999~999~999} \\ \hline \end{array}\)
\(\begin{array}{|lcll|} \hline \text{According to Euler's theorem,} \\ \text{if $a$ is coprime to $m$, that is, $gcd(a, m) = 1$, then }\\ {\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}\\ \text{where ${\displaystyle \phi } $ is Euler's totient function.}\\ \text{Therefore, a modular multiplicative inverse can be found directly:} \\ {\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.} \\ \hline \end{array}\)
2.
\(\text{greatest common divisor $gcd(12~500~000,999~999~999) = 1$ }\)
\(\begin{array}{|rcll|} \hline && \dfrac{1}{12~500~000} \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{12~500~000^{-1} \pmod{999~999~999}} \\\\ & \equiv & 12~500~000^{\phi (999~999~999)-1} \pmod{999~999~999} \\\\ & \equiv & 12~500~000^{648~646~704-1} \pmod{999~999~999} \\\\ & \equiv & 12~500~000^{648~646~703} \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{80 \pmod{999~999~999}} \\ \hline \end{array}\)
3. n = ?
\(\begin{array}{|rcll|} \hline n & \equiv & 111\cdot \dfrac{1}{12~500~000} \pmod{999~999~999} \\\\ & \equiv & 111\cdot \left( 12~500~000^{-1} \pmod{999~999~999} \right) \\\\ & \equiv & 111\cdot 80 \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{ 8880 \pmod{999~999~999} } \\ \hline \end{array}\)
The smallest positive integer n is 8880.
\(\begin{array}{rcll} 12 ~500~000 \cdot 8880 &\equiv & 111 \pmod{999~999~999} \\ 110~000~000~000 &\equiv & 111 \pmod{999~999~999}\ \checkmark\\ \end{array}\)