-2~

Return to Mat 417 Menu ,Home Page, Course Menu, Quarter Schedule, Grading Policy et. al.

Discussion of the GCD and LCM Excerpted from draft of the full discussion.

The following discussion is made to supplement our class activities and discussions, not supplant them. Remember that division is an operation, divides is a relation and the division algorithm extends the operation of division to allow for nonzero remainders. Also, remember that the following definitions generalize in tact by replacing the word "integers" with "real numbers."

Definitions: (Be sure you can write-out the definitions of the following terms, explain the relationships that hold among them and can prove the properties that hold for each.)

Division: For any two integers a and b≠0, we define to mean there exists a unique integer c such that b*c=a.

We say that “b is a divisor of a" or that" a is divided by b." We call b the divisor, a the dividend and c the quotient with a zero remainder.

Division is a binary operation over the real number system that is a function on ). Division is the rule of correspondence that gives us instructions as to how to assign to each given ordered pairs of numbers (a, b≠0) a unique number c such that b*c=a. In the case of , then a=b=q=1 and r=0. The only restriction to the division process is that the divisor b cannot be zero as is proved in the Theorem 1 below.

Divides : For two integers a and b≠0, we say that "b divides a" and write whenever b is a divisor of a, i.e. integer c such that c*b=a that satisfies the definition of the division operation above.

If b divides a, then we say that b is a factor of a and that a is a multipe of b. If no such integer c exists, we say that "b does not divide a" and write .

"Divides" defines a relation. Distinct from a function or operation, a relation is a Yes/No, True/False, etc. statement. We say that ba is a true statement whenever the division process of a nonzero integer b divided into a number a has a zero remainder. If the remainder is not zero, then a does not divide b and we say that a and b are not related and reference this by writing . And by the Law of the excluded middle, any two integers a and b≠0 are either related meaning that r=0 or they are not related, r≠0. There is no in between situation.

The Division Algorithm below defines the process by which we divide b into a, for any pair of integers a and b≠0 if b cannot be repeatedly subtracted from a an integral number of times.

Division Algorithm: For any pair of integers a and b≠0, there are unique integers q and r for which a=b*q+r and 0 ≤r< b.

The nonzero integer b is called the divisor; a is called the dividend, q the quotient and r the remainder. Symbolically we write: " integers a and b≠0, $ ! integers q and r, a=b*q+r and 0≤r<b.

The Division Algorithm is the extension of the division process (a binary operation) that allows for a nonzero remainder. The Division Algorithm tells how many times c the divisor b can be subtracted from a number a with a remainder r such that 0 ≤r< a.

COMMENTS:

Note: Division is a binary operation over the real number system (function on ). Division is the rule of correspondence that gives us instructions as to how to assign to each given ordered pairs of numbers (a, b≠0) a unique number c such that b*c=a. In the case of , then a=b=q=1. The only restriction is that the divisor b cannot be zero as is proved in the Theorem 1 given below.

The Division Algorithm is an extension of the division process that allows for a possible nonzero remainder. The Division Algorithm tells how many times c the divisor a can be subtracted from a number b allowing the possibility of there being a remainder r such that 0 ≤r< a.

Divides is a relation. A relation is a Yes/No, True/False, etc. statement. We say that ab is a true statement whenever the division process of an integer b divided by a nonzero whole number a has a remainder of zero. If the remainder is not zero, then a does not divide b, we say that a and b are not related and write . The end result is that a and b are either related ( r=0) or they are not related (r≠0). There is no in between situation.

Example: We say that 2|6 is a true statement because the operation 6 2=3 has an integral solution.

We say that 2|7 is not a true statement because the operation 7 2 does not have an integral solution. In this case, we write 2 7. However, the Division Algorithm says that 7=2*3 + 1 where b=2 is the divisor, a=7 the dividend, c=3 the quotient and r=1 is the remainder.

As promised above, we now give the proof that is based solely on the definition of division; namely, division by zero is undefined. It is not the case that division by zero is impossible by the meaning of that term today. In the early 1900's it was impossible for man to go to the moon, but it became possible in 1968. It is not now possible, nor will it ever be possible to divide by zero in the real number system, because it cannot be defined in that system. There are number systems where there are zero divisors, i.e. nonzero numbers whose product is zero, e.g. 2*3=9mod(6). Do not confuse the existence of zero divisors with division by zero. They are two separate entities.

Theorem 1: Division by zero is undefined.

Proof:

Case i) b=0:

The expression is not defined because there is no unique number c for which 0*c=0. It is the case that 0*c=0 for all real numbers c by the zero property of multiplication. So there is no unique number c satisfying 0*c=0 because, (0*5)=(0*76)=(0* )=(0*158)=0.

Case ii) b≠0:

The expression is undefined because there is no existence of a real number c for which c*0=b for any nonzero number b. By the same zero property of multiplication as referenced above, 0*c=0 for all real numbers c. So the division equation is undefined because there is no number c for which 0*c is not zero.

Repeat: 0 is not (cannot) be a divisor of any real number.

We need the following definitions in order to discuss some very powerful properties of the "divides" relation.

Definition: GCD(HCF)

‑Given any two integers, a nonzero integer c such that c|a and c|b is called a common divisor (common factor) of a and b. If d is the largest positive common divisor (common factor) of the two integers a and b, then d is called the greatest common divisor of a and b and is denoted by gcd(a,b)=d. (We define a common multiple and the LCM below.)

Some books refer to our greatest common divisor as the highest common factor. We write gcd(a,b)=d and they write hcf(a,b)=d. (A rose by any other name would still smell as sweet so what does it matter what we call the property?)

Examples: 5|35 and 5|75, because 5*7=35 and 3*5²=75. We can use are tests for "divides" to see that no smaller integer divides both numbers, so gcd(35,75)=5

gcd(4,6)= gcd(2 * 2, 2 x 3)= 2

gcd(36,45)= gcd(2² * 3², 3² * 5²)= 9

gcd(18,21,33)= gcd(2 * 3² , 3 * 7, 3 * 11)= 3

Property of common divisors and the gcd:

i) If d is any common divisor of two nonzero integers a and b, then d|gcd(a,b).

Remark: The gcd is used in reducing fractions to their lowest terms; eg.

Definitions:

Prime Number: A natural number p greater than one is said to be prime if it is divisible only by one and itself.

Relatively prime: If 1 is the only positive common divisor of any two integers a and b, that is gcd(a,b)=1, then a and b are said to be relatively prime. For example, gcd(15,28)=1 because 15 and 28 are not both divisible by any integer other than 1.

Properties of the “Divides” relation:

i) If c is any common divisor of two integers a and b, then c|gcd(a,b).
For example, 2|24 and 2|36, therefore, 2| 6 because the gcd(24,36)=6.

(And if n is any common multiple of of the two integers, then m|n. Clearly, this property proves that the gcd(a,b) and lcm(a,b) are unique because it says that both the gcd and lcm divide themselves.)

ii.) If a nonzero integer a divides an integer b, then a also divides the additive inverse, that is negative b, b. That is, a|b a|( b). Inverses of equals are equal, so (a*c)=b for some integer c implies that (a*c)= b. And we know that (a*c)=( a)*c=a*( c) by the uniqueness property of additive inverses, so we also get that a| b and a| b, etc.

The following is an alternate write-up of this same proof. Namely, whenever one integer divides another integer, then it also divides the inverse of that integer.

· Given for integers a≠0 and b.

· There exists a unique integer by the definition of divides.

· By the property that additive inverses of equals are equal.

· Equivalent property of negative integers as stated above.

· Definition of divides.

We should note that the proof of property ii) depends only on the closure property of multiplication and the definition of divides.

iii) If a nonzero integer a divides integers b and c, then a also divides the sum or difference of b and c.

That is, if a|b and a|c, then a|(b±c).

The proof of property iii) utilizes the distributive property of multiplication over addition and the definition of divides. (That is, by the definition of divides, integer r, s ar=b and as=c that by the distributive property satisfies the equations a(r±s)=ar±as=b±c which in turn satisfies the definition for a to divide b±c.)

iv) If a nonzero integer a divides an integer b and c is any other integer, then a also divides the product b*c. That is, if a|b then a|(b*c), for all integers c.

