Which expressions are equivalent to 35 + 30s - 45t?
2 answers:
You might be interested in
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
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.