Number of unique integer factors

[malachaipoos]

Homework Statement

A number divisible by both 16 and 15 is divisible by at least how many unique integers?

Homework Equations

Combination formula, nCk = n!/(k!(n-k)!)

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

 

[vela]

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?

 

[RUber]

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?

 

[malachaipoos]

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?

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!

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?

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!

 

[RUber]

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