April 1, 2013 | 2

Evelyn Lamb is a postdoc at the University of Utah. She writes about mathematics and other cool stuff. Follow on Twitter Evelyn Lamb is a postdoc at the University of Utah. She writes about mathematics and other cool stuff. Follow on Twitter

Rather appropriately, April 1st is the 91st day of the year, at least in non-leap years such as 2013. 91 might look innocent, but it’s a sneaky little number because 91=7×13.

That might not seem sneaky to you, but I’m here to tell you why it is. Every whole number can be broken down into some finite number of prime factors. For instance, 10=2×5, and 54=2×3×3×3. When you learn about factoring, you usually learn a few tricks to figure out a number’s factors. A number is divisible by 2 if it ends in an even digit, and by 5 if it ends in 0 or 5. And of course if a number’s digits add up to a multiple of 3, then the number is divisible by 3.

There is also an easy divisibility test for 11, although it’s a bit more involved than the tests for 2, 3, and 5. To test for divisibility by 11, first you alternate adding and subtracting digits of the number. The original number is divisible by 11 if the alternating sum of digits is divisible by 11. (This includes 0.) For example, 2013 gives us 2-0+1-3=0, so 2013 is divisible by 11.

I think of these tests as filters with different mesh sizes. Numbers are trapped by the 2 filter if they’re even and flow through if they’re odd. Then they go on to the 3 filter, where the multiples of 3 are weeded out, and so on. If a number is not prime, there’s a pretty good chance that the 2, 3, 5, or 11 filter will pick it out. Which means that it’s easy for me to be lazy and assume a number that passes through all four filters is prime, and in fact, that’s exactly what happens to me with the number 91. Except for squares, which many people, including me, have memorized up to 15 or 20 anyway, 91 is the first non-prime that makes it through all four of my filters. I call those numbers “fake primes” because I want to transfer responsibility onto the numbers rather than my imperfect factoring skills. 91 is especially fake because it is so small. As numbers get larger, there are more and more possibilities for factors, so I get less and less surprised when a composite number makes it through my filters.

I came up with the name “fake prime” for smallish numbers that aren’t divisible by 2, 3, 5, or 11, but in fact there is a real mathematical term for numbers that “look” prime. A *pseudoprime* is a number that satisfies some property that all primes satisfy, but isn’t itself a prime. Pseudoprimes are generally divided into different classes based on what properties they satisfy. I guess I could define a class called Lamb pseudoprimes as are all non-squares that aren’t divisible by 2, 3, 5, or 11, but most classes of pseudoprimes are quite a bit more sophisticated than that.

91 is a Fermat pseudoprime. This is the same Fermat of Fermat’s last theorem, and the pseudoprimes in question are related to what is called Fermat’s little theorem. That theorem states that if a number *p *is prime, then for any other number *a, *the number *a ^{p }-a* is divisible by

Any non-prime number *x* that satisfies this property for some base number *a, *that is, *a ^{x}-a* is divisible by

You can generate your own fake primes, or Lamb pseudoprimes, by finding any two or more prime numbers other than 2, 3, 5, and 11 and multiplying them together. It’s all fun and games with little numbers such as 91 and 119 (7×17), but they’re actually pretty serious business in the form of RSA encryption. That’s right, information you send over the Internet is often protected by souped-up fake primes! So maybe 91 isn’t trying to pull an April fool’s prank on unsuspecting algebra students—it’s just trying to keep your credit card safe.

Rights & Permissions

Add a Comment

You must sign in or register as a ScientificAmerican.com member to submit a comment.

Secrets of the Universe: Past, Present, Future

X
It is actually possible to verify it on a calculator. Since all you care about is the mod 3 value, only do part of the exponentiation, and when you get close to the limit on your calculator, take the remainder mod 3 before continuing. (Disclaimer: I do not actually own a calculator any more.)

Link to thisClever. Although I’m sure I would be very error-prone if I tried to do it that way! I have a calculator, and I even know where it is, but the batteries have been dead since at least the last time I moved. I use the Google calculator or Wolfram alpha when I need to crunch numbers.

Link to this