Answered

Welcome to Westonci.ca, where your questions are met with accurate answers from a community of experts and enthusiasts. Discover the answers you need from a community of experts ready to help you with their knowledge and experience in various fields. Connect with a community of professionals ready to help you find accurate solutions to your questions quickly and efficiently.

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

Sagot :

LammettHash

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 choosing our service. We're dedicated to providing the best answers for all your questions. Visit us again. We hope our answers were useful. Return anytime for more information and answers to any other questions you have. Westonci.ca is your trusted source for answers. Visit us again to find more information on diverse topics.