Section 2 - Radford University



Chapter 5: Divisibility and the Greatest Common Divisor

Practice HW p. 34 # 1, 4, Additional Web Exercises

The Greatest Common Divisor of Two Positive Integers

Definition: The greatest common divisor of two positive integers [pic] and [pic], denoted as [pic], is the largest positive integer that divides [pic] and [pic] with no remainder.

Examples: [pic] [pic]

How do we find the greatest common divisor of larger numbers?

Elementary Method for Computing the gcd of Two Numbers

Decompose each number into its prime factors. The gcd is obtained by multiplying the prime factors the two numbers have in common. If the two numbers have no common prime factors, then the gcd = 1.

Example 1: Find the gcd(360, 540).

Solution:

█

How do we find the greatest common divisor of very large integers?

Division algorithm: Let [pic]be a positive integer ([pic]) and let [pic] be any integer. Then there is exactly one pair of integers [pic] (called the quotient) and [pic] (called the remainder) such that

[pic] where [pic].

Example 1: Find the quotient q and remainder r and illustrate the division algorithm when computing [pic].

Solution:

█

The Euclidean Algorithm

The Euclidean Algorithm makes repeated use of the division algorithm to find the greatest common divisor of two numbers. Let a and b be positive integers where [pic], If [pic], then [pic]. If [pic], we apply the division algorithm as follows:

[pic]

The process ends when a remainder of zero is obtained. The last nonzero remainder, [pic], is the greatest common divisor of a and b, that is, [pic].

Note: If we set [pic] and [pic], the Euclidean Algorithm can be generalized as

[pic]

Example 2: Use the Euclidean Algorithm to determine the [pic].

Solution:

█

Example 3: Use the Euclidean Algorithm to determine the [pic].

Solution:

█

Example 4: Use the Euclidean Algorithm to determine the [pic].

Solution:

█

Note: The number of divisions needed to compute the gcd(a, b) in the Euclidean Algorithm is no more than 5 times the number of decimal digits for b.

For example, when we found [pic], b = 1095939 has 7 digits. Thus, the

[pic]

Proof that the Euclidean Algorithm Produces the gcd(a, b)

To show that [pic], the last non-zero remainder, is, the gcd(a, b) for [pic], we must show the following steps:

1. [pic] and [pic] ([pic] is a divisor of both a and b).

2. [pic] is the largest common divisor of a and b.

3. [pic] will always exist, that is, we are guaranteed to have a remainder of 0 in the Euclidean Algorithm.

Proof Step 1: Given

[pic]

Proof Step 2: Given

[pic]

Proof Step 3: For each step of the Euclidean Algorithm

[pic]

█

Least Common Multiple of Two Numbers

Definition: The least common multiple of two positive integers a and b, denoted as lcm(a, b), is the smallest positive integers that both a and b divide evenly. In mathematical terms, we say that [pic], if

1. [pic] and [pic].

2. If [pic] and [pic], then [pic].

Examples: [pic] [pic]

Fact: If k is a positive integer where [pic] and [pic], then for [pic], not only does [pic] but also [pic]. (Proof Additional Exercise)

Note: The least common multiple is used to find the least common denominator when adding or subtracting fractions.

How is the greatest common divisor related to the least common multiple? The following theorem answers that question.

Theorem: [pic]

Proof: We first need a preliminary fact that we will be able to prove in Chapter 7, which says:

If [pic] and [pic], then [pic].

Suppose [pic] and [pic]. Hence

[pic] and [pic] since [pic] and [pic]

[pic] and [pic] since [pic] and [pic]

We claim that [pic], for if not, there exists a common divisor [pic] of [pic] and [pic] where [pic] and [pic], which says that

[pic] and [pic]

But

[pic] and [pic],

which says that [pic] and [pic]. This contradicts the fact that [pic] ([pic]) Continued on Next Page

Since [pic] and [pic], we have

[pic]

[pic] (Recall [pic] and [pic])

[pic] (Cancel g’s)

Hence, [pic]. Since [pic], the preliminary fact says that [pic]. Thus, by divisibility, it follows that [pic]. Hence, using the fact that [pic] or [pic], we have

[pic].

Hence,

[pic].

Now, [pic] is the smallest positive integer that both a and b divide. This implies that [pic]. Hence

[pic]

and the proof is complete.

█

Example 5: Find the [pic].

Solution:

█

Maple Commands for Computing the Greatest Common Divisor of Two Numbers

[pic]

> igcd(360, 540);

[pic]

> igcd(52598, 2541);

[pic]

> igcd(3854682, 1095939);

[pic]

Maple Commands for Computing the Least Common Multiple of Two Numbers

> ilcm(3854682, 1095939);

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download