(a) Let us find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm. Since
141=19⋅7+8,19=8⋅2+3,8=3⋅2+2,3=2⋅1+1,2=1⋅2+0,
we get that
1=3−2⋅1=3−(8−3⋅2)=−8+3⋅3=−8+3(19−8⋅2)=3⋅19−8⋅7=19⋅3−(141−19⋅7)7=141(−7)+19⋅52.
Therefore, 141(−7)+19⋅52≡1(mod141), and hence
19⋅52≡1(mod141).
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⋅52≡1(mod141), we conclude that 19⋅(52⋅7)≡7(mod141), and thus
x≡52⋅7(mod141)≡364(mod141)≡82(mod141).
We conclude that the solution is of the form
x=82+141k, where k∈Z.
Comments