1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Incidentally, congrats for correcting the grammar of the question! $\endgroup$
    – chasly - supports Monica
    Oct 1, 2020 at 17:58

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
6
  • $\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, 2019 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, 2019 at 13:59
  • $\begingroup$ Wow. I'm so dumb. How do you get this sort of intuition? $\endgroup$
    – Aarony Jamesys
    Sep 15, 2019 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, 2019 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, 2019 at 14:09
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .