Quick - is 91 prime?(balltech.blogspot.com)
balltech.blogspot.com
Quick - is 91 prime?
http://balltech.blogspot.com/2008/03/is-91-prime.html
11 comments
n1 - n2 == 0 or if n1 - n2 is divisible by 11
aka
if n1 = n2 (mod 11)
Cool trick.
aka
if n1 = n2 (mod 11)
Cool trick.
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...
Here's some more fun: http://www.jgc.org/blog/2008/02/sum-of-first-n-odd-numbers-i...
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.
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.
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.
Seven wasn't new to me, but I've never been able to remember it. Maybe I will this time.
Of course not: 91 = 100 - 9 = 10^2 - 3^2 = (10 + 3) * (10 - 3).
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?
http://www.spaceandgames.com/?p=27
Now how certain are you that 51 is prime?
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!
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!
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.
Actually you can construct a finite automate (= a rule) - that operates on the digits and checks for divisibility - for any fixed number.
That reminds me how great the Cryptonomicon is. Normally I read it every 24 months, I am about due another read again.
Why every 24 months?
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.
vedic mathematics offers similar numeric tomfoolery
[deleted]
No.
Maybe I'm weird, but I knew right away that 91 = 7 x 13. Apparently you felt the same way.
Definitely shouldn't have to resort to tricks to factor 91. The answer really jumps out (70 + 21).
[deleted]
Yes... no
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.
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.
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