Question #260104

(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.


1
Expert's answer
2021-11-02T18:25:39-0400

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

141=197+8,19=82+3,8=32+2,3=21+1,2=12+0,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=321=3(832)=8+33=8+3(1982)=31987=193(141197)7=141(7)+1952.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)+19521(mod141),141(-7)+19\cdot 52\equiv1(\mod 141), and hence

19521(mod141).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 19521(mod141),19\cdot 52\equiv1(\mod 141), we conclude that 19(527)7(mod141),19\cdot (52\cdot 7)\equiv 7(\mod 141), and thus

x527(mod141)364(mod141)82(mod141).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,x=82+141k, where kZ.k\in\Z.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS