## Factoring

When you think about it, the subject of prime numbers is really a subtopic under factoring--the process of breaking a number into its prime components. Every integer can be written as the product of a unique list of primes. For example the number 12  has the prime factors: 2*2*3. Notice that I repeated the number 2. When you multiply the prime factors together* you should get the original number.

Number Factored
2 2
3 3
4 2*2
5 5
6 2*3
7 7
8 2*2*2
9 3*3
11 11
12 2*2*3
13 13
14 2*7
15 3*5
16 2*2*2*2
17 17
18 2*3*3
19 19
20 2*2*5
21 3*7
22 2*11
23 23
24 2*2*2*3
25 5*5
26 2*13
27 3*3*3
28 2*2*7
29 29
30 2*3*5
31 31
32 2*2*2*2*2
33 3*11
34 2*17
35 5*7
36 2*2*3*3
37 37
38 2*19
39 3*13
40 2*2*2*5
41 41
42 2*3*7
43 43
44 2*2*11
45 3*3*5
46 2*23
47 47
48 2*2*2*2*3
49 7*7
50 2*5*5

The table to the right shows the prime factors for the integers between 2 and 50. By definition, every number is divisible by 1. It is customary not to list 1 as a factor. With this convention, the prime factors of a prime number has only one member: itself.

Each integer is represented by one and only one group of prime factors. Every group of prime factors produces a unique integer. Particular prime factors might be repeated in a number. For example 24=2*2*2*3. Some authors write the list of prime factors in the form 2n1 3n2 5n3 where n1 is the number of 2s,  n2 the number of 3s and so on. With this notation, the prime factors of 24 would be written 23*3, since the two is repeated three times.

If you multiply two numbers, the result will have all the prime factors of both the numbers. For example 6*5 will have the components 2*3*5. Squaring a number doubles the the prime factors. For example the square of 6 is 36. 6 has the prime factors 2*3. 36 has the factors 2*2*3*3. To cube a number, you triple the prime factors. 63 = 2*2*2*3*3*3.

The following table shows that taking a number to the nth power is a matter of multiplying the exponent by n.

6=2*3
62=22*32
63=23*33
64=24*34
...
6n=2n*3n

Conversely, we see that for a number to be of the nth power, the exponents of its prime factors must be divisible by n. We know that 24*52 is a square because the exponents of the prime factors are divisible by 2. We know that 33*52 is not a square because the the exponents of the prime factors are not divisible by 2.

Multiply sets of prime factors is extremely elegant. It is the simple matter of combining the prime factors. Division is the reverse of multiplication. When you divide number a by number b, you simply remove the prime factors of b from a. For example 24 has the prime factors 2*2*2*3. 6 has the prime factors 2*3. To divide 24 by 6, you simply remove the prime factors 2*3 from 2*2*2*3 leaving 2*2. 24/6=4.

Sometimes you don't have enough prime factors to complete the division and you end up with a remainder. For example if you tried dividing 24 by 9 you would find out there are not enough threes to complete the operation: (2*2*2*3)/(3*3) = (2*2*2)/3.

This should all look familiar. Prime factoring encompasses that exciting area of fractions that you learned in grade school Using prime factors you can figure out the least common multiple between numbers and all sorts of groovy stuff.

As you can imagine, it is possible to create an extremely interesting mathematical landscape just playing with exponents of prime factors. Of course, the main article in this web is about writing computer programs to generate prime look up tables.

Breaking primes into lists of prime factors may be fun, but is not terribly efficient. One way to save a little bit of disk space would be to simply record the lowest prime factor of a number. Having the prime factors listed in a table gives me the ability to quickly factor any number.

Let's say I had a number like 105. The lowest prime factor of 105 is 3. Dividing 105 by 3 yields 35. The lowest prime factor of 35 is 5. 35/5 = 7. The lowest prime factor of 7 is 7.

Doing this repeated look up shows me that prime factors of 105 are 3*5*7.