# a big number that is obviously prime?

I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.

I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.

It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=\lfloor\sqrt{577}\rfloor$.

So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.

Are there any bigger primes than $577$ where this is so quick and simple?

• When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-) May 23, 2012 at 21:48
• I believe that $\lfloor\sqrt{577}\rfloor = 24$... May 13, 2017 at 21:51
• @u8y7541 : Fixed. $23$ is not the "floor" of $\sqrt{577}$ but it is the "prime floor" of $\sqrt{577}. \qquad$ May 14, 2017 at 16:19 ${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$

• I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that. May 24, 2012 at 15:08
• It answers the question, since its not very clear what is a 'big number' May 24, 2012 at 15:15
• All threes are equal, but some are more equal than others. May 25, 2012 at 1:35
• This is a big numeral, not a big number. :p
– user14972
Dec 1, 2012 at 19:08
• @Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/… Dec 1, 2012 at 19:31

We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $\lfloor\sqrt{677}\rfloor = 26$ so we need only check up to $23$.

As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $\lfloor\sqrt{977}\rfloor = 31$, we need only check up to $31$ so we are done.

• Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before. May 23, 2012 at 17:31
• I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy. May 23, 2012 at 17:36
• Are you suggesting that $100000000000003177$ is obviously prime? May 23, 2012 at 17:46
• Fair enough. If it gets too large I suppose it is a problem. May 23, 2012 at 17:52
• My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above. May 24, 2012 at 5:53

This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $\rm\:m = 10\:\!n \!-\! 3.\:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $\rm\:m\:$ to a sieve on an integer roughly $1/10\,$'th the size of $\rm\:m,\:$ namely $\rm\:n.\:$ Indeed, we have

Theorem $\$ If the positive integer $\rm\ m\: =\: 10\:\!n\!-\!3 < 841 = 29^2\:$ then

$$\rm 10\:\!n\!-\!3\ \ is\ prime\iff 3\nmid n,\ \: 7\nmid n\!-\!1,\ \: 11\nmid n\!+\!3,\:\ 13\nmid n\!+\!1,\:\ 17\nmid n\!-\!2,\:\ 19\nmid n\!-\!6,\:\ 23\nmid n\!+\!2$$

Proof $\$ Since $\rm\:m < 29^2,\:$ if it is composite it must be divisible by a prime $\rm\:p < 29,\:$ hence $\rm\:p \le 23.\:$ Consider, e.g. $\rm\:p = 13\:|\:10\:\!n\!-\!3\iff 13\:|\:10\:\!n\!-\!3\!+\!13 = 10(n\!+\!1)\iff 13\:|\:n\!+\!1,\:$ etc. $\ \$ QED

Your example $\rm\:577 = 10\cdot 58 - 3\:$ so the above primality test amounts to checking if any of the above $7$ primes divide $\rm\: 58\pm k,\:$ for $\rm\:k\le 6,\:$ which can be done very quickly mentally, as you did.

There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.

There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.

EDIT: Link to Primes at a glance mentioned above.

can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)

• $29 \mid 87$, so that reduces to two digits. May 23, 2012 at 20:47
• or subtracting 87 from 877 you'll get 790 which is not divisible by 29. May 23, 2012 at 23:59

How quick is quick enough?

$$n=1601$$. Let $$x=39$$. $$1601=40^2+1=40x+41=x^2+x+41$$ which, as is well known, is prime for integer $$0\leqslant x<40$$.

$$n=2081$$ obviously has the form $$x^2+5y^2$$ ($$x=9, y=20$$) so every prime factor of $$n$$ has an even tens-digit. Clearly not 3.

• 7: $$2100-n=19$$ and $$7\nmid 19$$.
• 23: $$2300-n=219$$; $$230-219=11$$ and $$23\nmid 11$$.
• 29: $$n+29=2110$$; $$211+29=240$$ and $$29\nmid 24$$.
• 41: $$n-41=2040$$; $$5\cdot 41=205$$ so $$41\nmid 204$$.
• 43: $$43^2$$ ends in 9; $$43\cdot 47=45^2-2^2=2021\ne n$$ and any other composite with smallest prime factor $$\geqslant 43$$ would be $$>n$$.