v) If a nonzero integer d divides an integer a and divides the sum or difference of a multiple of a and some integer r, then a is also a divisor of r. This property is just a corollary of the divides properties iii and iv given above. Namely, if d≠0, c and r are integers such that d|a and d|(ac+r), then by property iii) above, d|(ac+r)–ac which says that d|r.

Basic Models for finding the GCD and LCM of two or more numbers.

1. SET INTERSECTION Model Intersect the sets of divisors of two or more numbers and take the largest one.

Advantages:

§ Provides visual representation for the lower grades.

§ Provides a good initial presentation at any grade level because the student can literally see the relationship the gcd has with the rest of the common divisors.

Disadvantages:

§ Not good for large numbers because it is too cumbersome searching through all of the common divisors for the largest.

Example:

D_(6,10)= D₆ D₁₀ = {1, 2, 3, 6} ) {1, 2, 5, 10} = {1,2} gcd(6,10)= 2.

M_(6,10)= M₆ M₁₀₌{6,12,18,24,30, . . .} { 10,20,30, . . .} = {30, 60.) lcm(6,10)=30.

2. CUISENAIRE OR OTHER COLORED RODS Model

Advantages:

§ Visual for younger students for numbers 1 to 30 or a max line of three rods of length ten. This model also has the same set of Advantages and Disadvantages as the Set Intersection model, but provides the students with much more of a visually vivid and tactile experience.

Disadvantages:

§ Younger students must be dexterous enough to be able to stack the rods.

§ Process is impractical for numbers larger than fifty.

Example:

gcd(6,10)=2 lcm(6,10)=lcm((3*2),(5*2))=2*3*5=30

3. PRIME FACTORIZATION Model:

This model is a direct application of The Fundamental Theorem of Arithmetic: Every nonzero integer can be written as a finite product of multiples of distinct prime numbers

Advantages:

§ Good for numbers up to 2,000 for students who know their basic multiplication facts.

§ Gives solid foundation for understanding the factorization process for grades 6 and over.

Disadvantages:

§ Unnecessarily long process for very large numbers.

§ Requires mastery of working with exponents.

§ Confusing to many students who don’t understand the concepts of the gcd and the lcm. To wit: To get the greatest (common divisor) you take the least (smallest) power of each factor in the prime factorization of the numbers. But to get the least common multiple, you take the largest power of each factor in the prime factorization.

Therefore: gcd(420,522)= and lcm(420,522) =

It is usually more convenient for K-5 students to use a tree diagram than to find the prime factorization of two numbers using exponents.

4. TREE DIAGRAM Model:

Advantages:

§ Has same underlying factorization process as the previous model but lends itself to the students finding just two factors of any number in any one step.

§ Enables student to visualize the process leading to a clearer understanding of the concepts.

§ Eliminates the greatest/least, largest/least comparisons inherent in the Prime Factorization Model.

Disadvantages: Unnecessarily long process for very large numbers.

The following example finds the gcd and lcm of 280 and 702 using the tree diagram model.

Find the gcd and lcm of 280 and 702.

From this tree model, we see that the gcd(280,702)=2 and the lcm(280,702)=2³3³5 7 117

5. TWO AT A TIME Model

Advantages:

§ Good model if need to find the gcd or lcm of more than two numbers.

§ Helps to avoid the possible confusion that can take place by trying to factor too many numbers at one time.

§ Process is immediate for finding the gcd if there are any two any two numbers which are relatively prime and lets you pair up your numbers in the easiest way you see fit.

Disadvantages: Unnecessary if have small to intermediate numbers because using the prime factorization model would save time.

Example: Find the gcd(4,15,45). You can start with any two of the numbers but if you take a moment to look at the numbers here, you'll see that gcd(4,15)=1, so it must also be the case that gcd(4,15,45)=1.

Find the1cm(12,15,108) . Your rules of integer divisibility say that 3 and 4 both divide 12 and 108 telling you immediately that lcm(12,108)=108. Because 3 also divides 15=3*5, the only other factor you need to account for is 5. Hence, you know that lcm(12,15,108)=5*108=540. You could also have found the prime factorization of all three numbers, but combining what your rules for integer divisibility tell you and a little thinking and you can get your answer much more quickly.

