When is N-K coprime to N?

130 Views Asked by At

I have two integers $K$ and $N$ with $K < N$.

If $K$ is not coprime to $N$, then $N - K$ is not coprime to $N$.

This is easy to show: $K = lm$ and $N = ln$, where $l$ is the shared factor between $K$ and $N$ and $m,n$ are integers. Then $N - K = ln - lm = l(n-m)$.

If $K$ is coprime to $N$, is it true that $N-K$ is coprime to $N$? Intuition says yes, but I am not sure how to prove it.

1

There are 1 best solutions below

0
On

This was simple - many thanks to the commenters.

The contrapositive is: If $N - K$ is not coprime to $N$, then $K$ is not coprime to $N$.

As before, let $N - K = ln$ and $N = lm$. Substitute (2) into (1) to have $lm - K = ln$. Thus $K = l(m-n)$ and the proof is over.