Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Okay, THIS one is considerably more analytical... :P
(Used my post here as a basis.)

When successive Fibonacci numbers are factored, the primes appear in a specific order, which goes
$2, 3, 5, 13, 7, 17, 11, \dots$
(repeated factors are not included, such as the 2s in 8, the 3 in 21, the 2 in 34, and the 5 in 55).

Some primes don't appear until $F_{p}$, where $p$ is the prime. The list starts off
$2, 3, 7, 23, 43, 67, \dots$
(Edit: Thanks to Gerry and Qiaochu for the correction.)

I shall call these "First Prime Appearances", or FPAs for short. So therefore, the 5th FPA is 43.

My question is thus: what is the density of the FPA primes relative to all primes?

share|cite|improve this question
Have you consulted the OEIS? – Matthew Conroy May 9 '11 at 4:36
@Matthew: That says that these primes are those such that $p \equiv \{2,3\} \text{ mod } 5$. Does that mean that the answer I'm looking for is $\frac{2n}{5\ln{n}}$? EDIT: I see Qiaochu's answer. – El'endia Starman May 9 '11 at 4:54
Your list appears to be wrong. Why are $13$ and $17$ on it? – Qiaochu Yuan May 9 '11 at 4:56
@Qiaochu: ...VERY good question... -_- – El'endia Starman May 9 '11 at 14:36
@Qiaochu: Confirmed and fixed. – El'endia Starman May 9 '11 at 17:02
up vote 5 down vote accepted

Building on Qiaochu Yuan's answer, the problem is not to check that $\alpha = -\phi^2$ behaves like a primitive root, but to check that it has no more $n$th roots in $\mathbb{F}_{p^2}$, other than the ones given by its $(p-1)$th root.

Actually, you have already proved the partial result $\alpha$ has exactly enough nested square roots if and only if $p = 3 \mod 4$, so with probability $\frac{1}{2}$.

If $n$ is not a multiple of $2$ or $5$, pick a primitive $n$th root of unity $\zeta_n$, and we can look at the extension $\mathbb{Q} \subset \mathbb{Q}(\alpha,\zeta_n,\beta = \sqrt[n]\alpha)$

For any prime not dividing $n$, and different from $2$ or $5$, denote by $\sigma$ the Frobenius morphism. Chebotarev's theorem implies that the density of the primes for any possible action of $\sigma$ is always the same ($\frac1{2n\varphi(n)}$) :

$\sigma(\alpha) = \alpha^\epsilon$ with $\epsilon = \pm 1$