Alternatively, we could have found the lcm(12, 15, 108) by observing that 3*4=12. This tells you that you need both 3 and 4 as factors of the lcm. Also, 3*5=15 and you already have 3 as a factor so now you just need to pick up 5 as a factor. To this point you have that lcm(3*4*5,15)=12*5=60. Your rules of divisibility tell you that both 3 and 4 also divide 108 so you can get the lcm of all three numbers by now finding lcm(12*5,12*4)=12*5*4=60*4=240.

6. Formula Model: Product(a*b ) = gcd(a,b)*lcm(a,b), so and

Advantages:

§ Lets you see how the three numbers relate algebraically.

§ You can always find the product of the two numbers, so you only need to find one of the gcd or the lcm to find the result of both of them just by using the formula.

§ Answer is immediate if one knows the numbers a and b are relatively prime. Then the gcd(a,b)=1 and the lcm(a,b) is just the product a*b

Disadvantages:

§ Still need to find one of gcd or lcm by one of the above models before can apply the formula.

§ Unnecessarily confusing to younger students because they are just manipulating numbers and not building them from scratch as with some of the other models.

Example: . It should be easy for you to see that gcd(10, 32)=2, so

lcm(10,32)= .

7. REPEATED DIVISION Model

Advantages:

§ Is the fastest way to break down large numbers.

§ Students use this model combined with two-at-a-time.

Disadvantages:

§ Difficult for students still struggling with their division skills.

i.) GCD Case:

The Repeated Division model is called the Euclidean Algorithm when used to find the gcd of two integers.

The Euclidean Algorithm: If a and b are any integers, then gcd(a,b)=gcd(r,b), where r is the remainder when a is divided by b.

The Euclidean Algorithm is just a repeated application of the Division Algorithm and the Divides Property iii given earlier in this discussion. Suppose we wand to find the gcd(a,b≠0) using this repeated division model. If a=b≠0 then gcd(a,b)=a=b. So let's suppose with out loss of generality that b< a. The Division Algorithm guarantees us that we can divide b into a and find unique integers q and r, 0≤r< b such that a=(b*q+r). Further, we know that if d is a common divisor of b and r, then it is also a divisor of a by the Divides Properties iii and iv.

So the task becomes one of finding a common divisor of b and r. The remainder r<b, so the Division Algorithm guarantees us again that there exist unique integers q and r such that b=(r*q +r ) and 0≤r <r. We know that we can find a common divisor d of both r and r , so d also divides b and we continue in this same manner. Each remainder is nonnegative and less than the divisor with the first remainder being less than b. Hence, we know that we have less than b many steps to take before we must get a zero remainder. And, of course, the division steps end and the Divide Property iii takes over. Let's go to an example to see how the process works.

Example: Find the gcd(24,42),.

We have to stop when we get a zero remainder because division by zero is undefined.

By working backwards applying the properties of the divides relation at each step, we see that the last divisor that results in a zero remainder is then our gcd. That is,

6|6 and 6|18, so 6| (6+18) 6|24

6|18 and 6|24, so 6|(18+24) 6|42.

gcd(24, 42)=6.

Further, we can check that there is no greater common divisor of 24 and 42 by referencing the prime factorizations 24=2³ *3 and 42=2³ *3*7. So the gcd of any two numbers is the last divisor of the Euclidean Algorithm process that gives us a zero remainder. We show a condensed way to write up this process for the gcd after we discuss how to use the repeated division model to find the lcm of two numbers.*

*To me, it interesting how it is that if you just keep substituting the Division Algorithm equalities back into each step, you arrive back to the simple statement that 42=6*7.

42=1*(24)+18

42=(18+6)+18=2*18+6 substitute for 24, 24=1*(18)+6, then for 18, 18=3*6+0.

42= 2*18+6=2(3*6)+6= (by distributivity) 6*(2*3+1) =6(6+1)=6*7=42 Therefore, gcd(24, 42)=6

If we solve for 6 at the last step,

6=42-2*18,18=42-1*24, and substitute this in for 18, we get

6=42-2*(42-1*24)=42-2*42+2*24, so

6=(-1)42+48 gives us one example of how 6 as the gcd can be written as a linear combination of of 24 and 42.

ii.) LCM Case. The following discussion is not intended to fully explain how to find the lcm of any set of numbers using the repeated division model. The summary given here is intended only to remind you of how we cover the process in class.

