The Prime Factors Of 10⁴⁸⁶–1

by Helmut Richter

The number 10⁴⁸⁶–1 is the smallest number of the form 10^k–1 that is divisible by a prime p with the properties:

• p is coprime to 10–1.
• p does not divide 10^j–1 for any j < k.
• Not only p divides 10^k–1 but so does p².

The prime p above is 487, and the complete factorisation of 10⁴⁸⁶–1 is:

3⁷ × 7 × 11 × 13 × 19 × 37 × 163 × 487² × 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 10^k–1 for some smaller k. In the following table, for each p the smallest k is given so that p divides 10^k–1.

The factorisation was performed in 1997 on a 66 MHz 486 PC with the free program UBASIC written by Yuji Kida at Rikkyo University, using the ECM factorisation program (ECMX) which comes with UBASIC. It took about two days. The program had to be slightly modified 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, even 25 years later. Here, however, a lot of factors were known in advance: for each d that is one of the numerous factors of 486, 10^d–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.