Answered

Connect with experts and get insightful answers on IDNLearn.com. Join our Q&A platform to get accurate and thorough answers to all your pressing questions.

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

Sagot :

LammettHashidn

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

[tex]\begin{cases} 17x \equiv 1 \pmod{130} \\ 17y \equiv 1 \pmod{231} \end{cases}[/tex]

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.

Thank you for using this platform to share and learn. Keep asking and answering. We appreciate every contribution you make. Find reliable answers at IDNLearn.com. Thanks for stopping by, and come back for more trustworthy solutions.