Question

Number Theory Help!

Answer 1

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\]

Answer 2

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\]

Answer 3

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

Answer 4

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\)

Answer 5

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.

Answer 6

Bravo!

Answer 7

Thank you!

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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\]

Answer 12

sure, lets try using bezout's identity

Answer 13

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

Answer 14

Look at robjohn's reply here
http://math.stackexchange.com/questions/1151443/prove-for-positive-integers-a-b-c-and-d-where-b-does-not-equal-d-if-gcda-b

Answer 15

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

Answer 16

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

Answer 17

got it.
Thank you!