Bunuel wrote:
• Verifying the primality (checking whether the number is a prime) of a given number \(n\) can be done by trial division, that is to say dividing \(n\) by all integer numbers smaller than \(\sqrt{n}\), thereby checking whether \(n\) is a multiple of \(m<\sqrt{n}\).
Example: Verifying the primality of \(161\): \(\sqrt{161}\) is little less than \(13\), from integers from \(2\) to \(13\), \(161\) is divisible by \(7\), hence \(161\) is not prime.
A minor point, but the inequalities here should not be strict. If you want to test if some large integer
n is prime, then you need to try dividing by numbers up to and including \(\sqrt{n}\). We must include \(\sqrt{n}\), in case our number is equal to the square of a prime.
And it might be worth mentioning that it is only necessary to try dividing by
prime numbers up to \(\sqrt{n}\), since if
n has any divisors at all (besides 1 and
n), then it must have a prime divisor.
It's very rare, though, that one needs to test if a number is prime on the GMAT. It is, computationally, extremely time-consuming to test if a large number is prime, so the GMAT cannot ask you to do that. If a GMAT question asks if a large number is prime, the answer really must be 'no', because while you can often quickly prove a large number is
not prime (for example, 1,000,011 is not prime because it is divisible by 3, as we see by summing digits), you cannot quickly prove that a large number
is prime.
_________________
GMAT Tutor in Montreal
If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com