Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

What is the smallest integer , greater than , such that and are both defined?
Solution
For to have an inverse , it is necessary for to be relatively prime to 130. Conversely, if is relatively prime to 130, then has an inverse . The same holds for 231. Therefore we are looking for the smallest positive that is relatively prime to 130 and 231.

We can factor and . These are all of the primes up to 13, so none of the integers is relatively prime to both 130 and 231. However, 17 is relatively prime to both of these numbers. So the smallest positive integer greater than 1 that has a multiplicative inverse modulo 130 and 231 is .
Final answer
17