+0  
 
+1
304
7
avatar+380 

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

Best Answer 

 #3
avatar+19835 
+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}\)

 

laugh

heureka  Jan 29, 2018
edited by heureka  Jan 29, 2018
 #1
avatar
+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
avatar+19835 
+2
Best Answer

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}\)

 

laugh

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

Simple correction. heureka made a simple typo:

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

Guest Jan 29, 2018
 #5
avatar+19835 
+1

Thank you Guest

laugh

heureka  Jan 29, 2018

8 Online Users

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.