+0

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

0
83
7
+300

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?

RektTheNoob  Jan 29, 2018

#3
+18956
+2

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

heureka  Jan 29, 2018
edited by heureka  Jan 29, 2018
Sort:

#1
+1

[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 !!!!

Guest Jan 29, 2018
edited by Guest  Jan 29, 2018
#3
+18956
+2

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

heureka  Jan 29, 2018
edited by heureka  Jan 29, 2018
#4
+1

Simple correction. heureka made a simple typo:

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

Guest Jan 29, 2018
#5
+18956
+1

Thank you Guest

heureka  Jan 29, 2018

### 21 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details