2

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.

user71181
  • 253
  • 2
    Was there a proof? If so, did you read it? – user2357112 May 15 '14 at 06:29
  • 1
    Wild guess: $a,b,x,y$ are allowed to be integers, positive, negative, or zero, except that $a$ and $b$ can't both be zero. For instance, If $a=6$ and $b=10$, then taking $x=2$ and $y=-1$ you get $d=2$. Is that the smallest $d$ you can get? Well, the only positive integer smaller than $2$ is $1$. Can you get $6x+10y=1$? Not if $x$ and $y$ have to be integers, because then $6x+10y$ is an even number, and $1$ is odd. Well, is $gcd(6,10)=2$? – bof May 15 '14 at 06:38
  • 1
    You might find the Wikipedia article on Bezout's identity enlightening. It includes a proof. http://en.wikipedia.org/wiki/B%C3%A9zout's_identity – Kaj Hansen May 15 '14 at 06:41
  • check whether there's any mention of the well-ordering principle in your book. – abstract May 15 '14 at 06:45
  • @abstract: That's just induction.. I've never understood why we need multiple names for the same thing haha.. – user21820 May 15 '14 at 06:47
  • @21820 it seems intelligent beings tend to have affinity for proper-nouns – abstract May 15 '14 at 06:48
  • @abstract: Haha! The one I was taught was called "Least Integer Axiom". Not too bad actually, since it says what it means and means what it says.. – user21820 May 15 '14 at 06:49
  • @21820 exactly. – abstract May 15 '14 at 06:55

1 Answers1

2

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

user21820
  • 57,693
  • 9
  • 98
  • 256
  • +1 but I wish you'd swap the letters $a,b$ with $x,y$ so as to agree with the notation in the question. – bof May 15 '14 at 06:53
  • @bof: Done! I've been so used to $x,y$ being the constants and $a,b$ being the coefficients that I didn't notice the opposite notation in the question. – user21820 May 15 '14 at 06:55