Saturday, March 8, 2008

Is 91 Prime?

Quick -- without looking it up, tell me: Is 91 prime?

Hard to say, isn't it? It looks fairly prime. It's odd; it's not divisible by 5 or 11 -- or 3 either...

In this article, I'd like to show to several ways to quickly factor numbers in your head, and even some hints for tricks to speed up number factoring for computer programs. Factoring numbers has many important applications, including RSA (which is used in SSL encryption on your web browser). For me, I like to use the process of factoring numbers as a way to memorize a number. By putting significance on a number (and by going through the process of putting significance on a number), it's easier to recall numbers.

But first, a little lead-in...

Cryptonomicon
In Neil Stephenson's Cryptonomicon, Lawrence Waterhouse shows his cryptographic prowess to some British World War II officers while discussing Special Detachment 2701:
"Do you have any questions?" the Main Guy asks.
"Did Alan Choose the number?" [asks Waterhouse]
"You mean Dr. Turing?"
"Yes. Did he choose the number 2701?"
This level of detail is clearly several ranks beneath the station of the men in the Broadway Buildings. They look startled and almost offended, as if Waterhouse has suddenly asked them to take dictations.
"Possibly," says the Main Guy. "Why do you ask?"
"Because," Waterhouse says, "the number 2701 is the product of two primes, and those numbers, 37 and 73, when expressed in decimal notation, are, as you can plainly see, the reverse of each other."
All heads swivel toward the don, who looks put out. "We'd best change that," he says, "it is the sort of thing that Dr. von Hacklheber would notice." He stands up, withdraws a Mont Blanc fountain pen from his pocket, and amends the organizational chart so that it reads 2702 instead of 2701. As he is doing this, Waterhouse looks at the other men in the room and thinks that they look satisfied. Clearly, this is just the sort of parlor trick they have hired Waterhouse to perform.
This change sets in action one of the main subplots. You'll have to read the book to find out more (which I highly recommend).

Factoring Tricks
Most (mathematically inclined) people can quickly pick off the first several primes, just from memory: 2, 3, 5, 7, 11, 13, 17, 19, ... It's when you start getting past about fifty where things get a little sketchy.

Here are some tricks for factoring numbers by dividing by small primes.

2:
The first "trick" is to check whether the number is odd or even. If it's even (and not 2), then it's not prime because it is divisible by two.

5:
The next check is to see if the last digit is a '0' or '5'. If so, it's divisible by 5.

These first two tricks work because our numbering system -- decimal -- does some of the work for us. Since 10 is divisible by both 2 and 5, base 10 already computes the result in the last digit of dividing by 2, 5, or 10. If we used something like hexadecimal (base 16), then this trick wouldn't work for 5 -- it would only work for 2 (or 4 or 8). If we used base 12 (like American clocks do), then looking at the last digit would tell us whether the number is divisible by 2 or 3 (or 4 or 6) -- but not 5.

3:
The next trick is to add all the digits of the number, and see whether the result is divisible by 3. If so, then the entire number is divisible by 3. In our example, we can test 91 by adding 9 + 1 = 10 -- which is not divisible by 3.

Let's test 123456:
1 + 2 + 3 + 4 + 5 + 6 = 21 (= 7 x 3).
This process can be repeated, so to test 21 we have 2 + 1 = 3, which is divisible by 3.

This trick works because we're representing numbers in a base such that "base - 1" is divisible by three (10 - 1 = 9, which is divisible by 3 and 9). The process of adding digits works because we are subtracting 10 times the digit, but then adding 1 times the digit, for a net change of subtracting 9 times each digit. Take this example:

345 = [(3 * 100)] + [(4 * 10)] + [5]
sum of digits = 345 - (3 * 100) + 3 - (4 * 10) + 4
sum of digits = 345 - (3 * 99) - (4 * 9)
sum of digits = 12
Adding or subtracting multiples of 9 (or 99, or 999, ...) does not change the remainder when dividing by 9 (or by 3). That's basically why it's possible to add the digits of a number to test divisibility by 9 (or 3).

