What is the smallest integer n, greater than 1, such thatn−1(mod130) and n−1(mod231) are both defined?
What is the smallest integer n, greater than 1, such that n−1(mod130) and n−1(mod231) are both defined?
Modular multiplicative inverse is defined if gcd(130,n)=gcd(231,n)=1
factor 130=2∗5∗13factor 231=3∗7∗11
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:
17−1(mod130)≡2317∗23≡1(mod130) ✓17−1(mod231)≡6817∗68≡1(mod231) ✓