1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of unique integer factors

  1. Oct 14, 2014 #1
    1. The problem statement, all variables and given/known data
    A number divisible by both 16 and 15 is divisible by at least how many unique integers?

    2. Relevant equations
    Combination formula, nCk = n!/(k!(n-k)!)

    3. The attempt at a solution
    I found the prime factorization for 16 and 15, 2x2x2x2x3x5. A number divisible by 16 and 15 must be divisible by any combination of these prime factors. The repeated elements (the four 2's) are giving me trouble.

    I looked at just the factors 2x3x5 and summed the number of combinations that can be made with them (3C1+3C2+3C3) and got a total of 7. By hand, I wrote out the the number of possible combinations for 2x2x3x5 and got:

    2,3,5,2x2,2x3,2x5,3x5,2x2x3,2x2x5,2x3x5,2x2x3x5, which gives 11 total combinations. It looks like if I add another factor of 2 (2x2x2x3x5) then I will gain another 4 possible combinations, and 4 more for every additional "2".

    So, my solution is that there are 19 possible unique combinations and thus at least 19 unique integers that this number is divisible by. I'm not sure if that's right and I have no real intuition for why 19 (might) be correct. If the problem had asked for a number divisible by both 16 and 45 I'd be really lost (since there would now be repeated 3's as well as repeated 2's)!

    Is there a general solution to finding the number of combinations with repeated elements??
  2. jcsd
  3. Oct 14, 2014 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You forgot 1 will divide the number, so the total is actually 20 = 5x4. For each factor of 2 you add, you said you got 4 more combinations. Can you see why 5x4 makes sense?
  4. Oct 14, 2014 #3


    User Avatar
    Homework Helper

    I think your logic is right.
    You can do 3C1 (1+1/3*3) + 3C2(1+2/3*3) +3C3*(1+3/3*3) to handle the repeated elements. Should you count 1 as well?
  5. Oct 14, 2014 #4
    Ahh, I forgot 1!

    I can see that 2x3x5 gives me 8 combinations, which is the same as 2x4. For each "2" I add, I gain 4 combinations. Three 2's will give me 3x4. So then I have 2x4+3x4 = (2+3)x4 = 5x4. Right?

    I'm not very good at math to begin with, but this probability/counting stuff is impossible!

    Yep, I think that 1 should definitely be counted!

    I'm not sure how your suggestion for repeated elements works, I'm going to have to study that for a while :).

    Thanks for the help from you both!
  6. Oct 14, 2014 #5


    User Avatar
    Homework Helper

    My suggestion was clearly the less efficient. You have ( ways to choose 2's) x ( ways to choose 3 and/or 5) including not choosing any (=1).
    I was saying that for each n, 3Cn gives you how many ways to choose from the three. Multiply the portion that contains a 2, (n/3) by 3 to get the additional 3 options for multiple 2s.
    In general ##\sum_{i=0}^3 3Ci (1+ i)##.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted