Question Number 127532 by MathSh last updated on 30/Dec/20
$${Solve}\:{the}\:{equation}: \\ $$$$\mathrm{71}{a}+\mathrm{3}{b}=\mathrm{2021} \\ $$
Commented by mr W last updated on 30/Dec/20
$${see}\:{Q}\mathrm{44819} \\ $$
Answered by Ar Brandon last updated on 30/Dec/20
$$\mathrm{2021}=\mathrm{28}\left(\mathrm{71}\right)+\mathrm{33} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:=\mathrm{71}\left(\mathrm{28}\right)+\mathrm{3}\left(\mathrm{11}\right) \\ $$$$\left(\mathrm{a},\mathrm{b}\right)=\left(\mathrm{28},\mathrm{11}\right)\:\mathrm{is}\:\mathrm{a}\:\mathrm{solution} \\ $$
Commented by MathSh last updated on 30/Dec/20
$${Thanks}\:{sir} \\ $$
Answered by floor(10²Eta[1]) last updated on 30/Dec/20
![General solution to a Diophantine equation. ax+by=c let d=gcd(x, y)⇒d∣x, d∣y∴d∣ax+by=c ax+by has a solution if and only if d∣c. now suppose (x_0 , y_0 ) is a particular solution, then, ax_0 +by_0 =ax+by=c a(x_0 −x)=b(y−y_0 ) since d=gcd(a, b)⇒a=a′d, b=b′d where gcd(a′, b′)=1 da′(x_0 −x)=db′(y−y_0 ) a′(x_0 −x)=b′(y−y_0 ) ⇒(I): a′∣b′(y−y_0 )⇒a′∣(y−y_0 ) [because gcd(a′,b′)=1⇒a′∤b′] ⇒y−y_0 =a′k⇒y=y_0 +a′k ⇒(II): b′∣a′(x_0 −x)⇒b′∣(x_0 −x) ⇒x_0 −x=b′k⇒x=x_0 −b′k so the general solution to a diophantine equation of the form ax+by=c is (x, y)=(x_0 −((bk)/d), y_0 +((ak)/d)), k∈Z where (x_0 , y_0 ) is a particular solution now that you know this try to solve your question.](Q127574.png)
$$\mathrm{General}\:\mathrm{solution}\:\mathrm{to}\:\mathrm{a}\:\mathrm{Diophantine}\:\mathrm{equation}. \\ $$$$\mathrm{ax}+\mathrm{by}=\mathrm{c} \\ $$$$\mathrm{let}\:\mathrm{d}=\mathrm{gcd}\left(\mathrm{x},\:\mathrm{y}\right)\Rightarrow\mathrm{d}\mid\mathrm{x},\:\mathrm{d}\mid\mathrm{y}\therefore\mathrm{d}\mid\mathrm{ax}+\mathrm{by}=\mathrm{c} \\ $$$$\mathrm{ax}+\mathrm{by}\:\mathrm{has}\:\mathrm{a}\:\mathrm{solution}\:\mathrm{if}\:\mathrm{and}\:\mathrm{only}\:\mathrm{if}\:\mathrm{d}\mid\mathrm{c}. \\ $$$$ \\ $$$$\mathrm{now}\:\mathrm{suppose}\:\left(\mathrm{x}_{\mathrm{0}} ,\:\mathrm{y}_{\mathrm{0}} \right)\:\mathrm{is}\:\mathrm{a}\:\mathrm{particular}\:\mathrm{solution}, \\ $$$$\mathrm{then},\: \\ $$$$\mathrm{ax}_{\mathrm{0}} +\mathrm{by}_{\mathrm{0}} =\mathrm{ax}+\mathrm{by}=\mathrm{c} \\ $$$$\mathrm{a}\left(\mathrm{x}_{\mathrm{0}} −\mathrm{x}\right)=\mathrm{b}\left(\mathrm{y}−\mathrm{y}_{\mathrm{0}} \right) \\ $$$$\mathrm{since}\:\mathrm{d}=\mathrm{gcd}\left(\mathrm{a},\:\mathrm{b}\right)\Rightarrow\mathrm{a}=\mathrm{a}'\mathrm{d},\:\mathrm{b}=\mathrm{b}'\mathrm{d} \\ $$$$\mathrm{where}\:\mathrm{gcd}\left(\mathrm{a}',\:\mathrm{b}'\right)=\mathrm{1} \\ $$$$\mathrm{da}'\left(\mathrm{x}_{\mathrm{0}} −\mathrm{x}\right)=\mathrm{db}'\left(\mathrm{y}−\mathrm{y}_{\mathrm{0}} \right) \\ $$$$\mathrm{a}'\left(\mathrm{x}_{\mathrm{0}} −\mathrm{x}\right)=\mathrm{b}'\left(\mathrm{y}−\mathrm{y}_{\mathrm{0}} \right) \\ $$$$\Rightarrow\left(\mathrm{I}\right):\:\mathrm{a}'\mid\mathrm{b}'\left(\mathrm{y}−\mathrm{y}_{\mathrm{0}} \right)\Rightarrow\mathrm{a}'\mid\left(\mathrm{y}−\mathrm{y}_{\mathrm{0}} \right)\: \\ $$$$\left[\mathrm{because}\:\mathrm{gcd}\left(\mathrm{a}',\mathrm{b}'\right)=\mathrm{1}\Rightarrow\mathrm{a}'\nmid\mathrm{b}'\right] \\ $$$$\Rightarrow\mathrm{y}−\mathrm{y}_{\mathrm{0}} =\mathrm{a}'\mathrm{k}\Rightarrow\mathrm{y}=\mathrm{y}_{\mathrm{0}} +\mathrm{a}'\mathrm{k} \\ $$$$\Rightarrow\left(\mathrm{II}\right):\:\mathrm{b}'\mid\mathrm{a}'\left(\mathrm{x}_{\mathrm{0}} −\mathrm{x}\right)\Rightarrow\mathrm{b}'\mid\left(\mathrm{x}_{\mathrm{0}} −\mathrm{x}\right) \\ $$$$\Rightarrow\mathrm{x}_{\mathrm{0}} −\mathrm{x}=\mathrm{b}'\mathrm{k}\Rightarrow\mathrm{x}=\mathrm{x}_{\mathrm{0}} −\mathrm{b}'\mathrm{k} \\ $$$$\mathrm{so}\:\mathrm{the}\:\mathrm{general}\:\mathrm{solution}\:\mathrm{to}\:\mathrm{a}\:\mathrm{diophantine} \\ $$$$\mathrm{equation}\:\mathrm{of}\:\mathrm{the}\:\mathrm{form}\:\mathrm{ax}+\mathrm{by}=\mathrm{c}\:\mathrm{is} \\ $$$$\left(\mathrm{x},\:\mathrm{y}\right)=\left(\mathrm{x}_{\mathrm{0}} −\frac{\mathrm{bk}}{\mathrm{d}},\:\mathrm{y}_{\mathrm{0}} +\frac{\mathrm{ak}}{\mathrm{d}}\right),\:\mathrm{k}\in\mathbb{Z} \\ $$$$\mathrm{where}\:\left(\mathrm{x}_{\mathrm{0}} ,\:\mathrm{y}_{\mathrm{0}} \right)\:\mathrm{is}\:\mathrm{a}\:\mathrm{particular}\:\mathrm{solution} \\ $$$$ \\ $$$$\mathrm{now}\:\mathrm{that}\:\mathrm{you}\:\mathrm{know}\:\mathrm{this}\:\mathrm{try}\:\mathrm{to}\:\mathrm{solve} \\ $$$$\mathrm{your}\:\mathrm{question}. \\ $$$$ \\ $$
Commented by MathSh last updated on 31/Dec/20
$${Thanks}\:{sir} \\ $$