4
$\begingroup$

How to prove the following theorems about gcd?

Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$.

Theorem 2: Let $a$ and $b$ be nonzero integers. The gcd of $a$ and $b$ is the smallest positive linear combination of $a$ and $b$.

Progress

For Theorem 1 I have assumed that $d$ is the smallest possible linear combination of $a$ and $d$. Then $a = dq + r$. Solved it and found a contradiction. Is my method correct? Don't know what to do for Theorem 2.

$\endgroup$
1
  • $\begingroup$ Does theorem 2 imply theorem 1, since the gcd of two numbers is also their common divisor. Or am I missing something. Hence it is sufficient to prove theorem 2. $\endgroup$
    – john
    Sep 1, 2020 at 17:15

2 Answers 2

3
$\begingroup$

The procedure very briefly sketched in your comment is the standard way to prove Theorem 1.

For Theorem 2, the proof depends on exactly how the gcd of $a$ and $b$ is defined. Suppose it is defined in the naive way as the largest number which is a common divisor of $a$ and $b$.

We then need to show that there cannot be a larger common divisor of $a$ and $b$ than the smallest positive linear combination of these numbers.

Let $w$ be the smallest positive linear combination of $a$ and $b$, and let $d$ be their largest common divisor.

There exist integers $x$ and $y$ such that $w=ax+by$. Since $d$ divides $a$ and $b$, it follows that $d$ divides $ax+by$. So $d$ divides $w$, and therefore $d\le w$.

Your proof of Theorem 1 shows that $w$ is a positive common divisor of $a$ and $b$, so $w\le d$. It follows that $d=w$.

Remark: An alternate definition of the gcd is that it is a positive integer $d$ which is a common divisor of $a$ and $b$, and such that any common divisor of $a$ and $b$ divides $d$. Theorem 2 can also be proved in a straightforward way using that alternate (but equivalent) definition.

$\endgroup$
0
$\begingroup$

Theorem 1 is equivalent to asking: Is the remainder $r$ a linear combination of $a, b$?

If $d$ would not divide $a$, by division theorem: $a=dq+r, 0\lt r\lt d$. Furthermore, $a=dq+r\implies r=a-dq$, which means $r$ is a linear combination of $a$ and $b$, and it less than $d$, a contradiction that $d$ is the smallest. By the same idea we can prove $d$ divides $b$, so $d$ is a common divisor of $a$ and $b$.

$\endgroup$

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.