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 $X-Y$ and $Y$ are not co-prime. So there exists an integer $d \ge 2$ and integers $m,n$ such that $X-Y=md$ and $Y = nd$.



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

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