I'd just add a few comments to the posts above:pharmxanthan wrote: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?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).
* 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.
