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

  • $\begingroup$ Your approach appears to numerically agree with Brent's even for p=4k+3. $\endgroup$
    – joro
    Nov 7 '14 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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