Primary Mathematics/Method for Factoring

A method of prime factorization for children

In math, the way you get to the correct answer is just as important as getting the right answer. Sometimes the way one gets the answer can be thought of a proof. People don't usually use the word proof when talking about arithmetic problems, but I think it is a good idea and good habit to get into. This is a method of doing prime factorization that constructs a proof that your answer is correct as you arrive at the answer. It keeps you from getting lost and shows your work. More importantly, I think it helps you understand the process. It starts out very easy, so that beginners can use it, but later on lets you skip some steps to save time.

The basic point of prime factorization is to take a number and find the prime factors. Since each prime factor may occur more than once, for example in the number 4, which has prime factors (2,2), we know that the factors of a number are not a set but a multi-set. (The difference will be important as you get to more advanced math.) So the basic way we are going to do our work looks like this:

   pf(X)
= { a reason we believe this}
   (a list of factors)

For example, for the number 4, we could factorize it like this:

   pf(4)
= { 4 = 2 * 2 }
   (2,2)

This is a very simple proof, and also represents what is sometimes called "showing our work" or our "scratch paper". Learning math is often about learning the language and symbols of math, and we need to do that now.

I use the symbol pf(X) to mean "the prime factors of X". I use a comma list of numbers of "pf(X)" symbols between parentheses to mean a multi-set of prime factors. So (pf(45),2,5) means "multi-set that includes the prime-factors of 45 and the prime number 2 and the prime number 5".

Now, for doing prime factorization, we are only going to allow certain reasons to go from one step to the next toward the answer. For example, "my friend Harold said so" is not a good reason.

The first reason that we will allow is a simple multiplication equation of the form x = y * z. In particular, we are allowed to do this:

   pf(x)
= { x = y*z }
   (pf(y),pf(z))

