Wednesday, 29 October 2014

divisibility - Number theory,GCD, coprime integers



I am sorry for the bad title but I really can't think of a better one.
So I was learning about the euclidean algorithm and I see a statement that is hard for me to understand. In the book that I was reading, it says that if X and Y are coprime integers, then (X-Y) and Y are also coprime. It says that this is really easy to prove, so the proof is omitted. Can anyone explain or write down the proof for this?



Answer



Suppose, to the contrary, that XY and Y are not co-prime. So there exists an integer d2 and integers m,n such that XY=md and Y=nd.



But then X=(m+n)d, so d divides both X and Y, contradicting the fact that X and Yare co-prime.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...