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

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


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

  • $\begingroup$ Can I also ask you why "$k$ is a common divisor of $a$ and $b$" $\Rightarrow$ "$k$ divides $\gcd(a,b)$" is true? $\endgroup$ – Jxt921 Dec 26 '15 at 7:37
  • $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.