Discrete Math - Day 30

Today we continued looking at prime factorization and making connections to the greatest common divisor (gcd). I started by asking students what result they had for how many factors 1872 possessed. As anticipated, only a handful of students had worked on this at home. I gave them 65 seconds to find the prime factorization of 1872. The prime factorization of 1872 is 2⁴ x 3² x 13.

I asked students what this told them about the number of factors for 1872. Many were unsure what this told them. I related this back to the shirts and pants problem when we were counting. If we had 3 pants and 4 shirts we could mix and match these 12 ways. The 3² generates 3 distinct factors: 1, 3, and 9; the 13 generates 2 distinct factors: 1 and 13. How many ways can we mix and match the 3 factors of 3² with the two factors of 13? This is exactly the same situation as the shirts and pants problem.

Students started to multiple and came to a solution of 30. One student had tried to list all of the factors and had come up with 29. Of course using counting techniques is much faster and more accurate.

I pointed out to students they should make use of their divisibility rules to help them with prime factorization. It is readily apparent from divisibility rules that 1872 is divisible by 9 since the sum of its digits is divisible by 9. In addition, the last three digits are divisible by 8 so 1872 is also divisible by 8. Once these are factored out you are left with 26, which is easily factored to 2 x 13.

I gave the students the number 1976. They worked through this value and found the prime factorization was 2³ x 13 x 19. We talked through the number of factors and more students were comfortable with seeing that 1976 had 4 x 2 x 2 = 16 factors.

I gave the class one last number to work with: 3345. The prime factorization went much faster this time as students realized the number was divisible by both 3 and 5. Factoring out 15 left a value of 223, which they saw from their prime number list was also prime. So 3345 = 3 x 5 x 223 and had 8 factors.

I asked students to summarize in their notebooks how to count the number of factors that an integer has.

I then asked students to find the greatest common divisor for three different pairs of numbers. Students typically made factor trees and used these to find the gcd. We shared out results to make sure everyone was in agreement.

Next I asked students to determine the prime factorization for all of the numbers used. We looked at the prime factors and tried to make connections back to the gcd of each pair. Students recognized that the gcd was the product of all the common factors.

I asked students to pick two numbers, one a two digit number and one a three digit number and see if this worked. Students worked through their pairs and found this was true. The question is whether or not this would always work?

This problem lends itself to illustrating why proof is so important. We found a simple, convenient way to find a greatest common divisor of two integers and would like to be able to use it with confidence. Without proof, we could use the process but then would need to verify that the value we calculated was, in fact, the greatest common divisor. If this result were proven true for all integers then  we would not have to confirm the result each time.

I asked students to consider how they could create an argument that this process would always work. I don't expect students to create a highly detailed, formal proof in a class like this, but I do expect students to be able to provide an informal argument that would basically provide the proof outline but may lack some detail required of a formal proof.

After allowing students some time to think about what they could say, I provided an informal proof similar to what I would expect students to present. The proof below includes italicized material that provides additional foundation for the proof but is not something I would expect the typical student to provide,which is bolded.

Greatest Common Divisor Conjecture: The greatest common divisor q of two integers n and m is equal to the product of all the common prime factors of n and m.

We will make use of the previous theorem that every integer has a unique prime factorization and that if an integer a = bc and p|a then p|b or p|c.

First, let q be equal to the product of all prime factors that are common between n and m. Then q|n because n = qr where r is the product of all the primes that divide n but are not common to m. By definition, this means q|n. Similarly we see the q|m.

We have now shown that q divides n and m. Is there any number s such that s > q and s|n and s|m? For this to happen, s would have to be a product of prime numbers that appear in both n and m and not contain any primes that do not appear in both, otherwise s would not divide into either n or m. Since s can only contain primes that are factors of both n and m and q contains all of these primes, s <= q. Therefore q is the largest integer that divides both n and m and is, therefore, the greatest common divisor of n and m. Q.E.D.

Students needed some time to absorb the argument but many started to see how the logic tied the concepts together to demonstrate the truth of the conjecture.

Class concluded with students summarizing in their notes what they learned today.

Visit the class summary for a student's perspective and to view the lesson slides.