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

I wish to find the integers of $a,b,c$ and $d$ such that: $$225a + 360b +432c +480d = 3$$ which is equal to: $$75a + 120b +144c+ 160d =1$$

I know I have to use the Euclidean algorithm. And I managed to do it for two integers $x$ and $y$. But can't figure out, how to do it with $4$ integers.

Solution 1:

TO solve $75a+120b+144c+160d=1$

You can always you Euclidean Algorithm to solve $75A + 120B = \gcd(75,120)=15$

And to solve $120\beta + 144\gamma = \gcd(120,144) = 24$

And to solve $144C+160D = \gcd(144,160)=16$.

Then in an attempt to solve $15e + 24f + 16g=1$ and to

Solve $15E + 24F= \gcd(15,24) = 3$ and $24\phi + 16\rho = \gcd(24,16)=8$.

Then solve $3j + 8k = 1$.

Then $j(15E + 24F) + (24\phi + 16\rho)k = 15(jE) + 24(jF+\phi k) + 16(\rho k)=1$

So $e=jE; f=jF+\phi k; g=\rho k$ and

So $(75A + 120B)e + (120\beta + 144\gamma)f + (144C+160D)g = 1$

And $a = Ae; b=Be+\beta f; c=\gamma f + Cg; d = Dg$.

Of, course there are probably insights and ways to make it simpler along the way.

But that's the general idea, just break it into smaller and smaller pieces.

===

To actually do this:

$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.

$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)

$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.

The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so

$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So

$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$

Solution 2:

$$ 144 \cdot 12 - 75 \cdot 23 = 3 $$ $$ 160 \cdot 1 - 3 \cdot 53 = 1 $$ $$ 160 \cdot 1 - 53 ( 144 \cdot 12 - 75 \cdot 23 ) =1 $$ $$ 160 \cdot 1 - 636 \cdot 144 + 1219 \cdot 75 = 1 $$

The shortest vector solution is $$ a= 3, b= -2, c= -1, d= 1 $$ with $$ 3 \cdot 75 - 2 \cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$

The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:

$$ \left( \begin{array}{rrrr} -175536 & 0 & 91585 & -144 \\ -146280 & 1 & 76320 & -120 \\ -91424 & 0 & 47700 & -75 \\ \end{array} \right) $$ This three dimensional lattice has Gram determinant $66361$ Next is a reduced basis by the LLL algorithm.

$$ \left( \begin{array}{rrrr} 0 & 4 & 0 & -3 \\ 0 & 2 & -5 & 3 \\ 8 & -1 & 0 & -3 \\ \end{array} \right) $$

The Gram matrix for the reduced basis, still with determinant 66361, is

$$ \left( \begin{array}{rrr} 25 & -1 & 5 \\ -1 & 38 & -11 \\ 5 & -11 & 74 \\ \end{array} \right) $$

There is a theorem involved here, $$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$

All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$