-2~

Discussion of the GCD and LCM Draft.

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 are generalized 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 c*b=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 multiple 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 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 by the divides relation and write . And by the Law of the excluded middle, for any two integers a and b≠0 either b divides a or b does not divide a. There is no in between or compromise situation.

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

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 allows the five-cricket to jump three times and walk two steps to get to seventeen.

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 any number 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=0 mod(6). Do not confuse the existence of number systems that have zero divisors with the operation of division as by zero as it is defined in the real number system. They are two separate entities.

Theorem 1: Division by zero is undefined. [Def Division: For any two integers a and b≠0, we define to mean there exists a unique integer c such that c*b=a.]

Proof:

Case i) a≠0, b=0:

The expression is undefined because there is no real number c for which c*0=a for any nonzero number a. By the zero property of multiplication 0*c=c*0=0 for all real numbers c. There does not exist a real number c for which the division equation is defined. There simply is no number c for which 0*c=0*c is not zero,.

Case ii) a=0, b=0:

The expression is not defined because there is no unique number c for which 0*c=c*0=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 ; (0*5)=(0*76)=(0* )=(0*158)=0, etc.

Reiteration: 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 our 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.

Definition:

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 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.

Comment: A primary use of the gcd is in reducing fractions to lowest terms, for example,

Definition: LCM ‑ For two nonzero integers a and b, if m is an integer such that a m and b m, then m is called a common multiple a and b. If m is the smallest positive common multiple of the two integers a and b, then m is called the least common multiple and is denoted by lcm(a,b)=m.

Examples: 125 825 and 175 875, because 125*7=875 and 175*5²=875, so lcm(125,175)=875.

lcm(4,6) =	lcm( ) =	=	12
lcm(36,45) =	lcm( ) =	=	180
lcm(18,21,33)	lcm( ) =	=	1386

Property of common multiples and the lcm:

i) If m is any common multiple of two nonzero integers a and b, then lcm(a,b) m.

Remark: A primary use of the lcm is in finding the least common denominator of two or more fractions; eg.

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((32),(52))=235=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 first divide the small of the two numbers into the larger number.

Divide 24 into 42 to find the first Division Algorithm expression 42=1*(24)+18. Then

Divide the (smaller) remainder 18 into the divisor 24 (24<42) to get the Division Algorithm expression 24=1*(18)+6 and repeat the process again.

Divide the remainder 6 into the divisor 18 to see that 18=3*6 + 0.

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.

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
	Therefore, gcd(24, 42)=6.

Further, we can check that there is no greater common divisor of 24 and 42 nor a smaller least common multiply 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 .

Addendum:

I have always found 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 first for 24, 24=1*(18)+6	then for 18, 18=3*6 + 0
42 = 218+6=2(36)+6=	(distribute) 6(23+1)=6(6+1)=6*7=42	Therefore, gcd(24, 42)=6

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 7 divides 42.
7	24, 42 .
	Record 24 unchanged because gcd(7, 24)=1 so 7 24. Bring down 6 because 7*6=42. Choose another number that divides both 24 and 6. We choose 2 and repeat recording the cofactors in the same manner as above.
2	24, 6
	24=212 and 6=23. Record the corresponding cofactors 12 and 3. 3 divides both 3 and 12, so we choose to work with 3 next.
3	12, 3
	12=34 and 3=31. Record the co-factors 4 and 1 and choose 4 as the next divisor.
4	4, 1
	1, 1 Note that only ones are left. The lcm is the product of all of the divisors written vertically in the left column. That is, lcm(24,42)= .

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)	We choose the common divisor 6 this time.
6	24, 42 24=64 and 42=67
	Record cofactors 4 and 7; choose a divisor of at least of one of them, eg. 2
2	4, 7 4=2*2 but 2 7
	Record the cofactor 2 the number 7 because gcd(2,7)=1 and choose 2 next. We notice we could have saved a step here by choosing 4 for the divisor for the first step.
2	2, 7
	2=21 but 2 7, so bring down 1 and 7. 7 is the only non-unit divisor left and 71=7
7	1, 7 7*1=7 and 7 1. We end up with all 1's in the last row.
	1 1 Therefore, lcm(24,42)=62217= as above.

Additional examples of ways to find the lcm of two numbers:

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 number represented by the last 2 digits is divisible by 4.

c. An integer is divisible by 8 if and only if the number represented by the last 3 digits is 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 divisible by 7 if and only it 7 divides the result after you repeatedly double and subtract the units digit. I.e. subtract double the unit's digit from the number you get after you take the units digit away. Repeat doing this 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 11[(sum even)-(sum odd)]. I.e. add every other digit then subtract the sum of digits. If 11 divides the difference, then 11 divides the original number. It really doesn't matter if you (sum even place value digits) subtract (sum odd place value digits)] because d a d (-a).

alt. Separate a number's digits into consecutive triples, find the sum of every other triple and subtract the sum of the in-between triples like for the divisibility test for 11 gives an alternate test for 7, 11, and 13. I.e. 11 352469827 iff 11 [827 - 352 + 469 ], but today it's a lot easier to just get our your calculator for integers greater than one thousand.

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 both of the relatively prime factors 2 and 3 of six divide the number.