Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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=\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?

share|improve this question
    
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 ;-) –  dtldarek May 23 '12 at 21:48

5 Answers 5

https://mail-attachment.googleusercontent.com/attachment/?ui=2&ik=d860272f52&view=att&th=1377ee83b77f21fe&attid=0.1&disp=inline&realattid=f_h2ltntdx0&safe=1&zw&saduie=AG9B_P8uPzelpU1LhLRsIhOPqY2S&sadet=1337869307510&sads=h0-lBxxRSr2ieDrKqhhlK1j0axM ${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$

share|improve this answer
2  
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. –  Matt N. May 24 '12 at 15:08
8  
It answers the question, since its not very clear what is a 'big number' –  user1708 May 24 '12 at 15:15
15  
All threes are equal, but some are more equal than others. –  Gerry Myerson May 25 '12 at 1:35
2  
This is a big numeral, not a big number. :p –  Hurkyl Dec 1 '12 at 19:08
2  
@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/… –  Will Jagy Dec 1 '12 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.

share|improve this answer
    
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before. –  Michael Hardy May 23 '12 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. –  Eugene May 23 '12 at 17:36
5  
Are you suggesting that $100000000000003177$ is obviously prime? –  Robert Israel May 23 '12 at 17:46
    
Fair enough. If it gets too large I suppose it is a problem. –  Eugene May 23 '12 at 17:52
1  
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. –  Eugene May 24 '12 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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
2  
$29 \mid 87$, so that reduces to two digits. –  Michael Hardy May 23 '12 at 20:47
1  
or subtracting 87 from 877 you'll get 790 which is not divisible by 29. –  Keivan May 23 '12 at 23:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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