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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.