305 -Algebra and induction (2)

January 23, 2009

Last time we showed that given (integers) m,n with n>0, there are q,r with 0\le r<n such that m=nq+r. We began today by showing that these integers q,r are unique. When r=0, we say that n divides m, in symbols n\mid m.

Definition. A greatest common divisor of the integers m,n not both zero, is a positive integer d that divides both m,n and such that any integer that divides both m,n, also divides d.

We showed that for any m,n not both zero, there is a unique such d, in symbols d={\rm gcd}(m,n) or simply d=(m,n). We also showed the following characterization:

Theorem. Let m,n be integers, not both zero. Let S=\{l\in{\mathbb Z}^+: for some integers x,y, l=mx+ny\}.  Then the following are equivalent statements about the integer d:

  1. d=(m,n).
  2. d \mid m, d\mid n, and d\in S.
  3. S=\{ kd: k\in{\mathbb Z}^+\}.
  4. d is the least member of S.