ADVERTISEMENT
  About the SA Blog Network













Roots of Unity

Roots of Unity


Mathematics: learning it, doing it, celebrating it.
Roots of Unity Home

91 Is April Fooling You

The views expressed are those of the author and are not necessarily those of Scientific American.


Email   PrintPrint



7 × 13 pieces of beach glass found on the shore of Lake Michigan and arranged on my coffee table.

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 ap -a is divisible by p. For example, 5 is prime, and 25-2=30, which is divisible by 5. And for that matter, because 2 is prime as well, we can flip it around. 52-5=20, which is divisible by 2.

Any non-prime number x that satisfies this property for some base number a, that is, ax-a is divisible by x, is called a Fermat pseudoprime to base a, and 91 is the smallest Fermat pseudoprime to base 3. You’re not going to be able to verify it on your calculator because 391 has 44 digits, but 391-3 is divisible by 91. (But you can check it on Wolfram Alpha if you think I’m trying to pull an April Fool’s prank on you.)

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.

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

The views expressed are those of the author and are not necessarily those of Scientific American.





Rights & Permissions

Comments 2 Comments

Add Comment
  1. 1. pseudoprime 10:54 am 04/1/2013

    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 this
  2. 2. Evelyn Lamb in reply to Evelyn Lamb 2:58 pm 04/1/2013

    Clever. 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

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

More from Scientific American

Scientific American Special Universe

Get the latest Special Collector's edition

Secrets of the Universe: Past, Present, Future

Order Now >

X

Email this Article

X