The previous post illustrated a technique for finding factors of number of the form bⁿ – 1. This post will look at an analogous, though slightly less general, technique for numbers of the form bⁿ + 1.

There is a theorem that says that if m divides n then b^m + 1 divides bⁿ + 1 if n is odd. To see that the exponent must be odd, let b = 10, n = 4, and m = 2: 10,0001 is not divisible by 101.

Last time we looked at 2²⁰²³ – 1, so this time let’s look at J = 2²⁰²³ + 1.

Since 2023 = 7×17×17, we know J is divisible by 2ⁿ + 1 for n = 7, 17, 7×17, and 17×17. Factoring each of these factors tells us that J is divisible by

• 3
• 43691
• 72251
• 79187
• 1077971
• 823679683
• 18360250452977
• 197766803208315851
• 143162553165560959297
• 338858733065598401355195539629373089

(If it seems this post is moving too fast, you might want to go back and read the previous post and then come back.)

Let P be the product of the factors above, and let F = J/P.  Now F is a 493-digit number, so we don’t expect to be able to get much further unless we’re lucky. We can find three factors of F

• 43
• 4382432993
• 1809032819104754041

but then we get stuck. We know there are more factors, but it seems doubtful that I’m going to find any more anytime soon.

***

As in the previous post, we’ll conclude with Python code to verify the claims above.

from sympy import isprime

def verify_factors(N, factors, full=True):
    prod = 1
    for f in factors:
        assert(isprime(f))
        prod *= f
    if full:
        assert(N == prod)
    else:
        assert(N % prod == 0)
        assert(not isprime(N // prod))
    return N // prod

factors = [
    3,
    43691,
    72251,
    79187,
    1077971,
    823679683,
    18360250452977,
    197766803208315851,
    143162553165560959297,
    338858733065598401355195539629373089
]

J = 2**2023 + 1
F = verify_factors(J, factors, False)

factors = [43, 4382432993, 1809032819104754041]
verify_factors(F, factors, False)

print(len(str(F)))

Suppose you want to factor a number of the form bⁿ – 1.

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

Let’s use this theorem to try to factor J = 2²⁰²³ – 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⁷ – 1 and 2²⁸⁹ – 1 because 2023 = 7×17×17.

Is J divisible by (2⁷ – 1)(2²⁸⁹ – 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⁷ – 1) (2²⁸⁹ – 1) F

for some factor F.  Now 2⁷ – 1 = 127, a prime. What about 2²⁸⁹ – 1?

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

2²⁸⁹ – 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¹¹⁹ – 1 because 7 × 17 = 119 is a factor of 2023.

Now

2¹¹⁹ – 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ⁿ + 1.

I’ve written lately about two general ways to prove that a number is prime: Pratt certificates for moderately-large primes and elliptic curve certificates for very large primes.

If you can say more about the prime you wish to certify, there may be special forms of certificates that are more efficient. In particular, there are efficient tests to determine whether Fermat number or a Mersenne number is prime.

Pepin’s test, implemented in four lines of Python here, determines whether or not a Fermat number is prime. It can instantly prove that the known Fermat primes are indeed prime. It can quickly show that the next several Fermat numbers are composite, but the time required to run Pepin’s test increases rapidly for larger numbers.

The Lucas-Lehmer test, implemented in six lines of Python here, tests whether a Mersenne number is prime. The largest known primes are Mersenne primes because the Lucas-Lehmer test is relatively efficient, though it still takes a lot of effort to search for new Mersenne primes.

Certifying that a number is composite is potentially much easier than certifying that a number is prime. A famous example of a proof that a number is composite was Euler’s announcement in 1732 that

2³² + 1 = 641 × 6700417,

thereby proving that the fifth Fermat number is not prime, disproving Fermat’s conjecture.

Several Fermat numbers have been fully factored, concretely proving that they are composite, but some Fermat numbers have been proven composite via Pepin’s test that have not been factored. The analogous statement is true for Mersenne primes and the Lucas-Lehmer test.