# Prove $\mathbb Z \gcd(a,b)=\mathbb Z a + \mathbb Z b$ without conclusion of Bézout's identity to define $\gcd$ similar to $\text{lcm}$

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 $\text{lcm}(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 $\text{lcm}(a,b)$.

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

$m:=\text{lcm}(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$, $\tag{2}$

whence we deduce the set equality $$\mathbb Z \text{lcm}(a,b)=\mathbb Z a \cap \mathbb Z b \tag{1},$$ instead of defining $\text{lcm}(a,b)$ with the set equality $(1)$ and then deducing $(2)$.

• Observation 2: For $\text{lcm}(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 $\text{lcm}(a,b)$ is given in Cor 2.3.9 which states $ab=\gcd(a,b)\text{lcm}(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 Z\gcd(a,b) = \mathbb Za + \mathbb Zb, \tag{4}$$ 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$, $\tag{3}$

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. \tag{5}$$

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)=e\gcd(e_{\alpha},e_{\beta}), \text{where} \ e_{\alpha} := \frac{a'a+b'b}{e} \ \text{and} \ e_{\beta} := \frac d e \ \text{are 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} := \frac{a'a+b'b}{e} \ \text{and} \ e_{\beta} := \frac d e \ \text{are 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)\text{lcm}(a,b) \implies \frac{1}{\text{lcm}(a,b)} = \frac{r}{b} + \frac{s}{a} = r\frac{1}{b} + s\frac{1}{a}.$$

So, the inverse of $\text{lcm}(a,b)$ is an integer combination of the inverses of $a$ and $b$.

• You know, the statement in your title pretty much is Bezout's identity. – Lord Shark the Unknown Aug 31 '18 at 15:57
• @LordSharktheUnknown Had a feeling. Edited to 'conclusion of' instead. Ok now? Hmm...not sure how to phrase this, but I want to prove the converse without writing $d$ as a linear combination or something. I mean, we can define $\text{lcm}$ with (a) and (b) in Prop 2.3.8. I would like to see if we can similarly define $\text{gcd}$ with (a) and (b) in Prop 2.3.5. – BCLC Aug 31 '18 at 15:59
• The classic approach is to prove that $\mathbb{Z}a + \mathbb{Z}b = \mathbb{Z}d$, where $d$ is the minimal positive element of $\mathbb{Z}a + \mathbb{Z}b$. I don't see anything simpler than that. – metamorphy Aug 31 '18 at 16:13
• Bezout's identity is equivalent to $\Bbb Za+\Bbb Zb\supset \Bbb Z\gcd(ab).$ – DanielWainfleet Sep 1 '18 at 3:48
• @DanielWainfleet i changed bezout to the conclusion of bezout. Basically I want to do for gcd's what is done for lcm's, i.e. we can define $m:=\text{lcm}(a,b)$ with $m$ is divisible by both $a$ and $b$ and any integer divisible by $a$ and $b$ is divisible by $m$, so I want to know if we can define $d:=\gcd(a,b)$ with $d$ divides both $a$ and $b$ and any integer that divides $a$ and $b$ divides $d$. Edited question. Thanks! – BCLC Sep 1 '18 at 6:04

Since $d$ divides $a$ and $b$, there are $a',b'\in\mathbb{Z}$ such that $a=a'd, b=b'd$, so $a,b\in\mathbb{Z}d$, hence $\mathbb{Z}a+\mathbb{Z}b\subseteq\mathbb{Z}d$.
Now pick $e\in\mathbb{Z}a+\mathbb{Z}b$ minimum among those $x\in\mathbb{Z}a+\mathbb{Z}b$ such that $x>0$. Let $e=na+mb$. By the Euclidean algorithm we have $a=a'e+r$ with $0\leq r<e$, so $r=(1-a'n)a-a'mb\in\mathbb{Z}a+\mathbb{Z}b$; 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 $d\in\mathbb{Z}e$ and $\mathbb{Z}d\subseteq\mathbb{Z}e$. On the other hand we have $\mathbb{Z}e\subseteq\mathbb{Z}a+\mathbb{Z}b\subseteq\mathbb{Z}d$, what implies $\mathbb{Z}e=\mathbb{Z}a+\mathbb{Z}b=\mathbb{Z}d$.
Note that there exist GCD domains which are not Bézout domains, so the property $\mathbb{Z}a+\mathbb{Z}b=\mathbb{Z}d$ 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.
• Not using $(c)$! Woohoo! Thanks Jose Brox! ^-^ – BCLC Sep 1 '18 at 7:49
• "Since $e$ divides both $a$ and $b$, $e$ divides $d$" - depending on prerequisites, this may or may not be clear. The conventional logic is implied $e \leqslant d$, and $d \in \mathbb{Z}a + \mathbb{Z}b$ (as $d|a$ and $d|b$) implies $d \leqslant e$. Just a minor remark ;) – metamorphy Sep 1 '18 at 16:24