Suppose you want to factor a number of the form *b*^{n} – 1.

There is a theorem that says that if *m* divides *n* then *b*^{m} – 1 divides *b*^{n} – 1.

Let’s use this theorem to try to factor *J* = 2^{2023} – 1, a 609-digit number. Factoring such a large number would be more difficult if it didn’t have a special form that we can exploit.

Our theorem tells us *J* is divisible by 2^{7} – 1 and 2^{289} – 1 because 2023 = 7×17×17.

Is *J* divisible by (2^{7} – 1)(2^{289} – 1)? In fact it is, but this doesn’t necessarily follow from the theorem above because (*b*^{m }– 1) and (*b*^{n/m} -1) could share factors, though in this case they do not.

So we have

*J* = (2^{7} – 1) (2^{289} – 1) *F*

for some factor *F*. Now 2^{7} – 1 = 127, a prime. What about 2^{289} – 1?

By the theorem above we know that 2^{289} – 1 is divisible by 2^{17} – 1 = 131071, which turns out to be a prime. We can get a couple more factors of 2^{289} – 1 by consulting The Cunningham Project, a project that catalogs known factors of *b*^{n} ± 1 for small values of *b*. We learn from their site that 2^{289} – 1 is also divisible by 12761663 and 179058312604392742511009. All together

2^{289} – 1 = 131071 × 12761663 × 179058312604392742511009 × *R*

where

*R* = 3320934994356628805321733520790947608989420068445023

and *R* turns out to be prime.

So now we have five prime factors of *J*:

- 127
- 131071
- 12761663
- 179058312604392742511009
*R*.

That leaves us with *F* above, a 520-digit number. It would seem we’ve gotten all the mileage we can out of our factoring trick. But there’s something we haven’t tried: We know that *J* is divisible by 2^{119} – 1 because 7 × 17 = 119 is a factor of 2023.

Now

2^{119} – 1 = 127 × 239 × 20231 × 131071 × 62983048367 × 131105292137

and so these prime factors divide *J*. However, two of these, 127 and 131071, we’ve already discovered. But we do learn 4 more prime factors. So

*F* = 239 × 20231 × 62983048367 × 131105292137 × *G*

where *G* is a 492-digit number. We can tell by Fermat’s test that *G* is not prime, but I’m unaware of any clever technique for easily finding any of the factors of *G*.

***

In general factoring a 492-digit number is hard. There are RSA challenge numbers smaller than this that have not yet been factored, such as RSA-260, a 260-digit number. On the other hand, the RSA numbers are designed to be hard to factor. RSA-260 has two prime factors, presumably both the same order of magnitude. We get a little luckier with *G*. It has three relatively small factors that I was able to find:

*G* = 166684901665026193 × 3845059207282831441 × 153641005986537578671 × *H*

where *H* is a 436-digit number. I know from Fermat’s test that *H* is composite but I could not find any factors.

**Update**: From the comments, 2605053667526976413491923719 is also a factor of *G*. I’ve updated the code below accordingly. Now the unfactored part *H* is a 408-digit number.

***

Here’s Python code to verify the claims made above.

from sympy import isprime
def verify_factors(N, factors, full=True):
prod = 1
for f in factors:
assert(isprime(f))
prod *= f
assert(N % prod == 0)
if full:
assert(N == prod)
R = 3320934994356628805321733520790947608989420068445023
factors = [131071, 12761663, 179058312604392742511009, R]
verify_factors(2**289 - 1, factors)
J = 2**2023 - 1
prod = 127*(2**289 - 1)
F = J // prod
assert(J == prod*F)
factors = [127, 239, 20231, 131071, 62983048367, 131105292137]
verify_factors(2**119 - 1, factors)
prod = 239*20231*62983048367*131105292137
G = F // prod
assert(F == G*prod)
factors = [166684901665026193, 3845059207282831441, 153641005986537578671, 2605053667526976413491923719]
verify_factors(G, factors, False)
prod = 1
for f in factors:
prod *= f
H = G // prod
assert(G == H*prod)
assert(not isprime(H))
assert(len(str(J)) == 609)
assert(len(str(F)) == 520)
assert(len(str(G)) == 492)
assert(len(str(H)) == 408)

**Related post**: Primality certificates

**Update**: See the next post for the case of *b*^{n} + 1.