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

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

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.