(Note that on the x-axis, only prime numbers are listed.)
Every whole number can be written in exactly one way as a product of prime numbers. For example 600 = 23*3*52.
When you multiple two numbers, the prime factorization of their product, can be obtained
by writing the prime factorization of each number, multiplying them, and combining groups
of the same prime number. For example 600 = 23*3*52, and
350 = 2*52*7, so 600 x 350 =
| (23*3*52)*(2*52*7) | |||
| = 23*2*3*52*52*7 | (by grouping together the 2's and the 5's | ||
| = 24*3*54*7 | (by using the fact that am*an = am+n) | ||
| = 210,000 |
From this, it's easy to see an important fact: A number X divides into a number Y, if the exponent of each prime number p in the prime factorization of X, is less than or equal to the exponent of p in the prime factorization of Y.
Proof: When we say that X divides Y, we mean, of course, that there is some
whole number Z such that X*Z = Y. Suppose you start out with, say, 74 in
the prime factorization of X, and 73 in the prime factorization of Y:
X = 23*3*74
Y = 32*73*112
Then we want to know if there is a number Z such that:
23*3*74 * Z = 32*73*112
But clearly this is impossible since no matter what the prime factorization of Z is,
there are at least four 7's on the left-hand side, so you cannot end up with three 7's on the
right-hand side. When X is multiplied by Z, the exponent of each prime factor can go up
or stay the same, but it cannot go down.
A Prime Factor Bar Graph (PFGB) is a term that I just came up with, so you won't find it in any math textbook. But it may make it easier to visualize certain concepts in number theory, such as counting the number of divisors that a number has, or finding the greatest common factor of two numbers.
I would usually not recommend using a PFBG in the middle of a competition to solve a question. They are more useful for visualizing why certain facts are true.
Define the Prime Factor Bar Graph (PFBG) of a number as a bar graph representing the
prime factorization of the number. For example, 600 = 23*3*52, so
the PFBG representation of 600 is given by:
(Note that on the x-axis, only prime numbers are listed.)
Statement 1: A number X divides a number Y if the PFBG of X "fits under" the PFBG of Y.
This is just another way of stating what we proved in the review section: for each prime number p, the exponent of p in the prime factorization of X, is less than the exponent of p in the prime factorization of Y.
We can use a PFBG of a number to more easily visualize the solutions to some number theory problems. For example: How many divisors does the number 600 have?
In terms of a PFBG, this question becomes: how many numbers are there whose PFBG representations
will fit underneath the PFBG of 600?
First of all, if a number N has a PFBG that fits under the PFBG of 600, obviously the PFBG of N has to be zero for every prime number other than 2, 3, and 5. The question is, what powers of 2, 3 and 5 can be in the prime factorization of N.
If the PFBG of 600 shows that the prime factor 2 has an exponent of 3, what exponents can the prime
factor 2 have in the PFBG of N?
In the PFBG of N, the
prime factor 2 can have an exponent of 0, 1, 2, or 3. (Remember, the exponent 0 is possible as
well.) Any one of those will give a bar graph in which the exponent of 2 "fits under" the
PFBG of 600. So there are 4 possibilities for the exponent of 2; the 4 possibilities are: 0, 1, 2, and 3.
Similarly, the PFBG of 600 shows the prime factor 3 has an exponent of 1. Thus, for the exponent of 3 in N, there are only 2 possibilities: 0 and 1. And finally, in the PFBG of 600, the prime factor 5 has an exponent of 2. Thus for the exponent of 5 in N, there are 3 possibilities: 0, 1, and 2.
So, in the prime factorization of N:
This is an example of a more general theorem:
Statement 2: Given a number X whose prime factorization is p1n1 * p2n2 * ... * pknk, the number of divisors of X is (n1 + 1)(n2 + 1)...(nk + 1)
Note that the number of divisors depends only on the exponents of each prime number, not on the prime numbers themselves. Thus 22*3*75 has the same number of divisors as 11*135*172, because the set of exponents is the same.
Statement 3: Given a PFBG representation of X and Y, the greatest common factor or g.c.f of X and Y is represented by the overlap (i.e. intersection) of the PFBGs of X and Y.
For example, suppose you wish to find the greatest common factor of 450 and 500. 450 = 2*32*52,
and 500 = 22*53. Consider the PFBG for 450, with the bars with diagonals slanting down and
to the left:
and the PFBG for 500, with the bars with diagonals slanting down and to the right:
Now combine them:
The overlap of the bar graphs (the criss-crossed areas) represents the number 2*52 = 50, and this
is exactly the greatest common factor of 450 and 500.
The reason this works is that any number which is a factor of X and a factor of Y, must fit under the PFBG of X and fit under the PFBG of Y. In other words, it must fit under their overlapping area. And the greatest such number is the number that constitutes the entire overlapping area.
(In non-PFBG terms, this means that to find the g.c.f. of two numbers X and Y, you can look at the prime factorization of each number, and for each prime number p, look at the exponent of p in X and the exponent of p in Y and take the lesser of the two. This gives you the prime factorization of the g.c.f. of X and Y. But this is an example of something that's easier to visualize and understand by using the PFBG!)
Statement 4: Given a PFBG representation of X and Y, the least common multiple or l.c.m. of X and Y is represented by the union of the PFBGs of X and Y.
For example, take the numbers 450 and 500 again and suppose you wish to find their lowest common multiple.
Observe their PFBGs again:
The union of the two bar graphs represents the number 22*32*53 = 4500. which
is indeed the l.c.m. of 450 and 500.
To see why this works, recall that X divides Z only if the PFBG of X fits under the PFBG of Z. So if X and Y both divide some number, then that number's PFBG must cover the PFBG of X and it must cover the PFBG of Y -- in other words, it must cover the union of the two graphs. And the smallest PFBG that covers the union, is the PFBG represented by the union itself.
(Again, we can express this statement in non-PFBG terms. To find the l.c.m. of two numbers X and Y, you can look at the prime factorization of each number, and for each prime number p, look at the exponent of p in X and the exponent of p in Y and take the greater of the two. This gives you the prime factorization of the l.c.m. of X and Y.)
There is a nice symmetry between the methods used to find the g.c.f. and the l.c.m. of two numbers:
| When finding the g.c.f. of X and Y | When finding the l.c.m. of X and Y |
| Look at the PFBGs of X and Y and take their intersection | Look at the PFBGs of X and Y and take their union |
| In non-PFBG terms, look at the exponent of p in the prime factorization of each number, and take the minimum | In non-PFBG terms, look at the exponent of p in the prime factorization of each number, and take the maximum |
Statement 5: Given the PFBGs of two numbers X and Y, the PFBG of their product is given by "laying the PFBG of Y on top of the PFBG of X".
For example, let X = 2*32*11 = 198, which would be represented
by the following PFBG:
and let Y = 3*54*7 = 13125, which would be represented by the following PFBG:
Then their product, 2*33*54*7*11, would be represented by this PFBG:
Note: Given the PFBG representation of X and Y, there is no relationship to the PFBG representation of X + Y, or X - Y.