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