The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   ->   ...   


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

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


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


  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 

to find your answer with less work. 

Does this help? 

- Doctor Ian, The Math Forum 
Associated Topics:
High School Number Theory
High School Permutations and Combinations
High School Puzzles

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.