Question

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

Answer 1

First of all, the modular inverse of n modulo k can only exist if GCD(n, k) = 1.

We have

130 = 2 • 5 • 13

231 = 3 • 7 • 11

so n must be free of 2, 3, 5, 7, 11, and 13, which are the first six primes. It follows that n = 17 must the least integer that satisfies the conditions.

To verify the claim, we try to solve the system of congruences

$\begin{cases} 17x \equiv 1 \pmod{130} \\ 17y \equiv 1 \pmod{231} \end{cases}$

Use the Euclidean algorithm to express 1 as a linear combination of 130 and 17:

130 = 7 • 17 + 11

17 = 1 • 11 + 6

11 = 1 • 6 + 5

6 = 1 • 5 + 1

⇒   1 = 23 • 17 - 3 • 130

Then

23 • 17 - 3 • 130 ≡ 23 • 17 ≡ 1 (mod 130)

so that x = 23.

Repeat for 231 and 17:

231 = 13 • 17 + 10

17 = 1 • 10 + 7

10 = 1 • 7 + 3

7 = 2 • 3 + 1

⇒   1 = 68 • 17 - 5 • 231

Then

68 • 17 - 5 • 231 ≡ = 68 • 17 ≡ 1 (mod 231)

so that y = 68.