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.


$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$.

| cite | improve this answer | |
  • $\begingroup$ $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)$ $\endgroup$ – J. W. Tanner Sep 15 '19 at 13:59
  • $\begingroup$ The fact that both $A$ and $E$ are on the list is a hint that suggests this approach. $\endgroup$ – Ethan Bolker Sep 15 '19 at 13:59
  • $\begingroup$ Wow. I'm so dumb. How do you get this sort of intuition? $\endgroup$ – Aarony Jamesys Sep 15 '19 at 14:00
  • 1
    $\begingroup$ with experience, it's easy to recognize that $1000027$ is a sum of cubes $\endgroup$ – J. W. Tanner Sep 15 '19 at 14:01
  • 2
    $\begingroup$ @AaronyJamesys No, you are not dumb. Thinking in retrospect that some piece of mathematics is obvious is an occupational hazard in this profession. $\endgroup$ – Ethan Bolker Sep 15 '19 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.