+0  
 
+1
201
1
avatar

What is the smallest positive integer that will satisfy the following two modular equations: N mod 3,331 =1,851 and N mod 1,851 =1,468?
Thank you for help.

Guest Oct 19, 2017
 #1
avatar+19597 
+1

What is the smallest positive integer that will satisfy the following two modular equations:

N mod 3,331 =1,851 and

N mod 1,851 =1,468?

 

\(\begin{array}{|rcll|} \hline N &\equiv& 1851 \pmod{3331} \\ N &\equiv& 1468 \pmod{1851} \\ \hline \end{array}\)

 

Formula:

\(\begin{array}{rcll} N = 1851\cdot 1851\cdot \frac{1}{1851} \pmod{3331} + 1468\cdot 3331 \cdot \frac{1}{3331} \pmod{1851} + 3331\cdot 1851\cdot z \\ \quad z \in Z \\ \end{array}\)

 

check:

\(\begin{array}{|rcll|} \hline \pmod{3331}: & N = 1851 \cdot \frac{1851}{1851} + 0 +0 = 1851 \ \checkmark \\ \pmod{1851}: & N = 0 + 1468 \cdot \frac{3331}{3331} + 0 = 1468 \ \checkmark \\ \hline \end{array}\)

 

\(\text{with }\varphi() =\text{ Euler's totient theorem }: \\ 3331 \text{ prime number} \qquad \varphi(p) = p-1 \qquad \varphi(3331) = 3330 \\ 1851 =3\cdot 617\qquad \varphi(1851) =1851\cdot \left(1-\frac13\right)\left(1-\frac{1}{617}\right) = 1232 \)

 

Modular inverses:

\(\begin{array}{|rcll|} \hline && \frac{1}{1851} \pmod{3331} \\ &\equiv& 1851^{\varphi(3331)-1} \pmod{3331} \quad & | \quad gcd(3331,1851)=1 \\ &\equiv& 1851^{3330-1} \pmod{3331} \\ &\equiv& 1851^{3329} \pmod{3331} \\ && \ldots \\ &\equiv& 835 \pmod{3331} \\ \hline \end{array}\)

 

\(\begin{array}{|rcll|} \hline && \frac{1}{3331} \pmod{1851} \\ &\equiv& 3331^{\varphi(1851)-1} \pmod{1851} \quad & | \quad gcd(3331,1851)=1 \\ &\equiv& 3331^{1232-1} \pmod{1851} \\ &\equiv& 3331^{1231} \pmod{1851} \\ && \ldots \\ &\equiv& 1387 \pmod{1851} \\ \hline \end{array}\)

 

\(\begin{array}{rcll} N &=& 1851\cdot 1851\cdot 835 + 1468 \cdot 3331 \cdot 1387 + 3331\cdot 1851\cdot z \quad & | \quad z \in Z \\ &=& 2860877835 + 6782302396 + 6165681\cdot z \\ &=& \underbrace{9643180231}_{\equiv 55147 \pmod{6165681}} + 6165681\cdot z \\ &=& 55147 + 6165681\cdot z \\ \end{array} \)

 

\(\begin{array}{|rcll|} \hline \mathbf{55147} &\mathbf{\equiv}& \mathbf{1851 \pmod{3331}} \\ \mathbf{55147} &\mathbf{\equiv}& \mathbf{1468 \pmod{1851}} \\ \hline \end{array}\)

 

laugh

heureka  Oct 20, 2017
edited by heureka  Oct 20, 2017

4 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.