0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.