Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the following statement for 3, 5, 17 and 257 but can't prove it. I would be grateful if someone could provide a hint.

Let $F = 2^{2^k} + 1$ be a Fermat prime.
Then for $n=0, 1, ..., 2^k-1, x^{2^n} + 1 \equiv 0 \mod F$ has exactly $2^n$ solutions.

For example, when k=2 we have:
$(n=0) \hspace{10pt} x^1 + 1 \equiv 0 \mod 17$ has one solution (x=16).
$(n=1) \hspace{10pt} x^2 + 1 \equiv 0 \mod 17$ has two solutions (x=4 and 13).
$(n=2) \hspace{10pt} x^4 + 1 \equiv 0 \mod 17$ has four solutions (x=2, 8, 9 and 15).
$(n=3) \hspace{10pt} x^8 + 1 \equiv 0 \mod 17$ has eight solutions (x=3, 5, 6, 7, 10, 11, 12 and 14).

share|improve this question

3 Answers 3

up vote 3 down vote accepted

This sort of rephrases Henning's answer. (That one is bottom up, this one is top down, which I like more personally)

Fermat's little theorem says that $x^{2^{2^k}}-1$ has $2^{2^k}$ solution mod $p$. Now $x^{2^{2^k}}-1 = \left (x^{2^{2^{k-1}}} - 1 \right)\left(x^{2^{2^{k-1}}} + 1 \right)$, each factor having at most $2^{2^{k-1}}$ solutions because the degree of each factor is $2^{2^{k-1}}$. As their product has $2^{2^k}$ solutions we are forced to conclude that each factor has exactly $2^{2^{k-1}}$ solutions.

Now take the factor $x^{2^{2^{k-1}}} - 1$ and repeat the same argument.

share|improve this answer
    
+1 I have to agree on top-down being clearer. The bottom-up approach went fine until I noticed that I'd read the equation as $x^{2^n}=1$ instead of $x^{2^n}=-1$, and I had to scramble to recover some sense from my train of thought ... –  Henning Makholm Sep 14 '11 at 17:42

Obviously $x^1+1\equiv 0 \pmod p$ has exactly one solution.

For each $n$ it must hold that $x^{2^{n+1}}+1\equiv 0 \pmod p$ has at most twice as many solutions as $x^{2^n}+1\equiv 0\pmod p$ -- otherwise one of the $2^n$th roots must have more than two square roots in $\mathbb F_p$, which is is impossible.

Fermat's little theorem ensures that $x^{2^{2^k}}\equiv 1\pmod p$ for all nonzero $x$. But this means that $x^{2^{(2^k-1)}}$ must always be a square root of $1$ modulo $p$, that is, either $1$ or $-1$. An analogous argument to the one above shows that there cannot be more than $2^{(2^k-1)}$ instances of either $1$ or $-1$, so that must be the number of solutions to $x^{2^{(2^k-1)}}+1\equiv 0\pmod p$. But that determines the number of $2^n$th roots of $-1$ uniquely for $1\le n\le 2^k-1$.

In general, this reasoning means that $x^{2^n}\equiv a \pmod p$ with $a\not\equiv 0$ always has either exactly $2^n$ solutions or none at all, depending on how many times one can square $a$ modulo $p$ without reaching $1$.

share|improve this answer

[Removed my previous generalization for this]

Even more general theorem, with even easier proof:

If $p$ is prime and $2d|p-1$, then the number of solutions of $x^d+1=0$ in $\mathbb{F}_p$ is $d$.

Proof:

Since $\mathbb{F}_p^\times$ is a cyclic group of order $p-1$, the number of solutions for $x^{2d}-1=0$ is $2d$, and the number of solutions of $x^d-1=0$ must be $d$, so the number of solutions of $x^d+1=0$ must be $d$.

This uses two pieces of knowledge:

Lemma: $\mathbb{F}_p^\times$ is a cyclic group of order $p-1$.

Lemma: If $G$ is a cylic group of order $n$ and $m|n$, the number of solutions to $x^m=1$ in $G$ is $m$.

Even more generally: If $a\in\mathbb{F}_p^\times$ is of order $n$ and $dn|p-1$, then the number of solutions to $x^d = a$ is $d$. (The previous theorem corresponds to the case $a=-1$ and $n=2$.)

Most generally: If $(C_m,\times)$ is a cyclic group of order $m$, and $a\in C_m$ is of order $n$, and $d\geq 1$, let $d_0=\gcd(m,d)$. Then $x^d=a$ has solutions in $C_m$ iff and only if $d_0n|m$, in which case, there will be exactly $d_0$ solutions.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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