# Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example of course.

Tried using $\gcd(2^a+1, 2^b+1) = 2^{\gcd(a, b)}+1$ (where $a$ and $b$ are odd positive integers), stuck on both ends. I figured out that if $n$ divides $2^n+1$ then n divides both $2^{2^n+1}+1$ and $2^{2^{2^n+1}+1}+1$ but this implication doesn't work backwards (e.g. $n=57$).

Would appreciate some help.

EDIT1 Eric's pointer wasn't enough for me. Trying to bump by editing instead of reposting (sorry, not sure how to).

EDIT2 This is not much but might save some time for someone. Using user101140's notation and the $a^n+b^n$ identity

$f(n) = 2^n+1 = 3 \sum\limits_{k=0}^{n-1} (-2)^k$

$f(f(n)) = 3 \sum\limits_{k=0}^{2^n} (-2)^k$

$f(f(f(n))) = 3 \sum\limits_{k=0}^{2^{2^n+1}} (-2)^k$

Also, $n \mid f(n) \implies n \mid f(f(n))$ is due to $n \mid f(n) \implies f(n) \mid f(f(n))$ so the proof might be something along the lines of $n \mid f(f(n)) \implies f(f(n)) \mid f(f(f(n)))$. (Please don't bash me if that's stupid.)

• We can prove that $n$ must be of the form $n=p^k$ for some prime $p\equiv 3\pmod{4}$, and we can also prove that if $n=3^k$, then the implication is true, however dealing with $n=p^k$ for general $p$ seems difficult due to the appearing of $\phi(p-1)$. – Eric Naslund Oct 9 '13 at 1:03

## 2 Answers

My computer found the counterexample $n=520809$.

Interestingly $520809=57\times9137$, but I couldn't find any neat "explanation" for that, nor a natural way that $520809$ would appear.

Other few counterexample are $2343441, 15622617, 15622617...$ Indeed, one can show that there are infinitely many of then since if $n$ works, $f(n)$ also works (since $a|b \Leftrightarrow f(a)|f(b)$)

In case anyone is interested in my python code:

def factor(n): #Factors n, and returns a list with its factors (possibly repeated) in increasing order
k=2
v=[]
while n>1:
if n%k==0:
v.append(k)
n=n/k
else:
k=k+1
if k*k>n:
v.append(n)
return v

def phi(n): #Calculates the totient function using the prime factorization
v=factor(n)
prod=1
a=1
for b in v:
if b==a:
prod*=b
else:
prod*=b-1
a=b
return prod

def f2(n): # Calculates f(f(n)) mod n
a=pow(2,n,phi(n))+1
return (pow(2,a,n)+1)%n

def f3(n): # Calculates f(f(f(n))) mod n
a=pow(2,n,phi(phi(n)))+1
b=pow(2,a,phi(n))+1
return (pow(2,b,n)+1)%n

n=11
while 1: #Tries all odd n
if f2(n)==0:
if f3(n)!=0:
print n
break
n=n+2


I'm not a mathematician, so correct me if I did something wrong...

Let

$f(n) = 2^{n} + 1$

Then

$f(a \cdot b) = (2^{a} + 1)(1 - 2^{a} + 2^{2a} - 2^{3a} + ... + (-1)^{b-1}2^{(b-1)a})$, for $a$ and $b$ integers.

So $f(a \cdot b) = f(a)g(a, b)$, and $g(a, b)$ is integer too.

Let $f(n) = n \cdot p$. That is, $f(n)$ is divisible by $n$.

Then

$f(f(n)) = f(n \cdot p) = f(n)g(n, p) = n \cdot p \cdot g(n, p) = n \cdot p_2$

So $f(f(n))$ is divisible by $n$.

And

$f(f(f(n))) = f(n \cdot p_2) = f(n)g(n, p_2) = n \cdot p_2 \cdot g(n, p_2)$

So $f(f(f(n)))$ is divisible by $n$.

But $f(f(f(n))) = 2^{2^{2^n + 1} + 1} + 1$

Remembering, I assumed that $f(f(n))$ is divisible by $n$ and obtained that $f(f(f(n)))$ is also divisible by $n$.

I think that is proven.

• I realize that $f(a \cdot b)$ is $(2^{a} + 1)(1 - 2^{a} + 2^{2a} - 2^{3a} + ... + (-1)^{b-1}2^{(b-1)a})$ only if b is odd. So, there is a problem on my proof. – Eduardo Oct 16 '13 at 5:03
• I realize other thing. $f(n)$ is odd, so if $f(n) = n \cdot p$ then $n$ and $p$ is odd. So I think this comlete the proof. – Eduardo Oct 16 '13 at 5:15
• Since $2^n+1$ is odd, we're only interested in cases where n is odd, thus a and b are odd too. That's not the problem. The problem is that you didn't assume $f(f(n))$ is divisible by $n$ but that $f(n)$ is divisible by $n$. This is basically another proof for the statement in my second paragraph. – mathaway__ Oct 16 '13 at 5:22
• You are right. How did you figure out that for n = 57 the implication doesn't work backwards? – Eduardo Oct 16 '13 at 13:33
• It's actually part of the series $g(n) = (2^{3^n}+1)/9$ where $n>1$. The proof uses the equation in the second paragraph and the fact that the exponent of 3 in the prime factorization for any $2^n+1$ is exactly $n+1$. – mathaway__ Oct 16 '13 at 17:24