Discrete Math - Day 28

Today we started looking at prime factorization. This is familiar territory for most students but allows connections back to counting ideas and the greatest common divisor while setting the stage for the Euclidean algorithm to come.

The first step is to simply look at factoring some integers with the idea of seeing how many ways an integer can be factored into prime numbers. Students hopefully see that each integer only has one way to be factored into primes. This becomes a conjecture of interest, "There is only one prime factorization for an integer."

I asked students to consider how they could make an argument that would demonstrate the truth of this statement. This led many students to look at factor trees and to go through the idea of testing the conjecture. I pointed out to the class that testing is fine to show it works for specific numbers but that there are an infinite number of integers and how do we know that it will always work?

Students struggle with the idea of proof. What constitutes enough evidence to say something will always be true? The tendency is to check multiple situations and say it appears to work. I believe this is a remnant of how things are verified and checked in previous math classes. Justification is through testing. There isn't much attempt to provide evidence of a generalized nature that statements will always be true.

I provided a proof of prime factorization through contradiction. This proof relies on a lemma that if an integer n = ab and p|n then p|a or p|b. I didn't provide a proof of this lemma to the class but provided examples so they were clear about its meaning and treated this more as an axiom.

The proof I provided followed along the lines of assuming that an integer has two distinct prime factorizations designated by p's and q's. Without loss of generality you can assume there are more q's than p's. Clearly the first prime divides N and therefore must divide one of the q's. Continue repeating this process, exhausting all of the first p that are part of the factorization. Now repeat the process with the second p. Continue until there are no p's left. This results in the p-side equaling one. Since there were assumed to be more q's than p's we now have a series of q's multiplied together that equal one. Since the q's were assumed to be prime numbers this is a contradiction and therefore our assumption of having two different prime factorizations is false.

This is an important result. The knowledge that every integer can be factored into primes in only one way has ramifications throughout number theory and mathematics.

The next question posed is how many factors does any integer have and is there a way to determine this without having to list out all of the factors? Students explored several values: 10, 25, 120, 30, 24, and 33. I asked students to try to make connections between the prime factorization of a number and the number of factors it had. This investigation makes a connection back to the counting that students had been immersed in for the first several weeks of class.

Students made a little headway on this but were reluctant to be factoring values. What they noticed for the values provided were:

1. The odd numbers had four factors or less
2. The even numbers had four factors or more
3. The square number had an odd number of factors and the rest had an even number of factors

I told students they need to look at the first 500 integers and start to group and classify these integers based upon their prime factorization and how many factors they have. This is a homework assignment; I'll see if they find any additional patterns tomorrow.

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