# 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.

• Consider the second equation, rewrite it $mk = nk+1$, where 1 - is remainder. – openspace Dec 25 '15 at 9:30
• Do you know about Bézout's theorem ?? : en.wikipedia.org/wiki/B%C3%A9zout%27s_identity – user252450 Dec 25 '15 at 9:32
• Do you know about the extended euclidean algorithm? It proves the $\Rightarrow$ direction. – Arthur Dec 25 '15 at 10:14

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}$$

• Can I also ask you why "$k$ is a common divisor of $a$ and $b$" $\Rightarrow$ "$k$ divides $\gcd(a,b)$" is true? – Jxt921 Dec 26 '15 at 7:37
• @Jxt921: the proof of that turns out to be longer than the small amount that needs to be added to the proof by using $k\le\gcd(a,b)$, so I changed the proof to use that. – robjohn Dec 26 '15 at 10:39

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