I suspect you need the multiplicative inverse.
The inverse of 19 (mod 141) is a number such that when multiplied by 19, it will give a product congruent with 1 (mod 141).
Here, the base (141) is not a prime number, so it is possible that there be no inverse.
I did it the "easy" way (I checked all products of 19) and found 52.
52 * 19 = 988 congruent to 847, 706, 565, 424, 283, 142, 1
---
19 and 141 are relatively prime (they share no common factors) and 19 is not a divisor of 141. Therefore, 19 has an inverse.
There is a theorem in discrete math that states: if two numbers are relatively prime, there exists integers a and b such that
a*19 + b*141 = 1 (where a and/or b can be negative).
what we seek is
x*19 = k*141 + 1
which can be written in the form:
x*19 - k*141 = 1 (a=x and b=-k)
Therefore, we know the inverse exists.
---
I just found a method at
http://www.nku.edu/~christensen/section%206%20appendix%20euclidean%20algorithm.pdf
Euclid's algorithm to show that 141 and 19 are relatively prime:
141 = 7*19 + 8
19 = 2*8 + 3
8 = 2*3 + 2
3 = 1*2 + 1
Because we reach a remainder of 1, the greatest common divisor is 1 (the two numbers are relatively prime).
Working backwards.
From the last equation:
1 = 3 - 2
Using 2 from the penultimate equation (8 = 2*3 + 2) we get:
1 = 3 - (8 - 2*3) = 3 - 8 + 2*3 = 3*3 -8
Using 3 from 19 = 2*8 + 3, we get
1 = 3*(19 - 2*8) - 8 = 3*19 -6*8 - 8 = 3*19 -7*8
Using 8 from 141 = 7*19 + 8, we get
1 = 3*19 -7(141 - 7*19)
1= 3*19 -7*141 +49*19
1 = 52*19 -7*141
which is the format we needed.
7*141 is congrent to 0 modulo 141, so we can remove it from the modulo 141 sum:
1 = 52*19 (mod 141)
QFD
2007-02-19 00:34:56
·
answer #1
·
answered by Raymond 7
·
1⤊
0⤋