29
$\begingroup$

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?

  • 0
    When I read the title first thing that came to my mind was [primality certificate](http://en.wikipedia.org/wiki/Primality_certificate). It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)2012-05-23
  • 0
    I believe that $\lfloor\sqrt{577}\rfloor = 24$...2017-05-13
  • 0
    @u8y7541 : Fixed. $23$ is not the "floor" of $\sqrt{577}$ but it is the "prime floor" of $\sqrt{577}. \qquad$2017-05-14

6 Answers 6