Example:Please refer to your class notes to see how nice this process is to do even if it is not necessarily nice to explain.

lcm(24, 42)	To find the lcm(24 and 42), choose a factor of either number. We choose seven because divides 42. We set up the following diagram recording the cofactors of 7 for any number 7 divides and the all numbers with which 7 is relatively prime.
7	24, 42 .
	Record 24 unchanged because gcd(7, 24)=1 so 7 24. Record the co-factor 6 because 7*6=42. Choose 2 because it divides both 24 and 6 and repeat recording the cofactors in the same manner as described above..
2	24, 6
	24=212 and 6=23. Record the corresponding cofactors of 2 which are12 and 3 for 24 and 6 respectively. Notice that 3 divides both 3 and 12, so work with 3 next.
3	12, 3
	12=34 and 3=31. Record the co-factors 4 and 1 of 3 and choose 4 as the next divisor.
4	4, 1 4=4*1. Note that here is no factor other than one to be found now.
	1, 1 The lcm is the product of all of the divisors written vertically in the left column. That is, lcm= .

It should be noted that it is the process that yields the correct lcm here, not the way or order in which any one divisor is chosen. For example, the following shows another way to write-up the same model to find the same lcm(24,42).

lcm(24, 42)	To find the lcm the two numbers 24 and 42, this time first choose the common divisor 6.
6	24, 42 24=64 and 42=67
	Record cofactors 4 and 7 and choose a divisor at least of one of them, eg. 2
2	4, 7 4=2*2 but 2 7
	Record the cofactor 2 keep the number 7 because gcd(2,7)=1. We choose 2 as the divisor of 2 and notice that we could have saved a step if we had chosen 4 for the divisor for the first step.
2	2, 7 2=2*1 but 2 is still not a factor or 7
	Record 1 because 2=2*1 ; leave the 7 unchanged because gcd(2,7)=1. Your next divisor has to be 7 because it is the only non=unit divisor remaining. Repeat.
7	1, 7 71=7 and 7 1. We end up with all 1's in the last row. 1 1 Reading off the divisors we took this time gives us the same lcm as above, lcm(24,42)=62217=2³37=168*

Additional examples:

Example of another way of keeping track of the Euclidean Algorithm steps to find the gcd(117,522).						Condensed version of Repeated Div Model to find
		4				LCM(2,3,5,15)
	117	522	-----------		522 = 4*117+54
		468				2	2, 3, 5, 15
		54	117	-------	117 = 4*54 + 9	3	1, 3, 5, 15
			108			5	1, 1, 5, 5
			9	54 54	54 = 6*9 + 0		1, 1, 1, 1
				0	GCD(117, 522)=9	LCM(2,3,5,15)=

Condensed Summary of the Integer Divisibility Tests: (A complete write up with proofs of the following divisibility tests is given in the Integers Divisibility Tests discussion.)

a. An integer is divisible by 2, 5, or 10 if and only if its unit's digit is divisible by 2, 5, or 10, respectively.

b. An integer is divisible by 4 if and only if the last 2 digits of the integer represent a number divisible by 4.

c. An integer is divisible by 8 if and only if the last 3 digits of the integer represent a number divisible by 8.

d. An integer is divisible by 3 or by 9 if and only if the sum of its digits is divisible by 3 or 9, respectively.

e. An integer is divisibility by 7 or seven divides an integer if and only it 7 divides the result after you repeatedly double and subtract. You double the most rhs digit and subtract it from the remaining number until you get a number that is obviously divisible or not divisible by 7.

f. An integer is divisible by 11 if and only if the sum of the digits in the odd place value columns minus the sum of the digits in the even place value columns is divisible by 11.

Symbolically,11 |[(sum odd place value digits) – (sum even place value digits)]. This is often abbreviated as 11|[(sum even) - (sum odd)] because if d|a, then d|(-a).

Note: a|b ®a|(-b), so odd-even or even-odd place value s does not matter.

g. m | n An integer n is divisible by an integer m if and only if n is divisible by all of the relatively prime factors of m.

For example, 6 divides an integer if and only if the integer is divisible by both of the relatively prime factors 2 and 3.

Return to Mat 417 Menu, Home Page, Course Menu, Quarter Schedule , Grading Policy et. al.