so long as the equation x = y* z is true (and y and z are both greater than 1, otherwise we'd be going in circles!)

The second rule that we are allowed to use is to replace pf(x) with (x) if we know for sure that x is a prime. For example, you should probably memorize the first ten primes: (2, 3, 5, 7, 11, 13, 17, 19, 23, 29), so it's OK to go from substitute the number 23 for pf(23), since we should know by heart that 23 is prime. When we do this, we give the reason "23 is prime".

Finally, we need to note that ((X)) = (X), no matter what X is, so we never need to write parentheses inside parentheses (this is not true of multiplication, it is only true because we are using parentheses to mean something special).

So let's do an example:

   pf(4)
= { 4 = 2 * 2 }
   (pf(2), pf(2)
= { 2 is prime}
   (2,2)

So, in this example, we've chained together two steps, with a reason for each one that is very simple. This is a good idea when you are starting out. However, mathematicians also want to be efficient, so if you are sure of what you are doing, you could do two steps at once:

   pf(4)
= { 4 = 2 * 2, 2 is prime}
   (2,2)

Notice that whether we perform one, two, or even more steps, we are really creating an equation. If we drop out the intermediate steps, the result is pf(4) = (2,2), which is probably about what someone would want on a test.

Now let's do a harder one:

   pf(60)
= { 60 = 6 * 10 }
   (pf(6), pf(10))
= { 6= 2* 3, 10 = 2* 5 }
   (2,3,2,5)
= { commutativity of multiplication}
   (2,2,3,5)

Commutativity of multiplication is a rule that just lets us reorder the factors. It's nice to have them in order in our list, so we will often do that at the end. But that's a lot of writing, so we'll abbreviate it { com. of mult. } Also, notice that in the second step I dropped the unnecessary parentheses, instead of writing ((2,3), (2,5)).

Now let's do an even bigger one, that's still easy, since the prime factors are all small, and it's easy to see the factors.

   pf(450)
= { 450 = 45 * 10 }
   (pf(45), pf(10)}
= { 45 = 5 * 9, 10 = 2 * 5 }
   (5,pf(9),2,5)
= { 9 = 3 * 3 , com. of mult.}
   (2,3,3,5,5)

Now we see a way in which we could have made a mistake --- if we forgot that 9 is not prime and had written (5,9,2,5). Hopefully we would have noticed, but we need to be careful!

When the factors aren't obvious

I think this is a nice method when the factors are easy to see. But unfortunately, sometimes they aren't easy to see at all, and we need a new symbol for expressing our work in that case.

Consider the number 143. Is it prime, or does it have factors? Well, its not obvious. The basic approach to finding any factor, or proving that a number is prime, is to start at the first prime (the number 2) and see if it is a factor. By going systematically up through each prime, we either find a factor or reach a prime that is bigger than the square root of the number, in which case we know the number is prime.

However, this is sometimes a big job, and we would really like to show our work in a way that helps us keep track of where we are and also can be quickly checked over to make sure we haven't made any mistakes.

The way we can do this is with the symbol nu(X,Y), which means "the multi-set of prime factors of Y, understanding that none of the numbers up to and including X evenly divide Y". I'm thus using the "not divisible up to" function nu both to help remember what has already been checked, but I've defined it so that my equation remains technically true at all times. The reason we want this symbol is that we know that is how you prove something is prime---you prove nu(sqrt(Y),Y), and then you know Y is prime. For example, if you know nu(13, 123), you know 123 is prime since 13*13 > 123. We can introduce nu(2,X) with the reason { X is not even}. If we know nu(2,X), then we can introduce nu(3,X) with the reason { sum of X's digits not divisible by 3 }.

So let's try this:

   pf(143)
= { 143 is not even }
   (nu(2,143))
= { 1+4+3 not divisible by 3 }
   (nu(3,143))
= { 143 doesn't end in 5 }
   (nu(5,143))
= { 143 / 7 = 20 and 3 / 7 }
   (nu(7,143))
= { 143 / 11 = 13!!}
   (11,pf(13))
= { 13 is prime }
   (11,13)

So that is our answer. Now in this case, we had to use a reason that we derived by division: 143/ 7 is not a whole number, but 20 and 3/ 7s. And, we were surprised to learn that 11 evenly divides 143. Let's try an even harder one. (Note, I am using the divisibility test from the Dr. Math website: http://mathforum.org/dr.math/faq/faq.divisibleto50.html rather than doing division for many of these divisibility tests at noted, but if I had to do it on a test, I would use division, since I don't have those rules memorized.)

   pf(1709)
= { not even, doesn't sum to 3, doesn't end in 5 }
   (nu(5,1709))
= { 170+45 = 215, not divisible by 7 (x5 and add rule for 7) }
   (nu(7,1709))
= { 1709/ 11 leaves 609, 609/ 11 leaves 59 (short division)}
   (nu(11,1709))
= { 170+ 4*9 = 206, 20+24 = 48 not divisible by 13 (x4 and add rule for 13) }
   (nu(13,1709))
= { 170-45 = 125, not divisible by 17 (x5 and subtract rule for 17) }
   (nu(17,1709))
= { 170+18 = 188, not divisible by 19 (x2 and add rule for 19)}
   (nu(19,1709))
= { 170+63 = 233, not divisible by 23 (x7 and add rule for 23)}
   (nu(23,1709))
= { 170+27 = 197, 19+21 = 40, not divisible by 29 (x3 and add rule for 29)}
   (nu(29,1709))
= { 170 - 27 = 143, 14 - 27 = -13, not divisible by 31 (x3 and subtract rule for 31)}
   (nu(31,1709))
= { 170 - 99 = 71, not divisible by 37 (x11 and subtract rule for 37)}
   (nu(37,1709))
= { 170 - 36 = 134, 41* 3 = 123 (x4 and subtract rule for 41) }
   (nu(41,1709))
= { 4*43 = 172, 3 * 43 = 129, 1720+129 = 1849, so by nu rule we are done!}
   (1709)

By systematically working our way up from 2 to the square root of the number, we can always keep track of where we are. For example, if we had started with 6 * 1709 = 10254, we would have ended up with:

   pf(10254)
= { even}
   (2,pf(5127))
= {5+1+2+7=15 = 3 * 5 }
   (2,3,pf(1709))
.....
   (2,3,1709)

and then the proof would proceed as it did above, carrying with it the prime factors 2 and 3 the whole time.

It is recommended that children use this method of writing out their work in order to build good habits that will pay off in algebra and other more advanced mathematical calculation, and introduces gently the all-important concept of the proof.

One sometimes sees factor trees suggested as a notation. Factor trees may be useful for visualizing some things but are not useful at all if one can't see the factors!