Vtyjkyuk

Algebra by Michael Artin Prop 2.3.5, on $gcd(a,b)$

I previously attempted to prove the converse of Prop 2.3.8, where Prop 2.3.8 is the analogue of Prop 2.3.5 for $textlcm(a,b)$.

Now, I want to prove the converse of Prop 2.3.5 but without using $(c)$. My motivation for making $(c)$ inadmissible is based on the following two observations on $textlcm(a,b)$.

• 
  Observation 1: For $textlcm(a,b)$, that the converse of Prop 2.3.8 is true is equivalent, I believe, to saying that $textlcm(a,b)$ can be defined with the two conclusions of Prop 2.3.8 namely that

$m:=textlcm(a,b)$ is any integer (later: the integer) that is divisible by both $a$ and $b$ and s.t. any integer divisible by $a$ and $b$ also is divisible by $m$, $tag2$

whence we deduce the set equality $$mathbb Z textlcm(a,b)=mathbb Z a cap mathbb Z b tag1,$$ instead of defining $textlcm(a,b)$ with the set equality $(1)$ and then deducing $(2)$.

• 
  Observation 2: For $textlcm(a,b)$, Prop 2.3.8 doesn't exactly have an analogue of Prop 2.3.5(c) aka Bézout's identity. However, I believe the analogue of Bézout's identity for $textlcm(a,b)$ is given in Cor 2.3.9 which states $ab=gcd(a,b)textlcm(a,b)$. (*)

Therefore, if we can prove $(2) implies (1)$ without using Cor 2.3.9, then I think we can prove the analogous set equality to $(2)$: $$mathbb Zgcd(a,b) = mathbb Za + mathbb Zb, tag4$$ without using Prop 2.3.5(c). This would be equivalent, I believe, to saying that $gcd(a,b)$ can be defined only with the first two conclusions of Prop 2.3.5, namely that

$d:=gcd(a,b)$ is any integer (later: the integer) that divides both $a$ and $b$ and s.t. any integer that divides $a$ and $b$ also divides $d$, $tag3$

whence we deduce the set equality $(4),$ instead of defining $gcd(a,b)$ with the set equality $(3)$ and then deducing $(4)$. To clarify, this means we will not assume that conclusion of Bézout's identity, i.e. we will not assume that this integer $d$ can be written as an integer combination $d=ra+sb$.

Now, I want to try to prove

Converse of Prop 2.3.5 (without (c)): Let $a$ and $b$ be integers not both zero. Suppose $d$ is an integer s.t. (a) $d$ divides $a$ and $b$, (b) any integer $e$ that divides $a$ and $b$ also divides $d$. Then $$mathbb Z d=mathbb Z a + mathbb Z b. tag5$$

Now, referring to my proof attempt of Converse of Prop 2.3.5 here, the proof for $(5)(supseteq)$ would be the same because $(5)(supseteq)$ is proved with only $(a)$. As for $(5)(subseteq)$, we can prove $(5)(subseteq)$ without assuming $(c)$ because we can actually first deduce $(c)$ from $(b)$ because apparently, $(b)$ implies $(c)$, contrary to the text and then use $(c)$.

I would like to prove $(5)(subseteq)$ both without assuming $(c)$ and without using $(c)$. Here is my attempt to do such:

Given $n in mathbb Z d$, i.e. $n/d in mathbb Z$, i.e. $n=dn_d$ for some integer $n_d$, we must write $n$ as $n=an_a+bn_b$ for integers $n_a, n_b$, i.e. we must show $n in mathbb Z a + mathbb Z b$.

• Now, the note after Prop 2.3.5 says that any integer $e$ that divides $a$ and $b$ divides the combination $a'a+b'b$, where $a'$ and $b'$ are integers. Combining this note with Prop 2.3.5 $(b)$, as an assumption that an integer $d$ satisfies, gives that for any integer $e$ that divides $a$ and $b$, $e$ divides both the linear combination $a'a+b'b$ and $d$. While I'm using an external fact (namely the note), I'm not assuming $(c)$. Hence, if $e$ divides $a$ and $b$, then

$$gcd(a'a+b'b,d)=egcd(e_alpha,e_beta), textwhere e_alpha := fraca'a+b'be textand e_beta := frac d e textare integers.$$

Of course that may be circular because the whole point of this exercise is to establish a definition of $gcd$ in which case we can instead just say: If $e$ divides $a$ and $b$, then

$$e_alpha := fraca'a+b'be textand e_beta := frac d e textare integers$$

I don't know where to go from here.

• I also thought of how we might be able to say (perhaps if we further assume $n,a,b,d > 0$) something like we can write $n$ as $n=ar_a+br_b$ for rational numbers $r_a,r_b$ and then somehow conclude that $r_a,r_b$ must be integers: Something like if they are rational but not integers, then we write them in canonical form with coprime numerators and denominators which results in some contradiction. In the case that we can write $n$ as $n=ar_a+br_b$ for rational numbers $r_a,r_b$, we have

$$frac n d=frac a d r_a + frac b d r_b$$

Now $frac n d$ is an integer by assumption and $frac a d, frac b d$ are integers by $(a)$.

I don't know where to go from here.

Update: Based on Jose Brox's answer or metamorphy's comment, I believe the idea is that we're no longer using that $mathbb Z a + mathbb Z b$, as defined in Def 2.3.4, is a subgroup of $mathbb Z$. Therefore, the way to prove the set equality involves reinventing the proof of the forms of the subgroups of $mathbb Z$ given in Thm 2.3.3.

(*) The reason why Cor 2.3.9 would be an analogue of Prop 2.3.5(c) aka Bézout's identity:

$$ab=(ra+sb)textlcm(a,b) implies frac1textlcm(a,b) = fracrb + fracsa = rfrac1b + sfrac1a.$$

So, the inverse of $textlcm(a,b)$ is an integer combination of the inverses of $a$ and $b$.

Since $d$ divides $a$ and $b$, there are $a',b'inmathbbZ$ such that $a=a'd, b=b'd$, so $a,binmathbbZd$, hence $mathbbZa+mathbbZbsubseteqmathbbZd$.

Now pick $einmathbbZa+mathbbZb$ minimum among those $xinmathbbZa+mathbbZb$ such that $x>0$. Let $e=na+mb$. By the Euclidean algorithm we have $a=a'e+r$ with $0leq r<e$, so $r=(1-a'n)a-a'mbinmathbbZa+mathbbZb$; therefore $r>0$ is discarded by minimality of $e$ (as $r<e$), thus $r=0$ and $a=a'e$. Similarly $b=b'e$. Since $e$ divides both $a$ and $b$, $e$ divides $d$. Therefore $dinmathbbZe$ and $mathbbZdsubseteqmathbbZe$. On the other hand we have $mathbbZesubseteqmathbbZa+mathbbZbsubseteqmathbbZd$, what implies $mathbbZe=mathbbZa+mathbbZb=mathbbZd$.

Note that there exist GCD domains which are not Bézout domains, so the property $mathbbZa+mathbbZb=mathbbZd$ cannot be proved by the definition of gcd alone, we need something stronger: in this case, I have actually used that any Euclidean domain is Bézout.