$\sigma(\zeta_n) = \zeta_n^{p \mod n}$ (this is Dirichlet's theorem)

$\sigma(\beta) = \zeta_n^k \beta^\epsilon : \sigma(\sigma(\beta)\beta^{-\epsilon})^n = \sigma(\alpha^{\epsilon-\epsilon}) = 1$, so $\sigma(\beta)\beta^{-\epsilon} = \zeta_n^k $ for some $k \in \mathbb{Z}/n\mathbb{Z}$.

Then for any divisor $d$ of $n$, the $d$th roots of $\alpha$ in $\mathbb{F}_{p^2}$ are the $\rho_i = (\zeta^i\beta)^{n/d}$ such that $\rho_i = \sigma\sigma(\rho_i) $. But $$ \sigma\sigma(\rho_i^{n/d}) = \sigma\sigma(\zeta_n^{in/d}\beta^{n/d}) =\sigma(\zeta_n^{(pi+k)n/d}\beta^{-n/d}) = \zeta_n^{(p^2i+(p-1)k)n/d}\beta^{n/d} = \zeta_n^{(p-1)((p+1)i+k)n/d} \rho_i$$ So it was equivalent to $(p-1)((p+1)i+k)n/d = 0 \mod n$, which is also $(p-1)((p+1)i+k) = 0 \mod d$ : The number of $d$th roots in the number of classes $i$ mod $d$ such that $(p-1)((p+1)i+k) = 0 \mod d$

This agrees with what we know, for example when $d$ is prime, if $p = 1 \mod d$, then since $\alpha$ has $(p-1)$th roots, it has $d$th roots ; if $p \neq \pm 1 \mod d$, then $x \mapsto x^d$ is a permutation of $\mathbb{F}_{p^2}$ so we can always find exactly one root ; and if $p = -1 \mod d$ then it has $d$th roots if and only if $k=0 \mod d$, which happens 1/d of the time.

The point of having a generic $n$ instead of a prime is that it tells us having $q$th roots is "independant" of having a $q'$th roots for coprime $q$ and $q'$.

Now we can say that for primes $p$ other than $2$ or $5$:

  • with probability $\frac12$, $\alpha \notin \mathbb{F}_{p^2}$ and $p$ is therefore disqualified from being a PFA.

The other $\frac{1}{2}$ is split independantly for all primes $q$ other than $2$ or $5$ :

  • with probability $\frac1{(q-1)}$, if $p = 1 \mod q$ and $\alpha$ has $q$th roots in $\mathbb{F}_{p^2}$.
  • with probability $1-\frac2{q-1}$, $p^2 \neq \pm 1 \mod q$ and $\alpha$ has one $q$th root in $\mathbb{F}_{p^2}$.
  • with probability $\frac1q$, $p = -1 \mod q$ and $\alpha$ has no $q$th root in $\mathbb{F}_{p^2}$.
  • with probability $\frac1{q(q-1)}$, $p = -1 \mod q$ and $\alpha$ has $q$th roots in $\mathbb{F}_{p^2}$, and $p$ is therefore disqualified from being a PFA.

  • for $q=5$, there is no obstruction to being a PFA

  • for $q=2$, $p$ is not a PFA with probability $\frac12$

Thus I expect the density of PFA to be precisely $\frac{10}{19} \Pi (1-\frac1{p(p-1)})$ where $p$ ranges over all primes.

share|cite|improve this answer
I wish I could 'accept' two answers at once, but I'm choosing this one because it has a final answer to my question. :P – El'endia Starman May 10 '11 at 22:33

A partial result: any FPA mus be congruent to $2, 3 \bmod 5$, and these primes have density $\frac{1}{2}$ in the set of all primes by the strong form of Dirichlet's theorem.

First, I claim that Binet's formula $F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$ (my numbering differs from yours), where $\phi, \varphi$ are the two roots of $x^2 = x + 1$, is valid modulo $p$ for any prime $p \neq 5$, where $\phi, \varphi$ are interpreted as elements of the splitting field of $x^2 = x + 1$ over $\mathbb{F}_p$. The proof is the same proof as in the usual case, the point being that the discriminant of $x^2 = x + 1$ is $5$, so for any other prime there are two distinct roots. Moreover, since $(\phi - \varphi)^2 = 5$, we know that $\phi - \varphi \neq 0$ for any such prime. It follows that $F_n \equiv 0 \bmod p$ if and only if $\phi^n \equiv \varphi^n \bmod p$.

If $\left( \frac{5}{p} \right) = 1$, then $x^2 = x + 1$ splits over $\mathbb{F}_p$, from which it follows that $\phi^{p-1} \equiv \varphi^{p-1} \equiv 1 \bmod p$, hence that $$F_{p-1} \equiv 0 \bmod p.$$

By quadratic reciprocity, $\left( \frac{5}{p} \right) = \left( \frac{p}{5} \right)$, hence these are precisely the primes $p \equiv 1, 4 \bmod 5$. So none of these primes are FPAs.

If $\left( \frac{5}{p} \right) = -1$, then $x^2 = x + 1$ has splitting field $\mathbb{F}_{p^2}$. The Galois group is generated by the Frobenius map $x \mapsto x^p$, hence $\phi^p \equiv \varphi \bmod p$ and, similarly, $\varphi^p \equiv \phi \bmod p$, hence $\phi^{p+1} \equiv \phi \varphi \equiv \varphi^{p+1} \equiv -1$, from which it follows that $$F_{p+1} \equiv 0 \bmod p.$$

This occurs if and only if $p \equiv 2, 3 \bmod 5$.

Edit: Second partial result: any FPA must be congruent to $3 \bmod 4$. Now the density has been reduced to $\frac{1}{4}$. To see this, note that since $\phi \varphi = -1$, the condition that $\phi^n \equiv \varphi^n \bmod p$ is equivalent to the condition that $(-\phi^2)^n \equiv 1 \bmod p$. On the other hand, we know that when $p \equiv 2, 3 \bmod 5$ we have $\phi^{p+1} \equiv -1 \bmod p$, hence $$\left( - \phi^2 \right)^{ \frac{p+1}{2} } \equiv (-1)^{ \frac{p-1}{2} } \bmod p.$$

It follows that when $p \equiv 1 \bmod 4$ we have

$$F_{ \frac{p+1}{2} } \equiv 0 \bmod p.$$

I don't expect these necessary conditions to be sufficient. The question is similar to asking that $- \phi^2$ behave like a primitive root, so this question or a variation on it may end up being an open problem.

Edit #2: For example, you can verify for yourself that $F_{16} \equiv 0 \bmod 47$ even though $47 \equiv 2 \bmod 5$ and $47 \equiv 3 \bmod 4$.

share|cite|improve this answer

I think the sequence is actually which starts off $2, 3, 7, 23, 43, 67, 83, 103, 127, 163, 167\dots$. I concur with Qiaochu's suggestion that this is an open problem.

share|cite|improve this answer
Thanks for the correction and it has been fixed. :) – El'endia Starman May 9 '11 at 17:03

This might be helpful for someone:

Here are the first few prime numbers which are congruent to either $2$ or $3$ modulo $5$, and congruent to $3$ modulo $4$, but which are not FPA's: $$107,\ 263,\ 307,\ 347,\ 563,\ 967,\ 1087,\ 1103,\ 1223,\ 1427,\ 1483,\ 1523,$$ $$1823,\ 2027,\ 2207,\ 2243,\ 2267\dots$$ I tried taking this list modulo many different primes, but I cannot see a pattern. The most important thing to take from this is that there are still many primes satisfying the congruences which are not FPA's.

share|cite|improve this answer
It's unlikely that there would be a simple pattern. The list is analogous to the list of, say, primes such that $2$ is a primitive root. – Qiaochu Yuan May 9 '11 at 21:00

Your Answer


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.