Quick - is 91 prime?

http://balltech.blogspot.com/2008/03/is-91-prime.html

by bdfh42 • 18 years ago

73 24 18 years ago

balltech.blogspot.com

jgrahamc• 18 years ago

Nice math hack. The 11 and 7 ones were new to me.

Here's some more fun: http://www.jgc.org/blog/2008/02/sum-of-first-n-odd-numbers-i...

staticshock• 18 years ago

7 was new to me too, that's an odd one

there's also another trick for 11 that comes from addition. 1234 * 11 = 12340 + 1234 = 13574 (or, by digit: 1 (1+2) (2+3) (3+4) 4). that makes 3 digit multiples easy to detect. for instance, 484: 8 is clearly 4+4, so it's divisible by 11 (440 + 44).

it's slightly more tedious for >3 digit numbers. for instance, 1353: from left to right: 3 = 1 + ..2, 5 = 2 + ..3. 3 == 3, so it'd divisible by 11. i guess i explained this somewhat poorly, sorry for that.

it's also somewhat harder if you have carries.

philh• 18 years ago

What I use for 11 is take the final digit, subtract the penultimate, add the third last, etc. The result = the original number (mod 11). Obviously it works if you start at the MSD, but then you need to worry about whether there's an even number of digits, in which case you need to negative the answer.

Seven wasn't new to me, but I've never been able to remember it. Maybe I will this time.

andr3• 18 years ago

No.

BrandonM• 18 years ago

Maybe I'm weird, but I knew right away that 91 = 7 x 13. Apparently you felt the same way.

andr3• 18 years ago

I actually figured 91 = 70 + 21 = 10 * 7 + 3 * 7

cstejerean2• 18 years ago

Definitely shouldn't have to resort to tricks to factor 91. The answer really jumps out (70 + 21).

hernan7• 18 years ago

Yes... no

cstejerean2• 18 years ago

For 11 there is an easier trick (or at least it's easier in that you can perform it in your head faster).

Starting from the left add every other digit => n1, Starting with the second digit add every other digit => n2

if n1 - n2 == 0 or if n1 - n2 is divisible by 11 then the number is divisible by 11. Example

13574

1 + 5 + 4 = 10

3 + 7 = 10

Since 10 - 10 == 0, the number is divisible by 11.

Even cooler example 155357548018579643

1 + 5 + 5 + 5 + 8 + 1 + 5 + 9 + 4 = 43

5 + 3 + 7 + 4 + 0 + 8 + 7 + 6 + 3 = 43

43 - 43 == 0, also divisible by 11

aston• 18 years ago

n1 - n2 == 0 or if n1 - n2 is divisible by 11

aka

if n1 = n2 (mod 11)

Cool trick.

aneesh• 18 years ago

hack? tsk tsk. if you get anything under 1000, it's probably quicker to subtract multiples of 70 until it gets to 2 digits - you should just memorize all the 2 digits multiples of 5,7,11,13, etc. Seriously, there aren't that many!

for example, here's a quicker way for 1353 than what staticshock posted. 1353 - 1100 = 253. and 253 - 220 = 33. And clearly 11 divides 33, so 11 divides 1353.

modular arithmetic ftw!

Novash2• 18 years ago

This is what I usually do. It is called "adding / subtracting tens", I believe.

tokipin2• 18 years ago

looks like the GCD algorithm

Novash2• 18 years ago

I knew those already. Studied those as curiosity on Algebra class. Up to 11, but there are rules for up to 17, as far as I know. By the way, took me three seconds to figure it was divisible by 7, using multiplication properties.

eru• 18 years ago

Actually you can construct a finite automate (= a rule) - that operates on the digits and checks for divisibility - for any fixed number.

curi• 18 years ago

the method for 7 works because:

you want to know if 8765 is divisible by 7. take the one's digit and multiply by 21. this gets a number that is divisible by 7 so you can subtract it. this will clear the last digit because we're subtracting this:

last digit * 1 + last digit * 20.

now we have a number that ends in a zero. in this case: 8660

now divide by 10. we can do that because that's dividing by 2 and 5 and that won't affect whether or not 7 can go into the number.

now we have a number to deal with that's at least one digit shorter. repeat until it's obvious if the remaining number divides by 7 or not.

tokipin2• 18 years ago

vedic mathematics offers similar numeric tomfoolery

michaelneale2• 18 years ago

That reminds me how great the Cryptonomicon is. Normally I read it every 24 months, I am about due another read again.

dmoney• 18 years ago

Why every 24 months?

michaelneale2• 18 years ago

yeah - should have picked a prime number. Just seems to work out that way - long enough for the details to get fuzzy so I want to read it again.

aoeuid• 18 years ago

This reminded me so much of a useful rationality anecdote, I almost thought it was going to be a link to it. Alas, it wasn't.

http://www.spaceandgames.com/?p=27

Now how certain are you that 51 is prime?

cperciva• 18 years ago

Of course not: 91 = 100 - 9 = 10^2 - 3^2 = (10 + 3) * (10 - 3).

Quick - is 91 prime?

Related Stories