Suppose 1 ≤ k ≤ n − 1 and gcd(k, n) = 1. Prove that gcd(n − k, n) = 1

Question

I wrote: Since gcd(n-k, n)=1, we can use Bezout's Identity to say: ∃(x,y)∈Z such that (n-k)x+ny=1. Distributing, nx-kx+ny=1. One can then produce the equation: n(x+y)-kx=1. I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?

Answer 1

Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $\gcd(3,4) = 1$ rather than $\gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.

Another way to prove it is to assume there is a $d \gt 0$ with $d \mid n - k$ and $d \mid n$. Then $d \mid n - (n-k) = k$. However, since $\gcd(k,n) = 1$, this means $d = 1$, so $\gcd(n-k,n) = 1$.

A similar, but perhaps a bit simpler, way to show this is to let $d = \gcd(n-k,n)$, giving that $d \mid n-k$ and $d \mid n$, so $d \mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $\gcd(n-k,n) = 1$.

Answer 2

Yes, you can use Bezout: $\ 1 = \gcd(n,k) = an\!+\!bk = (a\!\color{#c00}{+\!b)n - b(n\!}-\!k)\,\Rightarrow\,\gcd(n,n\!-\!k)=1$

Or $ $ if $\ d\mid n\ $ then $\ d\mid k\!\iff\! d\mid n\!-\!k,\,$ so $\,n,k\,$ and $\,n,n\!-\!k\,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= \max S)$

Or $\!\bmod d\!:\: $ if $\,n\equiv 0\ $ then $\ k\equiv 0\!\iff\! k\equiv n,\,$ so $\ \ldots\,$ (as above)

Answer 3

$\gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form $g=ax+by$ where $a,b \in \mathbb Z$.

Since $\gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$

So

\begin{align} 1 &= ak + bn \\ &= -a(-k) -an + an + bn \\ &= -a(n-k) + (a+b)n \\ &= (-a)(n-k) + (a+b)n \end{align}

Since $1$ is the smallest possible positive integer, it follows that

$$\gcd(n-k,n)=1$$