Try the Free Math Solver or Scroll down to Tutorials!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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.