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

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

[12500000*n] mod 999999999 =111, solve for n

One obvious N =999,999,999 + 111 =1,000,000,110 because:

1,000,000,110 mod 999,999,999 =111      !!!, But:

n = 1,000,000,110 / 12,500,00

n =80.0000088, which is non-integer, but when multiplied by 12,500,00 you get:

N =1,000,000,110 which is an integer !!!! I don't think your teacher will buy this !!!!.

Now, onward to another rediculous answer !!!

If we wish to have both N and n whole integers, will try this:

n =111 x [999,999,999 / 111 + 1,000,000,000 / 12,500,000]

n = 111 x [9,009,009 + 80]

n =1,000,008,879, which is a whole integer!!!!. And...........

N =1,000,008,879 x 12,500,000

N =12,500,110,987,500,000, which is a whole integer !!!!! And.......

12,500,110,987,500,000 mod 999,999,999 =111    !!!!

Melody and CPhill : Take a whack at this one !!!!

Simple correction. heureka made a simple typo:

80 x 111 =8,880. The smallest integer.