n! and prime numbers

[PetriF258]

I think I understand this correctly but would like to confirm. So, if the question states: "What is the smallest number that 21! is not a multiple of OR what is the smallest number that is not a factor of 21! OR what is the smallest number that 21! could be divided by that would result in a residual"

So 21! is actually 21x20x19....x3x2x1. This means that 1 - 21 are factors of 21!

Next, 22 is also a factor of 21! because 2 and 11 are both factors of 21!

So it must then be 23? The first prime after 21.

If this is correct, it would mean the answer for the same question but using 18! would be 19. I tried to test this on Excel but it doesn't work. If I divide 18! by 19 I get no residual?

Thanks

[danr969]

there must be some way to control the display in Excel, or there might be an explicit remainder (residual?) type of division operator. In any case, 18! divided by 19 has a non-zero remainder
of 18. This is not an obvious result, but similar, smaller examples
are 6! + 1 is divisible by 7. 10! + 1 is divisible by 11.
12! + 1 is divisible by 13. In your case

18! + 1 is divisible by 19, so 18! is 1 less than a multiple of 19.

I don't know any easy way to arrive at this result that doesn't use a lot of remainder properties, but the result itself is sometimes cited as "Wilson's Theorem"

[PetriF258]

First off, thanks. I think a better way to phrase to question would be: "What is the smallest integer that 18! could be divided by that would result in a non zero remainder".

With regards to your method, I am not sure that will always work. For example: 3! + 1 = 7 which is not dividable by 4. 5! + 1 = 121 which is not dividable by 6.

Maybe one of the instructors could comment whether my first thought process was correct? I see it as follows: Above the line I have 18x17x16x15....2x1 and below the line I have 19. There is nothing above the line (no combination) that would result in me being able to eliminate the 19.

Thanks again

[danr969]

My examples were of the form (p-1)! +1. This is always divisible by p when p is an odd prime. When p is not an odd prime we get your examples.
Certainly k! cant be divided by any prime larger than k. The question is which composite numbers larger than k do not divide into k!? Take 32! It can be divided by 33,34, 35, 36, but not 37, the first prime after 32. No factor of 32 can be larger than 16, so all the factors will be found in 32!
So, my conjecture is that the smallest number that cannot divide into k! is the smallest prime that is larger than k.
Perhaps an instructor could weigh in with a definitive reply.

[PetriF258]

Thanks Dan, I agree.

Another way of explaining it might be the "above the line, below the line" as mentioned earlier. In your example 32! is above the line. If we put the following numbers below the line, the numbers will cancel (i.e. be dividable), for example: 33 (3x11), 34 (2x17); 35 (5x7); 36 (2x18). All the numbers in brackets form part of 32!

As you mentioned, the first prime after 32 is 37, so I believe we are on the right track.

Regards

[PetriF258]

Dan, one more thing. You pose an interesting question in your 32! example. The question you pose is what is the largest non-prime number that is not a factor of 32! Here is my view on it.

All numbers from 33 to 64 will either be prime, or 2x(number in 32!). 65 (13x5); 66 (6x11); 67 (prime); 68 (4x17); 69 (3x23); 70 (7x10); 71 (prime); 72 (4x18); 73 (prime) and then 74 seems to be the smallest non-prime that is not a factor of 32!, and guess what, it is 2x37 (the first prime after 32).

Must give credit to Bunuel from GMAT club who answered a similar question.

How cool is that?

Regards

[RonPurewal]

Petri,

All numbers from 33 to 64 will either be prime, or 2x(number in 32!).

^^ This part isn't quite right. It should say "either (a) prime or (b) a product of numbers that are in 32!".
For instance, the number 35 is neither of the things you mentioned here. It's not prime, and of course it's not 2 times anything. But it's the product of 5 and 7, which are both in 32!.

I think you have this basic idea; it just wasn't written out correctly.

[RonPurewal]

How cool is that?

Regards

It's cool, but it's way, way, WAY beyond the bounds of anything you'd ever have to do on the GMAT.
Much too "mathematician-like" for this test.