Question Number 133761 by liberty last updated on 24/Feb/21
$$\mathrm{Solve}\:\mathrm{the}\:\mathrm{linear}\:\mathrm{congruence}\: \\ $$$$\mathrm{19}{x}\:\equiv\:\mathrm{4}\:\left(\mathrm{mod}\:\mathrm{141}\:\right) \\ $$
Answered by bobhans last updated on 24/Feb/21
$${Using}\:{Euclidean}\:{algorithm}\: \\ $$$$\:\mathrm{141}\:=\:\mathrm{7}×\mathrm{19}+\mathrm{8} \\ $$$$\:\:\:\mathrm{19}\:=\:\mathrm{2}×\mathrm{8}\:+\mathrm{3} \\ $$$$\:\:\:\:\:\mathrm{8}\:=\:\mathrm{2}×\mathrm{3}\:+\mathrm{2}\: \\ $$$$\:\:\:\:\:\mathrm{3}\:=\:\mathrm{1}×\mathrm{2}\:+\:\mathrm{1} \\ $$$${now}\:{we}\:{get}\:\mathrm{1}\:=\:\mathrm{3}−\mathrm{1}×\mathrm{2}\: \\ $$$$\mathrm{1}=\mathrm{3}−\mathrm{1}×\left(\mathrm{8}−\mathrm{2}×\mathrm{3}\right) \\ $$$$\mathrm{1}\:=\:\mathrm{3}×\mathrm{3}−\mathrm{1}×\mathrm{8} \\ $$$$\mathrm{1}=\mathrm{3}×\left(\mathrm{19}−\mathrm{2}×\mathrm{8}\right)−\mathrm{1}×\mathrm{8} \\ $$$$\mathrm{1}=\:\mathrm{3}×\mathrm{19}−\mathrm{7}×\mathrm{8} \\ $$$$\mathrm{1}=\mathrm{3}×\mathrm{19}−\mathrm{7}\left(\mathrm{141}−\mathrm{7}×\mathrm{19}\right) \\ $$$$\mathrm{1}=\mathrm{52}×\mathrm{19}−\mathrm{7}×\mathrm{141} \\ $$$${This}\:{show}\:{that}\:\mathrm{52}\:{is}\:{an}\:{inverse}\:{of} \\ $$$$\mathrm{19}\:\left({mod}\:\mathrm{141}\right) \\ $$$${Then}\:\mathrm{19}{x}\equiv\mathrm{4}\:\left({mod}\:\mathrm{141}\right) \\ $$$$\Rightarrow\mathrm{52}×\mathrm{19}{x}\:\equiv\:\mathrm{4}×\mathrm{52}\:\left({mod}\:\mathrm{141}\right) \\ $$$$\Rightarrow\left(\mathrm{1}+\mathrm{7}×\mathrm{141}\right){x}\:\equiv\:\mathrm{208}\:\left({mod}\:\mathrm{141}\right) \\ $$$$\therefore\:{x}\equiv\:\mathrm{67}\:\left({mod}\:\mathrm{141}\right) \\ $$