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:

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

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 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, 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 1997-09-15; last update 2021-12-26      https://hhr-m.de/fact486