English Deutsch Français Italiano Español Português 繁體中文 Bahasa Indonesia Tiếng Việt ภาษาไทย
All categories

pls attached the solution

2007-02-19 00:21:03 · 4 answers · asked by Lanie R 1 in Science & Mathematics Mathematics

4 answers

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

1/(19 modulo 141) = 1/8

2007-02-19 00:26:41 · answer #2 · answered by gebobs 6 · 0 1

19/141= 0 Remainder 19

so ans = 19

inverse = 1/19

2007-02-19 00:28:48 · answer #3 · answered by dragongml 3 · 1 0

1/19

2007-02-19 01:15:18 · answer #4 · answered by Anonymous · 1 1

fedest.com, questions and answers