Prime Numbers

Pedros above has posted the most efficient way to check if a number is prime. In general, it is *very* time consuming to prove that a large number *is* prime -- so time consuming that you could never be asked to do it on the GMAT. It is, however, sometimes easy to see that a large number is *not* prime, and that is something you are occasionally asked to do on the test. So, for example, it is easy enough to see that none of the numbers

31,112
31,113
31,114
31,115
31,116

are prime; three of them are even, 31,113 is divisible by 3 (add the digits) and 31,115 is divisible by 5 (it ends in 5). However, it would take several minutes with pen and paper to work out whether 31,111 is prime (it is not, as it turns out; it is divisible by 53). The only way to check that is to start trying to divide it by small primes until you find a factor, and that takes ages; you don't have time to do that on the GMAT, so they can't ask you to do it. The only way the GMAT can ask you whether a large number is prime is if it is not prime, and in that case the number must have an 'obvious' factor like 2, 3, or 5, or a factor you can find using algebraic techniques, as in the following examples:

11! + 7 (since 11! and 7 are both multiples of 7, when we add them we must get a multiple of 7, so 11! + 7 is not prime)

13^9 + 13^2 + 13 (again, we are adding multiples of 13, so we must get a multiple of 13; 13^9 + 13^2 + 13 is not prime)

1003^2 - 1000^2 (this follows the 'difference of squares' pattern, so we can factor: 1003^2 - 1000^2 = (1003+1000)(1003-1000) = (2003)(3), so is not a prime number)