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.