# Euclid's Algorithm - Finding positive solutions (x,y)

Ok, so maybe I'm missing some crucial steps here, but I just can't see it.

So, I have got $\gcd(144,252) = 36$

$144x+252y=36$

I need to find ALL positive solutions. I can find $x=2$ and $y=-1$ by reversing the algorithm. The answer is given as follows.

$36=144-108 =144-(252-144) =2\times144-252$

But then says

$\times 117$
$4212=118 \times2 \times144 -117 \times252$

solution of $4212 = 144x + 252y$ are $x= 234- 252t/36 = 243 - 7t$ $y= -117 + 144t/36 = -117 + 4t$

$x,y>0$ if $234/7 > t > 117/4$

$t=30,31,32,33$

$(x,y)=(24,3),(17,7),(10,11),(3,15)$

FIRSTLY - where on earth does the multiplier $117$ come from? this seems to have been plucked from thin air,

and secondly, please, how to convert the $t$ values into the $(x,y)$ values. ie, how does $30$ relate to $(24,3)$

Many thanks

-
I think you need to clarify whether the base question is how to express $4212=144x+252y$ with $x$ and $y$ both being positive (or non-negative?) integers. –  Mark Bennet May 27 '13 at 17:36
In the line $4212 = 118 \times 2 \times 144 - 117 \times 252$, the $118$ must be $117$. –  f.nasim May 27 '13 at 17:37

If $ax+by=c$, then $a(x+nb)+b(y-na) = c$ for all $n$, since $a(x+nb)+b(y-na) = ax+nab+by-nab = c$

-
ok thanks that is helpful, but why 117? –  Claire May 27 '13 at 17:10
Your original problem was probably to find the solutions of 4212=144x+252y; 4212=36(117) –  Zen May 27 '13 at 17:13
Helps to read the question doesn't it, this has had me stumped. the original question has 114x+252y=4212. Didn't see the 4212, just waded in with the algorithm. SORRY for wasting your time!. –  Claire May 27 '13 at 17:16

sIt isn't clear what problem you are trying to solve. Using multiples of $144=4 \cdot 36$ and $252=7 \cdot 36$ you can generate any multiple of $36$.

Note that (Fact A) $1008 =28 \cdot 36 = 7 \cdot144=4\cdot252.$

Now it looks as though your original question may have been to express $4212=144x+252y$ with both $x$ and $y$ being positive integers.

The first step in this is to check the gcd of $144$ and $252 = 36$ and then check that this is a factor of $4212$ - if it isn't, the problem cannot be solved. $4212=117\cdot 36$. So that is where the $117$ comes from.

If we have a convenient way of writing $36$ - in this case $36=2 \cdot 144-252$ we can multiply this by $117$ to get an expression for $4212=234\cdot144-117\cdot252$

The next thing we need is to adjust this so that the $-117$ is replaced by a positive integer. Using Fact A, we can increase $-117$ by $4t$ provided we reduce $234$ by $7t$ (the total remains the same). The smallest multiple of $4 \ge117$ is $120=4\cdot30$, corresponding to $t=30$. We can't allow $234$ to be replaced by a negative number, and we note that: $7\cdot33=231, 7\cdot34=238$, so $t \lt34$. This tells you which valued of $t$ will work.

Finally $(x,y)=(234-7t,-117+4t)$

I hope this helps you to understand the logic involved - you will need to work it through yourself.

-
yes, brilliant. thanks a lot. very helpful. –  Claire May 27 '13 at 17:49