Answer to Question #260104 in Discrete Mathematics for King

Question

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

≡

Answer 1

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