Factoring b^n + 1

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

There is a theorem that says that if m divides n then bm + 1 divides bn + 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 22023 – 1, so this time let’s look at J = 22023 + 1.

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