Prove that $\gcd(k,n) = 1$ if and only if $ \exists m,d \in \mathbb{Z}: mk+nd=1$ I need to understand why $\gcd(k,n) = 1 \Leftrightarrow \exists m,d \in \mathbb{Z}: mk+nd=1 $. Any help would be appreciated.
 A: 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}
$$
A: Hint: The gcd of $k$ and $n$ is the least positive value of $kx+ny$ where $x,y$ range all over the integers. 
