# Prime Appearances in Fibonacci Number Factorizations

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?

-
Have you consulted the OEIS? oeis.org/A003631 –  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

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.

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

-
+1, this is very nice. –  Eric Naslund May 9 '11 at 15:53

I think the sequence is actually http://oeis.org/A000057 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.

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

-
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