2
$\begingroup$

Michael Artin in Proposition 2.6 states:

Let $a,b$ be integers not both zero, and let $d$ be the positive integer which generates the subgroup $a \mathbb Z +b \mathbb Z$ then

  • $d$ can be written in the form of $ar+bs$
  • $d$ divides both $a,b$
  • If an integer $e$ divides $a$ and $b$, it also divides $d$

My questions:

  1. How does the second proposition hold true for $a=2,b=7 , d=9$?

  2. How do we prove this? (a slight hint may be sufficient)

  • 2
    $d$ is the positive integer that **generates** $\dots$. Definitely if $a=2$ and $b=7$ then $d\ne 9$. Indeed $d=1$.2012-09-06

4 Answers 4

5

Question 1: It doesn't, but these three numbers don't satisfy the assumptions because $2\mathbb{Z}+7\mathbb{Z}$ isn't generated by $9$. (As pointed out slightly faster by Julian).

Question 2: This follows from the fact that $\{a,b\}\subset a\mathbb{Z}+b\mathbb{Z}$. (Here I have taken your second question to mean "how do we prove the second proposition?").

3

$2\mathbb{Z}+7\mathbb{Z}=\mathbb{Z}$, not $9\mathbb{Z}$:

$2\cdot (-3)+7\cdot (1)=1$.

  • 0
    Thanks for pointing this out. I indeed checked it, and well... :) (sheepish smile)2012-09-06
0

Hint $\ $ The set $\rm\:S\:$ of integers of the form $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ is closed under subtraction so, by the Lemma below, every $\rm\:n\in S\:$ is divisible by the least positive $\rm\:d\in S.\:$ Thus $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, by $\rm\:e\:|\:a,b\:$ $\Rightarrow$ $\rm\:e\:|\: \hat x\:a+\hat y\:b = d\:$ $\Rightarrow$ $\rm\:e\le d.$

Lemma $\ \ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\:1} \in S.$

Proof $\ \: $ If not there is a least nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\:1} \in S\:$ is a nonmultiple of $\rm\:m_{\:1}.$

Remark $\ $ This fundamental lemma, interpreted procedurally, yields Euclid's classical algorithm to compute the gcd using only repeated subtraction.

This linear representation of the the gcd is known as the Bezout identity for the gcd. It need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:D = \mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there are no $\rm\:f(x,y),\: g(x,y)\in D\:$ such that $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\:0 = 1.$

0

There are several things you want to do. The first would be to show that $H=a\mathbb{Z} + b\mathbb{Z}$ contains positive integers and let $S$, say, be the set of all positive integers in $H$. Use the well-ordering principle to obtain a least element of $S$ and call this least element $d$. Now, let $t=ar+bs \in H$. Write $t=qd+r, 0\leq r, by the division algorithm. Note that $r=t-qd$ is in $H$, which is a contradiction unless $r=0$, whence $d$ divides $t$. Thus $d$ divides both $a$ and $b$ since each is is $H$.

If $e$ divides both $a$ and $b$, then $e$ must divide $d$, since $d \in H$ and so can be written as $d=ar+bs$ for suitable $r$ and $s$.

In essence, you have just shown that $d$ is the greatest common divisor (or, highest common factor) of $a$ and $b$.