Question Number 92255 by jagoll last updated on 05/May/20
$$\mathrm{7x}\:=\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{18}\:\right)\: \\ $$
Answered by Rasheed.Sindhi last updated on 05/May/20
$$\mathrm{7}{x}\equiv\mathrm{3}\left({mod}\:\mathrm{18}\right) \\ $$$$\mathrm{7}{x}\equiv\mathrm{3}+\mathrm{18}\left({mod}\:\mathrm{18}\right) \\ $$$$\mathrm{7}{x}\equiv\mathrm{21}\left({mod}\:\mathrm{18}\right) \\ $$$${x}\equiv\mathrm{3}\left({mod}\:\mathrm{18}\right) \\ $$
Commented by Joel578 last updated on 06/May/20
$${yes},\:{there}\:{are}\:{many}\:{solutions} \\ $$
Commented by jagoll last updated on 06/May/20
$$\mathrm{only}\:\mathrm{x}\:=\:\mathrm{3}\:\mathrm{sir}\:? \\ $$
Commented by Maclaurin Stickker last updated on 06/May/20
$${x}=\mathrm{18}{n}+\mathrm{3}\:{for}\:{n}\in\mathbb{Z} \\ $$$$\:{think}\:{there}\:{are}\:{many}\:{solutions}…\: \\ $$$${or}\:{am}\:{I}\:{wrong}? \\ $$
Commented by Rasheed.Sindhi last updated on 06/May/20
$$\bullet{x}\equiv\mathrm{3}\:\left({x}\:{is}\:{congruent}\:{to}\:\mathrm{3}\right. \\ $$$${mesns}\:{x}=\mathrm{3}+\mathrm{18}{n}\:{for}\:{n}\in\mathbb{Z} \\ $$$$\bullet{x}\equiv\mathrm{3}\left({mod}\:\mathrm{18}\right)\:{means}\:{all}\:{values} \\ $$$${which}\:{leaves}\:{remainder}\:\mathrm{3}\:{when} \\ $$$${they}\:'{re}\:{divided}\:{by}\:\mathrm{18}. \\ $$
Answered by Rio Michael last updated on 07/May/20
$$\mathrm{if}\:\mathrm{gcd}\left(\mathrm{7},\mathrm{18}\right)\:=\:{d} \\ $$$$\mathrm{and}\:{d}\mid\:\mathrm{3}\:\Rightarrow\:\mathrm{there}\:\mathrm{is}\:\mathrm{a}\:\mathrm{solution} \\ $$$$\mathrm{but}\:\mathrm{relative}\:\mathrm{to}\:\mathrm{18}\:,\:\mathrm{7}\:\mathrm{is}\:\mathrm{prime}\: \\ $$$$\mathrm{so}\:\mathrm{from}\:\mathrm{my}\:\mathrm{suggestion} \\ $$$$\:\mathrm{7}{x}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{18}\right)\:\mathrm{has}\:\mathrm{1}\:\mathrm{solution} \\ $$$$\mathrm{since}\:{d}\:=\:\mathrm{gcd}\left(\mathrm{7},\mathrm{18}\right)\mid\:\mathrm{3}. \\ $$$$\mathrm{these}\:\mathrm{theorem}\:\mathrm{might}\:\mathrm{help}. \\ $$$$\mathrm{if}\:{ax}\:\equiv\:{b}\:\left(\mathrm{mod}\:{n}\right) \\ $$$$\mathrm{and}\:\mathrm{gcd}\:\left({a},{n}\right)\:=\:{d} \\ $$$$\mathrm{then}: \\ $$$$\left(\mathrm{1}\right)\:{d}\:\mid{b}\:\mathrm{implies}\:\mathrm{a}\:\mathrm{solution} \\ $$$$\left(\mathrm{2}\right)\:{ax}\:\equiv\:{b}\:\left(\mathrm{mod}\:{n}\right)\:\mathrm{has}\:{d}\:\mathrm{solutions}. \\ $$$$\:\:\:\boldsymbol{\mathrm{solution}} \\ $$$$\:\mathrm{7}{x}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{18}\right) \\ $$$$\mathrm{gcd}\:\left(\mathrm{18},\mathrm{7}\right) \\ $$$$\:\:\mathrm{18}\:=\:\mathrm{7}\left(\mathrm{2}\right)\:+\:\mathrm{4} \\ $$$$\:\:\:\mathrm{7}\:=\:\mathrm{1}\left(\mathrm{4}\right)\:+\:\mathrm{3} \\ $$$$\:\:\:\:\mathrm{4}\:=\:\mathrm{1}\left(\mathrm{3}\right)\:+\:\mathrm{1} \\ $$$$\:\:\:\:\:\mathrm{3}\:=\:\mathrm{3}\left(\mathrm{1}\right)\:+\:\mathrm{0}\:\mathrm{by}\:\mathrm{euclid}'\mathrm{s}\:\mathrm{algorithm} \\ $$$$\mathrm{moving}\:\mathrm{backwards}\:\mathrm{through}\:\mathrm{the}\:\mathrm{steps}\:\mathrm{in}\:\mathrm{euclid}'\mathrm{s}\:\mathrm{algorithm}. \\ $$$$\:\mathrm{1}\:=\:\mathrm{4}−\mathrm{1}\left(\mathrm{3}\right) \\ $$$$\:\:\:\:=\:\mathrm{4}−\mathrm{1}\left(\mathrm{7}−\mathrm{4}\right) \\ $$$$\:\:\:\:=\:\mathrm{4}−\mathrm{1}\left(\mathrm{7}\right)\:+\mathrm{1}\left(\mathrm{4}\right) \\ $$$$\:\:\:\:=\:\mathrm{2}\left(\mathrm{18}−\mathrm{7}\left(\mathrm{2}\right)\right)\:−\mathrm{1}\left(\mathrm{7}\right) \\ $$$$\:\:\:\mathrm{1}\:=\:\mathrm{2}\left(\mathrm{18}\right)−\mathrm{4}\left(\mathrm{7}\right)−\mathrm{7} \\ $$$$\:\:\:\mathrm{1}\:=\:\mathrm{2}\left(\mathrm{18}\right)−\mathrm{5}\left(\mathrm{7}\right) \\ $$$$\Rightarrow\:−\mathrm{5}\left(\mathrm{7}\right)\:=\:\mathrm{1}−\mathrm{2}\left(\mathrm{18}\right) \\ $$$$\mathrm{multiplicative}\:\mathrm{inverse}\:\mathrm{of}\:\mathrm{7}\:\mathrm{is}\:−\mathrm{5}. \\ $$$$\Rightarrow\:\mathrm{7}{x}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{18}\right) \\ $$$$\:\:\:\:\:−\mathrm{5}×\mathrm{7}{x}\:\equiv\:\mathrm{3}\:×−\mathrm{5}\:\left(\mathrm{mod}\:\mathrm{18}\right) \\ $$$$\Rightarrow\:\:{x}\:\equiv\:−\mathrm{15}\:\left(\mathrm{mod}\:\mathrm{18}\right) \\ $$$$\:\:{x}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{18}\right)\:\mathrm{is}\:\mathrm{the}\:\mathrm{only}\:\mathrm{solution}. \\ $$$$ \\ $$
Commented by Maclaurin Stickker last updated on 09/May/20
$${thank}\:{you}\:{sir} \\ $$