Wednesday, April 18, 2007

FUN with FACTORING: SAT-Type and Contest-Type Problems on Factors

[Important Note: Thanks to 'e', Question 1 below has been modified to 'five' 2-digit numbers with 12 factors. Please read the comments for follow-up.]

[The ideas and problems today are suitable for grades 6-12.]
Those into number theory know many basic principles that help them solve problems involving factors that seem arduous at first. One extremely useful formula that mathletes are taught early on and SAT students should know is the following (the abstract form hides how easy it is, so get to the example quickly!):

The FUN-damental FACTORING RULE: (I coined this silly name so don't quote me!!):
If the positive integer N = p1e1p2e2p3e3...pnen then
N has (e1+1)(e2+1)(e3+1)...(en+1) positive integer factors!

The pi's are distinct primes and the ei's are positive integer exponents.
Note: From this point on, whenever the term factor is used, it refers to a positive integer factor.

Ok, we need an example fast!

Example: How many positive integer factors does 48 have?
Solution: First we need to write the prime factorization of 48 = 2431
[For larger numbers, writing the prime factorization is more problematic and a computer program or a calculator like the TI-89 would be useful].
ADD ONE to each of the exponents and MULTIPLY: (4+1)(1+1) = 5 x 2 = 10. Voila!
Verify: 1,48; 2,24; 3,16; 4,12; 6,8. Ten, indeed!

The explanation of this very handy rule involves some basic combinatorial thinking since EVERY factor of 48 (similar argument for N, in general) can be written in the form 2a3b where a could be 0,1,2,3, or 4 and b could be 0 or 1. Thus, there are FIVE (4+1) possibilities for a and TWO (1+1) possibilities for b. By the multiplication principle, there would be 5 x 2 ways to form different factors of 48.

Ok, so here are some examples (not very challenging) for middle schoolers and on up:

1) Using our FUN-damental Rule above, find the five 2-digit positive integers which have exactly TWELVE distinct factors.
The object is not to list every number from 10-99 and count factors!
Extras: Explain why a 2-digit number cannot have more than 12 factors. What would be the smallest integer that has more than 12 factors?

2) How many factors does 2007 have?
[Easy, once you have the prime factors, but it's always fun finding them for each new year or showing it is prime. Students better know why 2007 is NOT prime!!].

3) SAT-type (easy using above rule): If N = pqr, where p, q and r are distinct primes, explain, without listing or plugging in numbers, why N has exactly eight factors.
Then list the eight factors in terms of p, q and r.

There are endless variations and applications of the FUN-damental Rule. I'll leave it my readers to suggest really 'wicked' ones!


Eric Jablow said...

How long do you think it will be before they realize that it's easier for a number to have 14 factors than it is to have 13 factors? Similarly, the smallest 15-factor number is less than the smallest 14-factor number:

2^{4}·3^{2} < 2^{7}·3 < 2^{12}.

Dave Marain said...

beautiful, eric!
I think you meant (2^6)(3^1) = 192 for 14 factors. Prime number of factors like 13 or 17 is definitely worth discussing. Now, how about 16 factors!

Answers for 12 factors:
6x2 leads to (2^5)(3^1) = 96
4x3 leads to (2^3)(3^2) = 72
3x2x2 leads to (2^2)(3^1)(5^1) = 60
(2^1)(3^2)(5^1) = 90
Thus, 60 is the smallest.

Eric Jablow said...

Sorry about that, Dave.

For 16 factors, let's try first the factorization 16=2·2·2·2. This leads to 2·3·5·7=210.

Let's see if we can do better. The factorization 16=4·2·2 leads to 2³·3·5=120. Somebody might figure out that it was smaller by writing it as 2·3·5·4, splitting the exponential and writing it like the previous factorization.

What about 16=4·4? This leads to 2³·3³ = 216. You've traded a 5 for a 3².

There's 16=8·2. This leads to 2^{7}·3 = 384. And the trivial factorization leads to 2^{15}=16384.

Eric Jablow said...

Oh, darn! 2^{15} = 32768. I should listen to The New Math aagin.

Eric Jablow said...

One final comment. Look at Sloane's sequence A005179.

e said...

Wait! What about (2^2)(3^1)(7^1)=84?
Factors are 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, and 84.

PS I love your site, and I use your ideas constantly.

eddi vulic

Dave Marain said...

thanks for the supportive comments! I hope my latest post won't offend anyone who thinks I'm 'selling myself out'! That could not be further from the truth - writing these posts are a great source of pleasure for me and the thought that someone out there appreciates these ideas is very gratifying.
Now for your result of 72! You are absolutely right - there are FIVE 2-digit integers with 12 factors. I forgot to include 7 as a prime factor - thank goodness others are more careful than I am.
Isn't it interesting that four of the five answers that have twelve factors are multiples of 12 themselves; 60,72,84,and 96. 90 is the exception since it is not divisible by 2^2.

Dave Marain said...

Notes on Question 3:
There are 8 factors for pqr using hte (Fun)damental Rule, however, it's instructive for students to see a list:
Do you see why I listed it like this?

Anonymous said...
This comment has been removed by a blog administrator.