Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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