DonBoy
Let me say publicly that DonBoyâ€™s answer exudes a combination of intuitive genius and confidence that make me think DonBoy is going to do big things in his life. -- Steven D. Levitt (Freakonomics blog)
Friday, April 11, 2008

Nine is Prime, Nine is Prime, Nine is Prime

Convincing un-math from a Slashdot poster!

I read one of Marilyn Vos Savant's books, and in it she listed 9 as a prime...

But there's a more-than-50% chance that 9 is prime!

I test primeness by dividing the test-number by all integers, from 2 through the test-number's square root, looking for a zero remainder. So, first, I divided 9 by 2. I worked on this for a while, and ended up with a nonzero remainder. So far, 9 looks prime, and I've already tested half of the potential divisors! In fact, there's just one more potential divisor to try: the number 3. I'm almost done, and everything rides on this final calculation. There's a lot of uncertainty here.

What are the chances that 9 is just going to happen to be divisible by the very last potential divisor that I try? I'll grant you that the chances are non-zero; there really are some composite numbers out there. But the chances aren't one, either. For example, when I was testing 17 for primeness, the last potential divisor I tried was 4, and it didn't work. This last calculation could go either way.

So here we are, having tested half of the possible divisors, and so far 9 is looking prime and there's just one more divisor to test against. So, I ask you: do you want to bet 9's primeness/compositeness on this last calculation? I'll make it easier for you: I tell you right now, that 9 is just like 17, in that it is not divisible by 4. And then, I'll even give you an option: we can finish the calculation by dividing 9 by 3, or you can change your candidate divisor to 5, now that you know 4 doesn't work. Well.. what'll it be?

free website counter