Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

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 $

share|improve this answer
    
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.

share|improve this answer
    
yes, brilliant. thanks a lot. very helpful. –  Claire May 27 '13 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.