Properties of Integers

76 Views Asked by At

A theorem presented in my discrete math book.

Let $d$ be the smallest positive integer of the form $ax + by$. Then $d = \gcd(a,b)$, where gcd means greatest common divisor.

I don't understand how the variable $d$ being the smallest possible integer from the expression ($ax + by$) results in the greatest common divisor.

It also doesn't state what are the allowed values of $a$, $b$, $x$, and $y$ are either.

My guess would be they want x and y to be integers.

1

There are 1 best solutions below

2
On

If that is all the book stated, it is not a very precise statement. Here is a precise version:

For any integers $a,b$ which are not both $0$:

  There exists a minimum positive integer $d$ such that $d = ax+by$ for some $x,y \in \mathbb{Z}$

  And $d = \gcd(a,b)$

Note that if $a=b=0$, there is no positive integer of the form $ax+by$, and at the same time $gcd(0,0)$ does not exist.

This theorem should be proven in your book, and the proof will depend on your exact definition of $\gcd$.