The problem is to prove: Let a,b belong to the set of integers, and a,b not equal to 0. Then for d belonging to the natural numbers, d=gcd(a,b) if and only if (1) d divides a and d divides b (2) if c is a common divisor of a and b then c divides d.

Bezout's lemma: For a,b belonging to the set of natural numbers, n belonging to the integers, we have gcd(a,b) divides n if and only if we can find x,y belonging to the integers such that n=ax+by. I.e. The set {ax+by:x,y belong to the integers} is precisely the set of integer multiples of gcd(a,b).

  • $\begingroup$ What are your thoughts on this problem? $\endgroup$ – paw88789 Nov 13 '14 at 11:52

Definition: If $a$ and $b$ are integers with one of them not zero, then the greatest common divisor, $gcd(a,b)$, of $a$ and $b$, is the positive integer $d$ satisfying:

(1) $d \mid a$ and $d \mid b$.

(2) If $c \mid a$ and $c \mid b$, then $c \leq d$.

Theorem: Suppose $a$, $b$ are integers not both $0$. Then, for an integer $d>0$, $d=gcd(a,b)$ if and only if

(a) $d \mid a$ and $d \mid b$.

(b) If $c \mid a$ and $c \mid b$, then $c \mid d$.

Proof: Suppose $d=gcd(a,b)$. Then (a) is (1) in the definition. Now, taking $n=d$ in Bezout's Lemma gives $d=ax+by$ for certain integers $x$ and $y$; so, if $c \mid a$ and $c \mid b$, we have $a=cm$ and $b=cn$ for certain integers $m$ and $n$, so that $$d=(cm)x+(cn)y=c(mx+ny).$$ Then (b) follows. Conversely, suppose $d>0$ is an integer and that (a) and (b) hold. Then (1) is (a) from the statement. Now, if $c \mid a$ and $c \mid b$, then, by (b), $c \mid d$, so that $c \leq d$. This is (2) from the defintion. Therefore $d=gcd(a,b)$.

| cite | improve this answer | |

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.