+0

Modular Math

+1
305
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?
Thank you for help.

Oct 19, 2017

#1
+21191
+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}$$

Oct 20, 2017
edited by heureka  Oct 20, 2017