Solution to (a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm. Show your … - Sikademy
Author Image

Archangel Macsika

(a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm. Show your steps. (b) Solve the congruence 19x ≡ 7 (mod 141), by specifying all the integer solutions x that satisfy the congruence. ≡

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

(a) Let us find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm. Since

141=19\cdot 7+8,\\19=8\cdot 2+3,\\ 8=3\cdot 2+2,\\ 3=2\cdot 1+1,\\ 2=1\cdot 2+0,

we get that

1=3-2\cdot 1= 3-(8-3\cdot 2)=-8+3\cdot 3\\=-8+3(19-8\cdot 2) =3\cdot 19-8\cdot 7\\= 19\cdot 3-(141-19\cdot 7)7=141(-7)+19\cdot 52.

Therefore, 141(-7)+19\cdot 52\equiv1(\mod 141), and hence

19\cdot 52\equiv1(\mod 141).

We conclude that 52 is the inverse of 19 modulo 141.


(b) Let us solve the congruence 19x ≡ 7 (mod 141),

Taking into account that 19\cdot 52\equiv1(\mod 141), we conclude that 19\cdot (52\cdot 7)\equiv 7(\mod 141), and thus

x\equiv 52\cdot 7(\mod 141)\equiv 364(\mod 141)\equiv 82(\mod 141).

We conclude that the solution is of the form

x=82+141k, where k\in\Z.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1151-qpid-889