20160224, 05:13  #1 
"Matthew Anderson"
Dec 2010
Oregon, USA
1756_{8} Posts 
5 digit factorization
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 
20160224, 05:28  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6324_{10} Posts 
TF to ~60 appears to be adequate.

20160224, 06:07  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·29·167 Posts 
The famous divisibilty test for 7, 11 and 13 at once
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 skipeveryother groups of digits (here, simply 46) 4. you add up all even skipeveryother 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!) 
20160224, 06:09  #4 
"Jacob"
Sep 2006
Brussels, Belgium
6EE_{16} Posts 
.
Last fiddled with by S485122 on 20160224 at 06:12 Reason: Sergey was quicker and much more didactic 
20160229, 08:57  #5 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23203_{8} Posts 
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 1001700), 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. Last fiddled with by LaurV on 20160229 at 09:08 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorization on 2^p +1  kurtulmehtap  Math  25  20100912 14:13 
Factorization of 7,254+  dleclair  NFSNET Discussion  1  20060321 05:11 
Factorization of 11,212+  Wacky  NFSNET Discussion  1  20060320 23:43 
160 digit factor found of 366 digit (PRP1)  AntonVrba  Factoring  7  20051206 22:02 
Factorization of 5,307  Jeff Gilchrist  NFSNET Discussion  7  20050223 19:46 