Analyzing Prime Factors

Date: 06/14/2007 at 10:32:42
From: Nancy
Subject: factors

Is there a number with the only 3 prime divisors 3, 5, 7 and that has
a total of 18 divisors?

I have squared the prime numbers and have used the combinations of
prime numbers to find factors/divisors, but I come up with 19 divisors.

Date: 06/14/2007 at 12:28:44
From: Doctor Ian
Subject: Re: factors

Hi Nancy,

Suppose we have

  3 * 5 * 7

How many divisors can we get?

  1                       Choose none

  3, 5, 7                 Choose one

  3*5, 3*7, 5*7           Choose two

  3*5*7                   Choose all

So those are all the possible factors.  Do you see why?  Now, suppose
we duplicate one of them:

  3^2 * 5 * 7

Then we get these factors:

  1                       Choose none

  3, 5, 7                 Choose one

  3*3, 3*5, 3*7, 5*7      Choose two

  3*3*5, 3*3*7, 3*5*7     Choose three

  3*3*5*7                 Choose all

In this way, you can systematically search the space by trying
different exponents:

  3^2 * 5 * 7    ->    3^2 * 5^2 * 7   ->   ...   

   |
   v

  3^3 * 5 * 7    ->    3^3 * 5^2 * 7   ->   ...

   |
   v
  
  3^4 * 5 * 7    ->    ...

   |
   v

  3^5 * 5 * 7    ->    ...

   |
   v

  3^6 * 5 * 7    ->    ...

Note that you never have to consider a case where a larger exponent
follows a smaller one, e.g., 

  3^2 * 5^3 * 7^2

Do you see why?  

Anyway, at some point, one of two things will happen.  Either you'll
find the set of exponents you're looking for; or all your exponents
will be so big, you'll get more than 18 factors.  In the latter case,
you've proved that no such set of exponents exist.  Either way, you
win...and that's the whole point of a systematic search like this. 

Does that make sense? 

Note that you can change the form of the problem, without changing the
underlying meaning, and that can help you think about it in a
different way.  For example, suppose I have two red balls, two blue
balls, and one green ball in a jar, and I want to pick a subset of the
balls from the jar.  How many distinct outcomes are possible?

  rrbbg   ->   [nothing]               Choose none
               r, b, g                 Choose one
               rr, rb, rg, bb, bg      Choose two
               rrb, rrg, rbg, ...      Choose three
               ...                     Choose four
               rrbbg                   Choose five

  Note that the '[nothing]' case corresponds to a divisor of 1
  in the original formulation of the problem. 

Once you see it this way, you might find that you can use formulas
like the ones here, 

  Permutations and combinations
    http://mathforum.org/dr.math/faq/faq.comb.perm.html 

to find your answer with less work. 

Does this help? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/