Use the Euclidean algorithm to find integers ## a, b, c ##

[Math100]

Homework Statement

Use the Euclidean algorithm to find integers $a, b, c$ and $d$ such that $225a+360b+432c+480d=3$.

Relevant Equations

None.

Let $a, b, c$ and $d$ be integers such that $225a+360b+432c+480d=3$.
Then $75a+120b+144c+160d=1$.
Applying the Euclidean algorithm produces:
$gcd(75, 120)=15, gcd(120, 144)=24$ and $gcd(144, 160)=16$.
Now we see that $15x+24y+16z=1$.
By Euclidean algorithm, we have that $gcd(15, 24)=3$ and $gcd(24, 16)=8$, so $3m+8n=1$.
Observe that
\begin{align*}
&75A+120B=15\implies 5A+8B=1\\
&120B+144C=24\implies 5B+6C=1\\
&144C+160D=16\implies 9C+10D=1.\\
\end{align*}
This means $A=-3, B=2, C=-1$ and $D=1$.
Thus $-[75(-3)+120(2)]+[144(-1)+160(1)]=-15+16=1$.
Therefore, the integers $a, b, c$ and $d$ such that $225a+360b+432c+480d=3$ are $a=3, b=-2, c=-1$ and $d=1$.

 

[fresh_42]

I don't know the algorithm that you use ...

Homework Statement:: Use the Euclidean algorithm to find integers $a, b, c$ and $d$ such that $225a+360b+432c+480d=3$.
Relevant Equations:: None.

Let $a, b, c$ and $d$ be integers such that $225a+360b+432c+480d=3$.
Then $75a+120b+144c+160d=1$.
Applying the Euclidean algorithm produces:
$gcd(75, 120)=15, gcd(120, 144)=24$ and $gcd(144, 160)=16$.
Now we see that $15x+24y+16z=1$.
By Euclidean algorithm, we have that $gcd(15, 24)=3$ and $gcd(24, 16)=8$, so $3m+8n=1$.
Observe that
\begin{align*}
&75A+120B=15\implies 5A+8B=1\\
&120B+144C=24\implies 5B+6C=1\\
&144C+160D=16\implies 9C+10D=1.\\
\end{align*}
This means $A=-3, B=2, C=-1$ and $D=1$.

... and $5B+6C=5\cdot 2 - 6 \cdot 1=4\neq 1$ ...

Thus $-[75(-3)+120(2)]+[144(-1)+160(1)]=-15+16=1$.
Therefore, the integers $a, b, c$ and $d$ such that $225a+360b+432c+480d=3$ are $a=3, b=-2, c=-1$ and $d=1$.

... but your final result is correct, presumably because you did not use the equation in the middle.

 

[Math100]

I don't know the algorithm that you use ...... and $5B+6C=5\cdot 2 - 6 \cdot 1=4\neq 1$ ...

... but your final result is correct.

I apologize, I do not really know how to completely use the Euclidean algorithm when there are four variables to solve for. So I was making some of the stuffs up. What should be the correct way to do this?

 

[fresh_42]

I apologize, I do not really know how to completely use the Euclidean algorithm when there are four variables to solve for. So I was making some of the stuffs up. What should be the correct way to do this?

You did not use the equation in the middle, so the result came out fine. I, too, only know the algorithm for two numbers, but your solution is ok. Just delete the equation in the middle.

 

[Math100]

You did not use the equation in the middle, so the result came out fine. I, too, only know the algorithm for two numbers, but your solution is ok. Just delete the equation in the middle.

But is there another, perfect way to do this by the Euclidean algorithm?

 

[fresh_42]

We want to solve $75a+120b+144c+160d=1$ and we know $\operatorname{gcd}(75,120,144,160)=1.$
But
\begin{align*}
\operatorname{gcd}(75,120,144,160)&=\operatorname{gcd}(75,\operatorname{gcd}(120,144,160))\\
&=\operatorname{gcd}(75,\operatorname{gcd}(120,\operatorname{gcd}(144,160))
\end{align*}
We can use the Euclidean algorithm to solve $\operatorname{gcd}(a,b)=n\cdot a+ m\cdot b.$ So
\begin{align*}
\operatorname{gcd}(144,160)&=16=(-1)\cdot 144 + 1\cdot 160\\
\operatorname{gcd}(120,16)&=8= (-1)\cdot 120 +8 \cdot 16\\
\operatorname{gcd}(75,8)&=1=3\cdot 75+ (-28)\cdot 8
\end{align*}
I have not really used the algorithm, I "saw" the equations. A correct application of the algorithm would be, e.g.
\begin{align*}
\underline{75} &= 9\cdot \underline{8} +\underline{3}\\
\underline{8}&=2\cdot \underline{3} + \underline{2}\\
\underline{3}&=1\cdot \underline{2} +\underline{1}\\
\underline{1}&=2\cdot \underline{1} + \underline{0}\\
&\Longrightarrow \\
\underline{1}&=\underline{3}-1\cdot \underline{2}\\&=\underline{3}- 1\cdot (\underline{8}-2\cdot \underline{3})\\&=3\cdot \underline{3}- \underline{8}\\
&=3\cdot (\underline{75}-9\cdot \underline{8})-\underline{8}\\&=3\cdot \underline{75} + (-28)\cdot \underline{8}
\end{align*}
and a computer would prefer this algorithm, but "seeing" it is definitely shorter.

So what do we have now?
\begin{align*}
\underline{1}&=3\cdot \underline{75}+ (-28)\cdot \underline{8}\\
&=3\cdot \underline{75} + (-28)( (-1)\cdot \underline{120} +8 \cdot \underline{16})\\
&=3\cdot \underline{75} + (-28)( (-1)\cdot \underline{120} +8 \cdot ((-1)\cdot \underline{144} + 1\cdot \underline{160} ))\\
&=3\cdot \underline{75} +28\cdot \underline{120} + 224\cdot \underline{144} +(-244)\cdot\underline{160}
\end{align*}

This is what a computer would do. And, sorry, took me quite a while to type and check.

I like your version better. It is what a human would do.