Prime Numbers

pharmxanthan wrote:

Brian@VeritasPrep wrote:
2) Problem Solving in which they could ask you for the smallest prime factor of a factorial-plus-one (which will be greater than any of the factors of the factorial, based on that "rule" we just proved).

So, if we have to find the smallest prime factor of 10!+1, then the answer can not be 2,3,5, or 7? Can we find the smallest prime factor of 10!+1?

I'd just add a few comments to the posts above:

* The question in the original post is modeled directly after one found in the Official Guide, though the Official Guide question instead uses the range 13! + 2 to 13! + 13. These questions are based on an interesting feature of primes. Among small numbers we find a ton of primes (there are eight primes less than 20, for example). It is, however, possible to make a list of consecutive numbers as long as you like which contains no primes. For example, if you take the integers from 1,000,001! + 2 up to 1,000,001! + 1,000,001 inclusive, you get a list of a million consecutive integers with no primes anywhere.

* There's a question in GMATPrep that has been posted here many times that essentially asks about the smallest prime divisor of 50! + 1. As seen above, the smallest prime divisor of 50! + 1 must be greater than 50. It's one of the hardest questions in GMATPrep, but these facts from Number Theory are certainly tested on occasion on the GMAT.

* When Brian says above that 'I'm sure it's written down in some math book somewhere as a hard-and-fast "rule"', he's right, of course. The rule is often stated as follows (and this can occasionally be useful on the GMAT): The Greatest Common Divisor of two consecutive integers is always equal to 1. Brian gave a good explanation above of why this is true. So, using this rule, 50! and 50! + 1 cannot share any divisors (besides 1, of course), and since 50! is divisible by every prime less than 50, 50!+1 is divisible by *no* prime less than 50.

* Without a computer, it would be absolutely impossible to find the smallest prime divisor of 50! + 1 in any reasonable amount of time. It would also be time consuming to find the prime divisors of 10! + 1 -- it's just too big a number, and in most situations there are no fast ways to identify prime divisors, unless those divisors are very small (we can easily tell when we can divide a number by 2, 3 or 5 using divisibility tricks, but it's time consuming to work out if a large number is divisible by 43, say), so you could never be asked to identify the prime divisors of 10! + 1 on the GMAT. All you'd need to know is that this number cannot be divisible by 2, 3, 5 or 7.