# Number theory: Which one of the following numbers is prime?

Here is a quite basic high-school problem that I couldn't solve.

So I was working through past papers from a competition I have been selected to go to, and here is the problem:

Which one of the following numbers are prime:

A. 999973          B. 414577         C. 249951          D. 359919        E. 1000027


After a little bit of time, I figured that options $$C$$ and $$D$$ are definitely not the answer, as the numbers are divisible by $$3$$. This leaves us with choices of $$A$$, $$B$$, and $$E$$.

I tried seeing if the numbers satisfy the form $$6n\pm1$$ for some $$n$$, but all of them do, which make sense as none of the numbers are divisible by either $$3$$ or $$2$$.

I am left with the most stupid way I can find of doing this problem.

As we know, most of the numbers in options $$A, B$$ and $$E$$ are six-digit numbers, with exception to that of option $$E$$. This means that the numbers are mostly below $$1000^2$$. Thus, we know from the characteristics of prime numbers that as long as all of these numbers are not divisible by any primes less than $$1000$$, then it must be a prime. However, there are so many primes less than $$1000$$, and during the test, with roughly $$40$$ questions in $$45$$ minutes, it would be impractical and virtually impossible to test the divisibility of every prime and solve the problem.

Please tell me if there is an easier way.

Thank You.

• Incidentally, congrats for correcting the grammar of the question! Commented Oct 1, 2020 at 17:58

$$A$$ and $$E$$ are not prime because $$100^3\pm3^3$$ can be factored.

Since you have ruled out $$C$$ and $$D$$, that leaves $$B$$.

• $x^3+y^3=(x + y) (x^2 - x y + y^2)$ and $x^3-y^3=(x - y) (x^2 + x y + y^2)$ Commented Sep 15, 2019 at 13:59
• The fact that both $A$ and $E$ are on the list is a hint that suggests this approach. Commented Sep 15, 2019 at 13:59
• Wow. I'm so dumb. How do you get this sort of intuition? Commented Sep 15, 2019 at 14:00
• with experience, it's easy to recognize that $1000027$ is a sum of cubes Commented Sep 15, 2019 at 14:01
• @AaronyJamesys No, you are not dumb. Thinking in retrospect that some piece of mathematics is obvious is an occupational hazard in this profession. Commented Sep 15, 2019 at 14:09

Yes. @J. W. Tanner got it right.

Summing it up, we have:

Two crucial and basic steps for checking primes that are really large:

Step 1: Check for divisibility rules. Divide the number by $$3, 5, 7,$$ and $$11$$, and if any of them work, then the number is not prime

Step 2: Check if the number can be expanded as a form of a polynomial, such as $$x^2-y^2$$, or $$x^3\pm y^3$$. If it can, then it is not prime.