Is $p$ is square modulo $F_p$ when $p=4k+1 > 5$?

Question

$F_n$ are the Fibonacci numbers.

In On computing factors of cyclotomic polynomials p.1 for odd square-free $n>1$ the cyclotomic polynomial $\Phi_n(x)$ satisfies:

$$ 4 \Phi_n(x)=A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1)$$

and Brent gives algorithm for computing $A_n,B_n$.

For natural $N$, if we know $n$-th root of unity modulo $N$ the LHS will vanish and if $B_n$ is invertible this gives square root modulo $N$ of $(-1)^{(n-1)/2} n$.

Roots of unity come for free for sequences of the form $(a^n-1)/(a-1)$ and experiments suggest for composite $n$ non-trivial factor is found (which is known for other reasons) and for $n$ prime the trivial root is found and $B_n$ is invertible.

For $N=F_p$, $p$ odd prime, work in ($\mathbb{Z}/N\mathbb{Z})[w]/(w^2-5)$.

$(1+w)/(1-w)$ is $p$-th root of unity from the closed form for Fibonacci numbers.

Experiments suggest that if $p=4k+1$, Brent's algorithm gives solution in $\mathbb{Z}/N\mathbb{Z}$, i.e. the "algebraic" parts cancels.

if $p=4k+3$, the square root is of the simple form $w \mathbb{Z}/N\mathbb{Z}$, which gives square root of $-5p$.

Q1 Is $p$ is square modulo $F_p$ when $p=4k+1 > 5$?

Q2 How to explain the cancellation of $w$?

This doesn't hold for composite $p$.

Similar result is possible for Lucas number, where $w$ is known and probably $\sqrt{-1}$ might appear.

Answer 1

The answer to the first question is yes, although the argument I give below is not along the lines that you were originally thinking. I will show that $p$ is a square modulo $q$ for every prime factor $q$ of $F_{p}$, provided $p \equiv 1 \pmod{4}$ and $p > 5$.

As you mention, $\zeta = \frac{1 + \sqrt{5}}{1 - \sqrt{5}}$ is a $p$th root of unity modulo $F_{p}$ and hence modulo $q$. Also $\zeta$ will lie in either $\mathbb{F}_{q}$ or in $\mathbb{F}_{q^{2}}$. The classical Gauss sum formula allows one to express $\sqrt{p}$ in terms of $\zeta$: $$ \sqrt{p} = \sum_{j=1}^{p-1} \left(\frac{j}{p}\right) \zeta^{j}. $$ Now if $\sigma : \mathbb{F}_{q^{2}} \to \mathbb{F}_{q^{2}}$ is the nontrivial automorphism (given by $\sigma(x) = x^{q}$), we can see that $\sigma(\zeta) = \zeta$ if $\sqrt{5} \in \mathbb{F}_{q}$, and $\sigma(\zeta) = 1/\zeta$ when $\sqrt{5} \not\in \mathbb{F}_{q}$. In the former case, it's clear that $\sqrt{p}$ is fixed by $\sigma$ and hence is in $\mathbb{F}_{q}$, while in the latter case, we have $$ \sigma(\sqrt{p}) = \sum_{j=1}^{p-1} \left(\frac{j}{p}\right) \zeta^{-j} = \sum_{j=1}^{p-1} \left(\frac{-j}{p}\right) \zeta^{j} = \left(\frac{-1}{p}\right) \sqrt{p}. $$ Since $p \equiv 1 \pmod{4}$, $\left(\frac{-1}{p}\right) = 1$ and so in this case $\sqrt{p} \in \mathbb{F}_{q}$ also.