# Section 2.1 Comments

**Proposition 2.1.5. **Let a and b be integers, not
both zero. Then any common divisor of a and

b is a divisor of gcd(a, b).

Proof. The cast of characters in this proof:

• Integers **a** and **b** such that .

• By Proposition 1.3.8 there exists a greatest common divisor of a and b. Set **
g** = gcd(a, b).

• An integer** c **such that and
.

• The previous line gives rise to two more characters: The integers **u** and
**v **such that

and . The previous line gives also more
information about **c**: .

The quest in this proof is . Or, more
specifically the quest is and an integer **
z**

such that .

Now we start with the proof. By **Theorem 2.1.3** there exist integers **x**
and **y **such that

This is a quite dramatic scene, and the characters **u** and** v** demand
the stage:

But, the associativity of multiplication yields

and distributive low now gives

At this point our quest is finished in a color coordinated solution

**z = ux + vy.**

Since also , the
quest is successfully completed.

**Proposition 2.1.7.** Let a and b be positive
integers. Then any common multiple of a and b is

a multiple of lcm(a, b).

Proof. The cast of characters in this proof:

(I) **Positive** integers **a** and **b**.

(II) By Proposition 1.3.9 there exists a **least positive common multiple**
of a and b.

Set **m** = lcm(a, b).

(III) The previous line, that is the phrase **common multiple** hides two
more characters: the

integers** j **and **k** such that and
.

(IV) It is important to notice the following character feature of **m**: It
is the** least positive**

common multiple of a and b. What this means is the following

If an integer x is a common multiple of of a and b and x < m, then x ≤ 0. |

(V) An integer **c** which is a **common multiple**
of a and b.

(VI) The previous line gives rise to two more characters: The integers **u**
and **v** such that

and .

The quest in this proof is . Or, more
specifically the quest is and an integer**
z**

such that .

Now we start with the proof. In fact we start with a brilliant idea to use **
Proposition 1.4.1 **.

This proposition is applied to the integers c and m > 0. By** Proposition 1.4.1**
there exist integers

**q** and **r** such that

and .

What we learn about r from the previous line is that
. But, there is more action waiting

to be unfolded here. Follow the following two sequences of equalities (all the
green equalities!):

r = c − mq = au − mq = au − (aj)q = a(u − jq)

r = c − mq = bv − mq = bv − (bk)q = b(v − kq).

The conclusion is: **r is a common multiple** of a and b . But wait, also
. Now the item

(IV) in the cast of characters (in fact the character feature of m) implies that
. Since

also , we conclude
. Going back to the equality
, we conclude that

. At this point our quest is completed in a
color coordinated solution

**z = q.**

**Proposition 2.1.10.** If a and b are positive
integers, then ab = gcd(a, b) ยท lcm(a, b).

Proof. The cast of characters in this proof:

(I) **Positive** integers **a** and **b**.

(II) By Proposition 1.3.9 there exists a **least positive common multiple**
of a and b.

Set **m** = lcm(a, b).

(III) The previous line, that is the phrase **common multiple** hides two
more characters: the

integers** j** and **k **such that and
.

(IV) It is important to notice the following character feature of **m**: It
is the** least positive**

common multiple of a and b. What this means is the following

If an integer x is a common multiple of of a
and b and x > 0, then m ≤ x. |

(V) By Proposition 1.3.8 there exists a greatest common
divisor of a and b. Set **g** = gcd(a, b).

(VI) The previous line gives rise to two more characters: The integers **u**
and **v** such that

and . Since
and , we
conclude that and
.

The quest in this proof is simple .

Now we start with the proof. Consider a new green integer **c = guv**.
Clearly

**c = guv = av** and **c = guv = bu.**

Hence and
. That is c is a common multiple of a and b. Moreover,
. Now

the item (IV) in the cast of characters (in fact the character feature of m)
implies that .

Hence . Multiplying both sides of this
inequality by g > 0 we get

Hence . This is in some sense one half of
the quest. For the second half, we recall

**Theorem 2.1.3** and conclude that there exist integers **x** and **y**
such that

Multiplying both sides of this equality by m > 0 we get
y . Now more characters

are demanding the scene:

mg = max + mby = (bk)ax + (aj)by = ab(kx) + ab(jy) = ab(kx + jy).

Since and
, I conclude . Therefore
. This is the second

half of the quest. So, the quest is completed.