Prove that $\gcd(k,n) = 1$ if and only if $ \exists m,d \in \mathbb{Z}: mk+nd=1$

Question

I need to understand why $\gcd(k,n) = 1 \Leftrightarrow \exists m,d \in \mathbb{Z}: mk+nd=1 $. Any help would be appreciated.

Answer 1

Bezout's Identity is proven in this answer.

---

For any pair of positive integers $a$ and $b$, there exist $x,y\in\mathbb{Z}$ so that $ax + by = \gcd(a,b)$.

Proof:

Consider the set $$ K = \{ ax + by\ |\ x,y\in\mathbb{Z}\}\tag{1} $$ Let $k$ be the smallest positive element of $K$. Since $k\in K$, there are $x,y\in\mathbb{Z}$ so that $$ k = ax + by\tag{2} $$ Because $\mathbb{Z}$ is a Euclidean Domain, we can write $$ a = qk + r\text{ with }0\le r < k\tag{3} $$ Therefore, we can write $$ \begin{align} r &= a - qk\\ &= a - q(ax+by)\\ &= a(1-qx)+b(-qy)\\ &\in K\tag{4} \end{align} $$ Since $k$ is the smallest positive element in $K$, $(3)$ and $(4)$ imply that $r$ must be $0$. Thus, $a = qk$, and therefore, $k$ divides $a$. Similarly, $k$ divides $b$. Thus, $k$ is a common divisor of $a$ and $b$, and therefore, $k\le\gcd(a,b)$.

Since $\gcd(a,b)$ divides both $a$ and $b$, and $k = ax + by$, $\gcd(a,b)\mid k$.

Since $\gcd(a,b)\mid k$ and $k\le\gcd(a,b)$, we get that $\frac k{\gcd(a,b)}\le1$ is a positive integer. Therefore, $\frac k{\gcd(a,b)}=1$; that is, $k=\gcd(a,b)$. Thus, $(2)$ becomes $$ \gcd(a,b)=ax+by\tag{5} $$

Answer 2

Hint: The gcd of $k$ and $n$ is the least positive value of $kx+ny$ where $x,y$ range all over the integers.