# Will some $m$ and $n$ always exist for $m(coprime_1)-n(coprime_2)=1$?

That is, is it guaranteed that, given any $2$ numbers, $p$ and $q$, such that $(p,q)=1$, there will exist $m$ and $n$ so that $mp-nq=1$?

It seems like there should be, but it would be nice to have a proof without much abstract algebra used.

-
The use of the (extended) Euclidean algorithm to find the coefficients giving a GCD of two integers has been discussed more than once before. This special case (GCD is 1) is not (IMHO) special enough to warrant duplication. – hardmath Feb 5 '13 at 19:05

Yes. Called Bezout identity.

It says slightly more generally that for all $a,b\in\Bbb Z\ \exists x,y\in\Bbb Z:\ xa+yb=(a,b)\$ where $(a,b)$ is the greatest common divisor. And the proof relies on identifying the element of minimal absolute value among all elements of the form $xa+yb$.

-

Yes, by the Bezout identity for the gcd (special case gcd $=1).$ Below is a simple proof by induction. See here for a more conceptual proof, which lends greater insight into the essence of the matter.

Theorem $\rm\ \ gcd(m,n) = j\,m + k\,n\$ for some $\rm\,j,k\in\Bbb Z.$

Proof $\$ By induction on $\rm\, m\!+\!n.\:$ Trivial if $\rm\,m\,$ or $\rm\,n = 0,\:$ or if $\rm\,m = n.\:$ Else, wlog, $\rm\,m > n > 0.\,$

$$\begin{eqnarray}\rm\ \ gcd(m,n) &=&\,\rm gcd(m\!-\!n,n)\quad&&\text{by Lemma below}\\ &=&\,\rm j\, (m\!-\!n) + k\, n\quad&&\text{by induction (applies since}\rm\: (m\!-\!n)\!+\!n < m\!+\!n)\\ &=&\,\rm j\,m + (k\!-\!j)\, n\quad&&{\bf QED}\end{eqnarray}$$

Lemma $\rm\ \ gcd(m\!-\!n,n) = gcd(m,n)$

Proof $\$ If $\rm\:c\,|\,n\:$ then $\rm\:c\,|\,m\!-\!n\iff c\,|\,m.\:$ Thus $\rm\,m\!-\!n,n\,$ and $\rm\,m,n\,$ have the same set $\rm\,C\,$ of common divisors $\rm\,c,\,$ hence they have the same greatest common divisor (= max $\rm\, C).$

Remark $\$ By interpreting the inductive step procedurally, one easily derives a very simple extended Euclidean algorithm to compute the Bezout linear representation of the gcd.

-
I now realise I need to read more about number theory before I can appreciate the proof, so I'll leave both answers unaccepted until then. – Alyosha Feb 5 '13 at 21:58
@Alyosha I'm happy to elaborate. What is not clear? – Math Gems Feb 5 '13 at 23:17