11:
Testing divisibility by 11 is pretty easy for two digit numbers: if the two digits are the same, then the whole result is divisible by 11. It's when the number gets larger that things get a little trickier.

The method I'd like to describe here for testing divisibility by 11 is to group the original number into pairs of digits starting from the right, and then add these pairs and check whether the sum is divisible by 11. If the resulting sum is in 3 (or more) digits, repeat the process until 2 digits are remaining and see whether the digits are the same.

Here's an example:
Is 13574 divisible by 11?
1 + 35 + 74 = 110 (add pairs)
1 + 10 = 11 (add pairs again)
11 is divisible by 11 -- therefore 13574 is divisible by 11
The reason why this trick works is the same basic reasoning as for the trick with 3 and 9. The difference is that adding pairs of digits is equivalent to subtracting a multiple of 100 (or 10,000, etc) from the original number, and adding back that value one time, for a difference of 99 (or 9999, etc). Since 99 = 3 * 3 * 11, the result still equals the original number, modulo 11 (or 3).

The same basic principle applies to larger groupings of digits in any base (binary, decimal, hexadecimal...). I'll get into more details in a subsequent article about how this can speed up factoring large numbers.

7:
For 7, the trick is to successively subtract twice the last digit from the other digits to the left. If you get a number that is divisible by 7 during any stage of this process, then the original number is divisible by seven.

Here's an example:
Is 8638 divisible by 7?
863 - 2*8 = 847 (subtract twice the last digit)
84 - 2*7 = 70 (subtract twice the last digit)
70 = 7 * 10, which is divisible by 7 -- therefore 8638 is divisible by 7
How about our original number?
Is 91 divisible by 7?
9 - 2*1 = 7 -- therefore 91 is divisible by 7 (91 = 7 * 13)

There you have it -- 91 is not prime.

Conclusion
It's unclear whether factoring will get you a hot date or the next promotion, but it will help keep your mind sharp and give you some memory tools, or best of all, the illusion that you too can have the cryptographic genius of Stephenson's Waterhouse. In the next installment, I hope to entertain my programming geek readers with a discussion of how to speed up the process of finding large prime numbers using a binary generalization of the methods for finding divisibility by 3 or 11. For the rest of you, I hope to have given you an amusing diversion before your boss notices that you're reading random blogs instead of doing real work. If you're caught, just ask your boss if 91 is prime... :)

