Processing math: 100%
 
+0  
 
0
712
1
avatar+174 

What is the smallest integer n, greater than 1, such thatn1(mod130)  and n1(mod231) are both defined?

 Jul 16, 2020
 #1
avatar+26396 
+2

What is the smallest integer n, greater than 1, such that n1(mod130) and n1(mod231) are both defined?

 

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

 

factor 130=2513factor 231=3711

 


The first prim number = 2. This number is a prime factor in 130, so gcd(130,2)1
The 2nd prim number = 3. This number is a prime factor in 231, so gcd(231,3)1
The 3rd prim number = 5. This number is a prime factor in 130, so gcd(130,5)1
The 4th prim number = 7. This number is a prime factor in 231, so gcd(231,7)1
The 5th prim number = 11. This number is a prime factor in 231, so gcd(231,11)1
The 6th prim number = 13. This number is a prime factor in 130, so gcd(130,13)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:

171(mod130)2317231(mod130) 171(mod231)6817681(mod231) 

 

laugh

 Jul 17, 2020

3 Online Users