## science0229 one year ago Number Theory Help!

1. science0229

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. science0229

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. science0229

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. science0229

Bravo!

7. science0229

Thank you!

8. science0229

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. science0229

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. science0229

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

14. ganeshie8
15. science0229

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. science0229

got it. Thank you!