Well, it turns out that 253 is not prime. Rather, 253=11(23). It also turns out that the proposition I wanted to use to show that 253 is prime is not true. Oops.
(I worked out the latter myself and then looked up the former.)
Today I’ve been reading more about primality tests, which is a complex topic. I found this page, which seems to give a fairly clear account of two of them. I’m going to have to review quite a few ideas in number theory to understand it, though.
Sounds like it was an interesting “oops!”
Yes, I had some fun trying to prove things that turned out not to be true.
A few things to think about:
– The smallest divisor of $n$ is always a prime $p\le\sqrt n$.
– So if $n=253$, then $p$ is one of 2, 3, 5, 7, 11, 13.
– 2 and 5 are obviously out.
– More interestingly, for any positive integer $m$, $m$ is a multiple of 3 iff the sum of the digits of $m$ is a multiple of 3.
– And $m$ is a multiple of 11 iff the alternating sum of the digits of $m$ is a multiple of 11.
– $2-5+3=0$ is a multiple of 11, so 253 is a multiple of 11.
To prove the stuff about 3 and 11, what you really want to show is that, say, the sum of the digits has the same remainder on division by 3 as the original number.
– Fermat and Miller-Rabin are way cool, but they’re also more machinery than you need here.
– The stuff about 3 and 11 might be interesting to think about without getting too involved.
As always, your blog is such amazing fun!
I used an argument in my post Elegance and Regret (linked on the Highlights page) that could be adapted to prove the rule for multiples of 3. I don’t think it’s the one you hinted at above, though. I was not aware of the rule for multiples of 11. I may look into proving that in the future.
I want to work through Fermat and Miller-Rabin, but I may have to wait until I am feeling a little more lively mentally.