# Homework Help: Southeastern Massachusetts Conference Math League: Set theory, gcf,lcm

1. Oct 29, 2013

### RubixRevenge

1. The problem statement, all variables and given/known data
2.) if jimmy piles his baseball cards in stacks of 4, then there is 1 left over. if he piles them in stacks of 7, there are 4 left over. If he piles them in stacks of 9, there are 6 lefty over. If he piles them in stacks of 10, there are 7 left over. compute the smallest amount of baseball cards Jimmy could own.

2. Relevant equations
maybe using LCM?

3. The attempt at a solution

I spent 1 hour trying to figure out the solution and the only things I could figure out were that the ones digit has to be 7. I spent the rest of my time testing numbers with my calculator.
However, if this was the actual competition, I wouldn't have a calculator and I would only have 3-4 minutes to solve it. so I have no clue.

Last edited: Oct 29, 2013
2. Oct 29, 2013

### Dick

There are systematic ways to do this. See for example, http://en.wikipedia.org/wiki/Method_of_successive_substitution. There's also http://en.wikipedia.org/wiki/Chinese_remainder_theorem for the case where your pile sizes are relatively prime (which yours aren't). To do it in 3-4 minutes without a calculator would probably take a lot of practice, and accurate arithmetic, but I'm guessing there are people would could do that.

3. Oct 29, 2013

### bigfooted

This one is special. If you would never have any cards left (so you can pile them in stacks of 4,7,9,10), you would multiply the stack numbers: 4*7*9*10=2520
but note the sequence:
4 -> 1
7-> 4
9-> 6
10->7
You are always 3 cards short for the next stack!

4. Oct 29, 2013

### Dick

Ooo. That's clever. So n=(-3) is an obvious solution. And you can add the product to get another. But that's not going to give you the smallest solution. I think you want an LCM instead of the product.

5. Oct 30, 2013

### bigfooted

2517 is the smallest number of cards: 4*7*9*10 - 3

6. Oct 30, 2013

### Dick

Really? Then why does 1257 cards work as well?

7. Oct 30, 2013

### bigfooted

Yes, you're right, my mistake. But I don't know how you can see that actually 4*7*9*10/2 - 3 is the minimum.

8. Oct 30, 2013

### Dick

All that matters is that 4, 7, 9 and 10 divide the number you are adding to -3. So the smallest number to add is the least common multiple of 4, 7, 9 and 10. Which is only their product if they are relatively prime.

9. Oct 30, 2013

### Office_Shredder

Staff Emeritus
bigfooted, that's because if there were always zero cards left over you would want the least common multiple of 4,7,9 and 10, you wouldn't just multiply them all together.

10. Oct 30, 2013

### bigfooted

Yes, I see that you shouldn't simply multiply because 4 and 10 are not prime. So when a and b are both divisible by 2, then the LCM is a*b/2? And when a and b are both divisible by prime p, then the LCM is a*b/p? And the LCM of a*b*p1*p2*p3 with prime numbers p1,p2,p3 is a*b/2*p1*p2*p3?

11. Oct 30, 2013

### Office_Shredder

Staff Emeritus
12. Oct 30, 2013

### Dick

No, it's not quite that simple. 4 and 8 are both divisible by 2 but LCM(4,8)=8, not 4*8/2=16. Maybe it would be simplest just to look at http://en.wikipedia.org/wiki/Least_common_multiple

13. Oct 30, 2013

### bigfooted

True, but it works when a and b have only two prime factors with multiplicity 1, and in your example, 8 has multiplicity 2. For multiplicity 2 you have to divide by 2^2:
LCM(4,8)=4*8/2^2=8

I see in your wiki link that I should just multiply the prime factors with the highest multiplicities, so
LCM(4,7,9,10)=LCM(2^2, 7, 3^2, 2^1 * 5) = LCM(4,7,9,5) = 4*7*9*5=1260

OK, that makes sense now.