Number theory,GCD, coprime integers

193 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST 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.