+0  
 
0
90
1
avatar+172 

What is the smallest integer n, greater than 1, such that\(n^{-1}\pmod{130} \)  and \(n^{-1}\pmod{231}\) are both defined?

 Jul 16, 2020
 #1
avatar+25555 
+2

What is the smallest integer n, greater than 1, such that \(n^{-1}\pmod{130}\) and \(n^{-1}\pmod{231}\) are both defined?

 

Modular multiplicative inverse is defined if \(\gcd(130,n)=\gcd(231,n)=1\)

 

\(\begin{array}{|rcll|} \hline \text{factor}~ 130 &=& 2*5*13 \\ \text{factor}~ 231 &=& 3*7*11 \\ \hline \end{array}\)

 


The first prim number = 2. This number is a prime factor in 130, so \(\gcd(130,2) \ne 1\)
The 2nd prim number = 3. This number is a prime factor in 231, so \(\gcd(231,3) \ne 1\)
The 3rd prim number = 5. This number is a prime factor in 130, so \(\gcd(130,5) \ne 1\)
The 4th prim number = 7. This number is a prime factor in 231, so \(\gcd(231,7) \ne 1\)
The 5th prim number = 11. This number is a prime factor in 231, so \(\gcd(231,11) \ne 1 \)
The 6th prim number = 13. This number is a prime factor in 130, so \(\gcd(130,13) \ne 1\)
The 7th prim number = 17. This number is not a prime factor in 130 and not a prime factor in 231
, \(\gcd(130,17) = \gcd(213,17) = 1\)

 

The smallest integer n is 17

 

check:

\(\begin{array}{|rcll|} \hline 17^{-1} \pmod{130} &\equiv& 23 \\ 17*23 & \equiv& 1 \pmod{130}~ \checkmark \\\\ 17^{-1} \pmod{231} &\equiv& 68 \\ 17*68 & \equiv& 1 \pmod{231}~ \checkmark \\ \hline \end{array}\)

 

laugh

 Jul 17, 2020

39 Online Users

avatar
avatar