## anonymous one year ago Number Theory Help!

1. anonymous

For positive integers a,b,c,d, if gcd(a,b)=gcd(c,d)=1, then prove that $\frac{ a }{ b }+\frac{ c }{ d }\notin Z$ $b \neq d$

2. anonymous

I tried to start this problem by saying that since gcd(a,b)=gcd(c,d)=1, there exist x,y,u,w such that $ax+by=cu+dv=1$

3. anonymous

Since $\frac{ a }{ b }+\frac{ c }{ d }=\frac{ ad+bc }{ bd }$, I tried to somehow manipulate the above equation to get this form, but I've failed...

4. ganeshie8

try by contradiction suppose $$\dfrac{a}{b}+\dfrac{c}{d}=n \implies ad+bc= b*d*n$$ $$\implies b\mid ad$$ and $$d\mid bc$$

5. ganeshie8

since $$\gcd(a,b)=1$$, by euclid lemme, $$b\mid ad \implies b\mid d$$ similarly $$d\mid b$$ together imply $$b=d$$, contradiction, ending the proof.

6. anonymous

Bravo!

7. anonymous

Thank you!

8. anonymous

So the key to this problem was using contradiction. Does there happen to be an alternate proof?

9. ganeshie8

sure, but i feel they all are messy... you don't like that divisibility argument is it ?

10. anonymous

No. I do like that elegant solution that you provided using contradiction. It's just that I have a feeling that there might be an alternate solution using the Bezout's Identity...

11. ganeshie8

btw the key thing is not contradiction, i think the key thing is noticing that $m\mid n ~~\text{and}~~n\mid m~~\implies n=\pm m$

12. ganeshie8

sure, lets try using bezout's identity

13. anonymous

Wait. On the other thought, I do have this odd feeling that this will be dirty...

14. ganeshie8
15. anonymous

Ah. That's exactly what I wanted! It's not that dirty as I thought it would be.

16. ganeshie8

usually euclid lemma is covered prior to bezout so it is okay to use euclid lemma as it is more fundamental or whatever..

17. anonymous

got it. Thank you!