GMAT Math

mberkowitz wrote:what is the fastest way to figure out if a large number is prime in GMAT WORLD.

I know the things to look out for, namely

if square root end in integer, not prime
if ends in 0 2 4 5 6 8, not prime
if sum of digits is divisible by 3, not prime
dividing the number by all primes less than its square root, if divisible by a prime, it is not prime

just looking for a faster way, that requires zero thought.

thanks all.

If you find a fast way to do this, you'll win the equivalent of a Nobel Prize in mathematics. It is often easy to prove that a large number is *not* prime- for example, it's easy to see that none of the following is prime:

83,433 (divisible by 3)
83.434 (divisible by 2)
83,435 (divisible by 5)

but there is no fast way to prove that 83,437 *is* a prime. The 'square root test' that you mention is really the best you can do with pen and paper. You'd need to take the square root of 83,437 (which is roughly 290), then try dividing 83,437 by every prime less than 290. If you find that no prime smaller than 290 is a divisor of 83,437, you'd know that 83,437 must be a prime number (and it is prime, but I had to look at a prime number table to know that). Consider how much work is involved: there are 61 different primes less than 290, many of which you may not know (so you'd need to find them all first), and most of them are pretty awkward to work with. Even if it only takes 30 seconds to do each division test, you're looking at a problem that would take a half hour to complete. You could never be asked to do this on the GMAT, of course. If you are asked on the GMAT whether a large number is prime, it can't possibly be prime, because proving that a large number *is* prime is far too time-consuming. Proving that a large number is *not* prime is sometimes easy, however, as we saw above.

Proving that large numbers are prime, and factoring very large numbers, is, from a computational point of view, extremely time-consuming. It's for this reason that you sometimes see newspaper stories 'New largest prime number found'. It's also the reason that large prime numbers are the basis of much of cryptography, particularly that used on the internet.

Because these operations (factoring large numbers, and finding large primes) take so long to perform, they can be used to encrypt your email communications, your credit card details or your banking information when you send this data over the web. It's not that the codes used on the web are unbreakable; it's just that it would take so many millions of years for a computer to actually break the codes that they are for all practical purposes uncrackable. And as computing power increases, larger numbers can be used to keep pace.

So, while few people probably appreciate the fact, number theory may actually be the most important area of mathematics in our day-to-day lives. Without it, we wouldn't be able to use the internet the way we do.

[edit: made a small correction in the text quoted above- highlighted in red]