5 digit factorization

[MattcAnderson]

Hi Math People,

My puzzle today is to factor the number 46423.

I would like to see how to use the fact that 7*11*13 = 1001 is related.

Regards,
Matt

[retina]

TF to ~60 appears to be adequate.

[Batalov]

LaurV recently mentioned that he'd invented this divisibilty test when he was in 7th grade. Well, he ...and perhaps, many others.

It goes like this:
1. you are given a large (for a human eye) number N, e.g. 20 or even 40 or 80 digits
2. you then split from right to left every three positions (in your case 46'423)
3. you add up all odd skip-every-other groups of digits (here, simply 46)
4. you add up all even skip-every-other groups (here, simply 423)
5. subtract smaller from the larger (here, you get 377)
6. Now you can test for divisibility for 7, 11 and 13 (377 doesn't divide by 7 or 11 but 13 divides it
7. Therefore, here, 7 or 11 do not divide N, but 13 does.
8. Divide out. (Here, the remainder is prime. You are done factoring!)

[S485122]

.

[LaurV]

Originally Posted by Batalov

LaurV recently mentioned ...

True, but quite complicate.
Because 1001 is multiple of 7, 11, and 13, subtracting it from your number won't change the divisibility to any of these 3 primes. Also, subtracting 10 times it, or subtracting 100 times it. So, you get rid first of 3003, remaining 43420, then get rid of 2002(0) remaining 23400 (you just imaginary shift the digits by 3 and subtract the smaller from the bigger, i.e. in 46423, 6 is bigger than 3, get rid of 3, you have 43420, then first 4 is bigger than 2, get rid of twos, you have 23400). So your problem is to find out if 234 is divisible with either 7, 11, or 13, and splitting it in 2 (easier to do it in your mind than all those additions) leaves 117 which you can immediately see that it does not split to 11 (it leaves a 7 residue, cutting the 11), nor 7 (cut the last 7, it leaves a 40, i.e. a 5 residue), but if you put 13 to it, it is 130.

edit: to be clear, when I saw your number I could tell, following the long story above, that is a multiple of 13, in less than half of a second (no joke). Learning which numbers to 1000 are divisible by 13 and 7 helps (for 11 there is the +/- trick). I don't really know them, but if I get a high number I try cutting out mentally everything which is bigger than 7, or applying the fact that 301 is multiple of 7 (as 1001-700), so you just cut out three times from the hundreds what you cut from the units, and for 13, it helps the fact that 299 is a multiple of 13 (cut out 300 how many you can, then add 1 for each cut). Therefore, you very fast get an odd number below 300, and there you either know the "table" or do some more additions/subtractions.