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

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

Does this help?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search