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?

  • $\begingroup$ "$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. $\endgroup$ Feb 24 '14 at 13:59
  • $\begingroup$ @ArkanMegraoui: Regarding your Edit(3): You should at least require $n$ to be positive, or else the problem becomes trivial :) $\endgroup$
    – jpvee
    Feb 25 '14 at 13:56
  • $\begingroup$ Can I ask where this problem is taken from? Do you know that the assertion is true? $\endgroup$
    – Alexander Gruber
    May 8 '14 at 16:31
  • $\begingroup$ @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.) $\endgroup$
    – Alexander Gruber
    Jul 18 '14 at 0:40
  • 2
    $\begingroup$ How about a=1 j=1 c=3. Is that a contradiction to that fact that c is a multiple of 2? $\endgroup$ Feb 3 '15 at 10:22

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.