The Prime Factors Of 10486-1

by Helmut Richter


The number 10486-1 is the smallest number of the form 10k-1 that is divisible by a prime p with the properties:

The prime p above is 487, and the complete factorisation of 10486-1 is:

37 * 7 * 11 * 13 * 19 * 37 * 163 * 4872 * 757 * 1459 * 9397 * 52579 * 69499 * 333667 * 2462401 * 67430557 * 70541929 * P10 * P11 * P15a * P15b * P18 * P24a * P24b * P27 * P138 * P144

where

 P10  = 2458921051
 P11  = 14175966169
 P15a = 440334654777631
 P15b = 676421558270641
 P18  = 456502382570032651
 P24a = 411361786890737698932559
 P24b = 610600386089858349939139
 P27  = 130654897808007778425046117
 P138 = 810316718654935254370114242173495345974018609204623064367629310709846283..
      ..851718998731856856949061264781563433202832207926987960406521712613
 P144 = 899718757349577828631761341730093220713822770643140264600436229195941807..
      ..849819816835925771559643276518390048146301688389176642719947087961896703

Some of these primes are factors of 10k-1 for some smaller k. In the following table, for each p the smallest k is given so that p divides 10k-1.

pk
31
76
112
136
1918
373
16381
487486
75727
pk
1459162
939781
5257918
69499486
3336679
246240181
67430557486
7054192954
P10162
pk
P1154
P15a27
P15b81
P18162
P24a243
P24b162
P2781
P138243
P144486

The factorisation was performed on a 66 MHz 486 PC with the free program UBASIC, using the ECM factorisation program (ECMX) which comes with UBASIC. It took about two days. The program had to be slightly changed in order to prevent it from doing primality checks for which the numbers involved would have been too large. Instead the necessary primality checks were done with the program APRT-CLE of the same package.

Factoring a 486 digit number is generally a hopeless endeavour. Here, however, a lot of factors were known in advance: for each d that is one of the numerous factors of 486, 10d-1 is a factor. This allows splitting the number into pieces of no more than about 170 digits. This is still too large, but the largest factors so found turned out to be the product of only two primes each, one of them about 30 digits long. Now a 30-digit factor can be found by the ECM method, and a 140-digit number can be proven prime by APRT-CLE. It this thus fair to say that the number could only be factored by good luck.


© Helmut Richter      published here 1997-09-15; last update 1999-12-28      /numb/fact486.html