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
(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
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)))