# If $2^{2^j} a + 1$ divides $c^{2^j}+1$ for fixed $a,c$ and all $j$, then $a=1$,$c=2^l$ for some odd $l$, or $a=0$.

I have a very hard problem: Prove that, if $2^{2^j} a + 1$ divides $c^{2^j}+1$ for fixed integers $a,c$ and all nonnegative integers $j$, then $a=1$ and $c=2^l$ for some odd positive integer $l$, or else $a=0$.

Here is my progress on the problem so far:

Let $p$ be a prime divisor of $2^{2^j}a+1$. We have $p\mid 2^{2^j}+1\mid c^{2^j}+1$ for all $j\ge 0$, hence $c^{2^j}\equiv -1\pmod p$. Squaring both sides leads to $c^{2^{j+1}}\equiv 1\pmod p$. Thus, it is obvious that the multiplicative order of $c$ modulo $p$ is $2^{j+1}$. By Fermat's Little Theorem, we also know that $c^{p-1}\equiv 1\pmod p$, since obviously $\gcd(c,p)=1$. It follows that $2^{j+1}\mid p-1$ for all prime divisors $p$ of $2^{2^j} a + 1$. This means that $p=2^{j+1}k+1$ for all prime divisors $p$ of $2^{2^j} a+1$, which by the Euler-Lucas theorem is precicely a property of the Fermat numbers, i.e. $F_j=2^{2^j}+1$.

This is where I reached. I'm hoping that I can somehow conclude from this that $a=1$, i.e. $2^{2^j} a + 1$ is indeed the $j$'th fermat number (as Gilles Bonnet pointed out), but it seems difficult.

Added later: What if $2^n a+1$ divides $c^n+1$ for all nonnegative integers $n$, instead of just powers of 2? Does the problem become significantly easier?

• "$2^{2^j}a+1$ is indeed the $n$th fermat number" (at the end of the second edit) I think you mean $j$th Fermat number. – Gilles Bonnet Feb 24 '14 at 13:59
• @ArkanMegraoui: Regarding your Edit(3): You should at least require $n$ to be positive, or else the problem becomes trivial :) – jpvee Feb 25 '14 at 13:56
• Can I ask where this problem is taken from? Do you know that the assertion is true? – Alexander Gruber May 8 '14 at 16:31
• @ArkanMegraoui Sure, I didn't mean to sound critical. You've posted it in the right place. This information may simply be helpful to those working towards a solution. (See for example this discussion on our meta site about a similar type of inquiry.) – Alexander Gruber Jul 18 '14 at 0:40
• How about a=1 j=1 c=3. Is that a contradiction to that fact that c is a multiple of 2? – ghosts_in_the_code Feb 3 '15 at 10:22

## 1 Answer

As Elaqqad said in his comment, we can use Hadamard Quotient Theorem. For example, in this article (in french), it is proved the following result (see page 190).

Theorem : if $u$ and $v$ are in $\mathbb{Z}\backslash\{-1;0;1\}$ and $P_0$, $P_1$, $Q_0$, $Q_1$ are polynomials in $\mathbb{Z}[X]\backslash\{0\}$ such that for all integer $n>0$, $$P_1(n)u^n+P_0(n)\,|\,Q_1(n)v^n+Q_0(n)$$ then we can find $t\in\mathbb{N}^*$ such that $v=u^t$ and $Q_0P_1^t=(-1)^{t+1}Q_1P_0^t$.

So it is easy to deduce that if $a\not=0$ is such that $2^na+1\,|\,b^n+1$ for all integer $n>0$, then $a=1$ and $b=2^{2k+1}$ for some $k\geq0$.