+490 That is the smallest positive integer N for which \((12{,}500{,}000)\cdot n\) leaves a remainder of 111 when divided by 999,999,999?
+26393 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 !!!!
+26393 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}\)
