The previous post illustrated a technique for finding factors of number of the form *b*^{n} – 1. This post will look at an analogous, though slightly less general, technique for numbers 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 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^{2023} – 1, so this time let’s look at *J* = 2^{2023} + 1.

Since 2023 = 7×17×17, we know *J* is divisible by 2^{n} + 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)))