31 comments:

  1. I'm pretty impressed, and thoroughly enjoyed that...

    ReplyDelete
  2. Hi! Neat analysis, but I had it quicker than that.

    Sure, 91 looks as if it could be prime, but the only factors that are possible are those less than 10, as 10^2 = 100. Dividing by the possible odd integers says 9 isn't it, and 7, well, yes 7 divides 91 evenly. Not prime.

    Sort of like 51. Is it prime? ^_^

    ReplyDelete
  3. 51 is not prime

    ReplyDelete
  4. 5 + 1 = 6, thus 51 can be divided by 3.
    51 = 60 - 9 = (20-3)*3 = 17 * 3.

    ReplyDelete
  5. An easier way for your example for 13574 to check if it is divisible by 11:

    13574 --> add up alternating digits
    1 + 5 + 4 = 10
    3 + 7 = 10
    So, this number is divisible by 11

    ReplyDelete
  6. 91 has another property that lets you know instantly that it's nonprime: it's the difference of two squares.

    91 = 100 - 9 = 10^2 - 3^3

    Since a^2 - b^2 = (a+b)(a-b), the difference of two squares is always nonprime. This also gives us the factors of 91: (10+3)(10-3).

    Of course, 91 was easy to identify as the difference of two squares because one of the squares was 100. It's not as easy to see in a number like 133.

    ReplyDelete
  7. Nice little article. You missed one big tip -- not sure if it is a "trick" or not, but it's worth noting that you never need to evaluate a number for prime factors that are larger than the number's square root.

    In your '91' example, the square root of 81 is 9, the square root of 100 is 10, so the square root of 91 is somewhere between there. The largest prime number less than 10 is 7 ... so for 91, you do not even need to consider 11, 13, etc.

    Another example, 151. 13 squared is 169, so the square root of 151 must be less than that, so the largest prime that needs to be considered is 11.

    ReplyDelete
  8. sum of digits != 345 - (3 * 100) + 3 - (4 * 10) + 4

    sum of digits = 345 - (3 * 100) + 3 - (4 * 10) + 4 + 5

    ReplyDelete
  9. I'm stumped on the trick for 7. I actually figured out on my own very similar tricks for 3, 9, and 11, but I don't understand why the trick for 7 always works. Is there a simple explanation?

    ReplyDelete
  10. Nice article, but 91 is a triangle number so it isn't prime. It's also a hexagonal number (the difference between two cubes) AND the sum of two cubes.

    ReplyDelete
  11. 91 is not prime. 91 divides by both 7 and 13.

    You can test for primes pretty easily in Excel. :^)

    ReplyDelete
  12. Also, if you have a number abcdef, calculate ijk = abc-def.
    If ijk is divisible by 7,11, or 13, then abcdef is too - based on the fact that 1001=7*11*13.
    You can actually group a number into chunks of size 3, alternately add and subtract, and the same rule holds: if your end result is divisible by 7,11,13 then the original number is too.

    ReplyDelete
  13. The divisible-by-7 technique is clever -- I wasn't aware of it before -- but personally I find it easier to just do it the straightforward way, from left to right, in my head:

    Is 8638 divisible by 7? Subtract 7000
    Is 1638 divisible by 7? Subtract 1400
    Is 238 divisible by 7? Subtract 210
    Is 28 divisible by 7? It sure is.

    ReplyDelete
  14. Hi Plex (and JM),
    This is how the divisibility by 7 works: write your number n as n = 10a + b for b an integer from 0 to 9. Since -2 and 7 have no factors in common, n is divisible by 7 if and only if -2n = -20a -2b is. Since 21a is divisible by 7, you can add this to it, so this is also equivalent to a - 2b being divisible by 7.
    (mathematical explanation: -2 is the inverse of 10 modulo 7)

    Doetoe

    ReplyDelete
  15. @drdrang: The difference between two squares will not always be a composite number. The difference between any two adjacent squares n^2 and (n+1)^2 is always an odd number 2n+1. Every odd number is the difference between two squares, including odd prime numbers. For example, the prime 23 is the difference between 12^2 (144) and 11^2 (121). In this case (a-b) turns out to be 1.

    ReplyDelete
  16. Graham: the real question is "Is 57 prime?" :-)

    ReplyDelete
  17. If you want to get some practice in, try my game PrimeShooter.
    When 91 (or 57) comes at you, try shooting it with the "p" (for prime) bullet. It will ignore your bullet and keep coming at you.
    Actually, I did consider adding an advanced "Grothendieck" mode to the game, but this remains on my to-do list.

    ReplyDelete
  18. Check out the 37 factoring trick, it's really impressive

    http://www.flickr.com/groups/multiplesof37/discuss/72157594196046188/

    and it works!

    ReplyDelete
  19. @ drdrang

    91 = 100 - 9 = 10^2 - 3^3
    91 = 100 - 9 = 100 - 27 ?

    hmm, sup wit dat?

    ReplyDelete
  20. This is like the scientific clock post all over!

    I believe the answer is 42? Isn't that what Douglas Adams taught us?

    Here... kill your time with this one. Much easier.

    Top 10 Awesome Websites That Sell Cool Products You Probably Have Never Visited But Need To.

    http://www.comember.net/blogs/firepixel/

    ReplyDelete
  21. More tricks (4,8,9,25):

    4:

    If the last 2 digits of a number are divisible by 4, then the number is divisible by 4.

    Example: 148 -- 48 is divisible by 4

    8:

    If the last 3 digits of a number are divisible by 8, then the number is divisible by 8.

    Example: 9168 -- 168 is divisible by 8

    9:

    If the digits add up to a number divisible by 9, then the number is divisible by 9.

    Example: 78885 -- 7 + 8 + 8 + 8 + 5 = 36, which is divisible by 9

    25:

    If the last 2 digits are 00, 25, 50, or 75.. it is divisible by 25.

    Example: 450 -- last 2 digits are 50

    Combinations:

    You can get easy checks for 6, 12, 14, 15, 18, 21 by combining other simpler checks

    ReplyDelete
  22. Fantastic. The beauty of mathematics!

    ReplyDelete
  23. * Although the divisible by seven (7) test is not well known (especially compared to the popular divisible by three (3) test), there is an easy way to test if a natural number is evenly divisible by seven (7). See also Divisibility rule.

    1. Remove the last digit,
    2. Double it, and
    3. Subtract it from the remaining digits.
    4. If the result is negative and there are 2 or more digits, drop the negative sign.
    5. Repeat until you end up with a result that is a multiple of seven (7). (i.e. -7, 0, or +7)

    For example, the number 1358 is evenly divisible by seven, since:

    135 - (8*2) = 119
    11 - (9*2) = -7

    Using Number Theory the proof is rather simple, once the number n is rewritten in the form:

    n = 10a + b

    Where:

    a is the remaining digits, and
    b is the last digit.

    Then:

    10a + b = 0 (mod 7)
    5 * (10a + b) = 0 (mod 7)
    49a + a + 5b = 0 (mod 7)
    a + 5b - 7b = 0 (mod 7)
    a - 2b = 0 (mod 7)

    ReplyDelete
  24. Hello,

    Divide by 91 was the topic of my first video. I teach this to my MathCounts team. The goal is to beat the calculator. I call it Club 91. Just thought I would share this.

    Kevin

    www.siyensya.com

    ReplyDelete
  25. Checking divisibility by 11 is easier by adding and subtracting alternate digits. For 12345, you compute 1-2+3-4+5. If the result (3 in this case) is zero or a multiple of 11, the original number is divisible by 11.

    ReplyDelete
  26. Anonymous #1: Yes, of course if (a-b)=1 then (a+b)(a-b) might be prime. Good catch; I wasn't thinking of the degenerate case.

    Anonymous #2: It was obviously a typo. Should have been

    91 = 10^2 - 3^2

    ReplyDelete
  27. There's an interesting trick I found for (working toward) factoring numbers of 4 digits (or more) and it's based on 91 not being prime.

    91*11 = 1001
    7*11*13 = 1001

    Thus, if you have any 4 digit number abcd (where a,b,c,d are single digits), you can simplify it sigificantly by subtracting either a00a or d00d, whichever is less, leaving bc(d-a) or (a-d)bc0. In the case of (a-d)bc0, you can divide by 10 to get the 3 digit number (a-d)bc.

    If a=d, you get a 2 digit number to work with (well bc0, but you can divide by 10).

    In any case, you have turned a 4 digit number into at least a 3 digit number and can quickly test that 3 digit number for factors of 7,11 and 13.

    Also, you don't have to actually add the digits to check for divisibility by 3, just throw out 3s (and multiples of 3). For example, is 3240184320741 divisible by 3? throw out 3,24,18,432,741 leaving no more digits. Not all are this easy, but you get the idea.

    ReplyDelete
  28. Much of this is based off of the Euclidean Algorithm. (which actually isn't an algorithm, but is still called that) Everyone is coming up with their own tricks when this has already been around for hundreds of years...

    ReplyDelete
  29. This comment has been removed by a blog administrator.

    ReplyDelete
  30. pretty and nice issue.. thank you.

    ReplyDelete
  31. Wonderful. Thank you very much.

    ReplyDelete

Note: Only a member of this blog may post a comment.