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
you 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 let's 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 multiset.
(The difference will be important as you get to more advanced math.) So the basic
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 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 multiset of prime factors. So (pf(45),2,5) means "multiset that includes
the primefactors 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
towared 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 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 greter 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 substitue 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 unly true because we are useing 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 one step or two (or more), 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 let's 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 abberivate 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 multiset 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 technicallly
true at all times. The reason we want this symbol is that we
know that is how you prove something is prime---your 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. Not 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 divisibilty 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 divisble 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 divisble 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 divisble by 31 (x3 and subtract rule for 31)}
    (nu(31,1709))
= { 170 - 99 = 71, not divisble 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.

I recommend this way of writing out your work. I think it works well for the child who will
have trouble factorizing 54, and well for the child factorizing 10254. I think it builds a goods 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 see factor trees suggested as a notation. Factor trees maybe useful for visualizing some things
but are not useful at all if one can't see the factors!