How to tell if a Fibonacci number has an even or odd index Given only $F_n$, that is the $n$th term of the Fibonacci sequence, how can you tell if $n \equiv 1 \mod 2$ or $n \equiv 0 \mod 2$?
I know you can use the Pisano period, however if  $n \equiv 1$ or $n \equiv 2$ $\mod \pi(k)$, it can never be found, where $k$ is in $\pi(k)$ (The Pisano period).
Also there is the fact that if $\sqrt{5F_n^2+ 4}$ is an integer then $n 
\equiv 0 \mod 2$, but is there a faster way?
Lastly, because $F_1 = F_2 = 1$, that would have to be an exception for whatever rule/formula that would apply.
 A: Based on the relationship with the Lucas numbers,
$$L_n^2 = 5 F_n^2 + 4 (-1)^n$$
And the fact that
$$\lim_{n \rightarrow \infty} \dfrac{L_n}{F_n} = \sqrt{5}$$
We see for $n \ge 3$,
$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = (-1)^n$$
So
$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = -1 \Rightarrow n\text{ is odd}$$
$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = 1 \Rightarrow n \text{ is even}$$
Which is equivalent to
$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) < 0 \Rightarrow n\text{ is odd}$$
$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) > 0 \Rightarrow n \text{ is even}$$
A: You can't, in general, since $F_1=F_2$ but $1\not\equiv2\pmod2.$ Otherwise, compute the index of the Fibonacci number and checks its parity (the negatives don't cause trouble because $F_{2n+1}=F_{-2n-2}$ both have odd indices).
Modular methods with a fixed modulus will never be entirely effective for the same reason: $F_1=F_2$ and so $F_{m+1}\equiv F_{m+2}\mod M$ where m is the Pisano period mod M. But you could use multiple moduli to increase the chance of at least one working. In the extreme case, if the LCM of the moduli is at least as large as the number itself, at least one modulus will work (by the CRT) assuming the Fibonacci number is greater than 1.
A: You can do some things with moduli, but I haven't found a complete solution.  If $F_n \equiv 2 \pmod {12}$, $n$ is odd.  Similarly for $10$, while if it is equivalvent to $0, 3, 4, 7, 8, 9$ or $11, n$ is even.  Unfortunately, $1$ and $5$ go both ways and account for $9$ of the cycle of $24$.  You might do better with some others.
A: Assuming that $F_n\geq 2$, you can check the parity of $n$ depending on the sign of the difference between $\frac{1+\sqrt{5}}{2}F_n$ and the closest integer. If negative, then $n$ is even, if positive, then $n$ is odd.
A: We know that $$F_n = \frac{1}{\sqrt 5}(\varphi^n - \hat\varphi^n)$$  where $\varphi = \frac12\big(1+\sqrt 5\big)$ and   $\hat\varphi = \frac12\big(1-\sqrt 5\big)$ as usual.  Neglecting $\hat\varphi^n$, which is small when $n$ is large, we can calculate $n$ directly as
$$n =\operatorname{round}\left \lbrace \frac{\log F_n + \log\sqrt 5}{\log \varphi} \right\rbrace $$ where “round” means round to the nearest integer. For speed of computation we should simplify this to:
$$n =\operatorname{round}\left \lbrace \alpha\cdot\log F_n+\beta \right\rbrace  $$ where the $\alpha$ and $\beta$ constants are precomputed as:
$$\begin{array}{rcl}
\alpha & = \frac1{\log\varphi} & \approx 2.078087\\
\beta &= \frac{\log \sqrt 5}{\log \varphi} & \approx 1.672276
\end{array}
$$
For example, letting $F_n=233$, we find $n = \operatorname{round}{13.0000076556886} = 13$.
The calculation need not be done very precisely, it only needs to be done with sufficient precision to determine the nearest integer, and it always comes out extremely close to that integer.  If the value fell close to a half-integer, one might have to calculate many digits to determine whether it was a little bit more than or a little bit less than $n+\frac12$.  But this never happens.  The $13.0000076556886$ example above is typical, and as $n$ increases the calculated value becomes increasingly close to the desired integer.
Note that one can approximate the logarithm simply by counting the number of decimal digits in $F_n$ and then multiplying by $\log 10 \approx 2.302585$, or by counting the bits in $F_n$ and multiplying by $\log 2\approx 0.693147$.  (The foregoing is not correct; one has to be more careful in approximating the logarithm; see below.)
Since $\alpha$ and $\beta$ are constants, they can be precomputed and used in the program at zero cost.
[ Addendum: I have not done a careful analysis of the precision with which the logarithm needs to be calculated, but experiments suggest that it is low, as I suggested earlier.  For example, I tried the following method for fudging the logarithm: 


*

*Take $F_n$ and count the decimal digits.

*Multiply this by $2.3026$.

*Add the log of the  two leftmost digits of $F_n$. (There are only 90 possible values, which can be precomputed and stored in a lookup table.)


This was sufficiently precise to yield correct answers for each $F_n$ with $n<1000$.  ]
A: Given some $F_n$, compute: 
1) the residue $f_m = F_n \mod{p}$ where p is a prime such that $x^2-x-1$ has roots in $\mathbb{F}_p$ and $p$ is a safe prime. (for example $p=11$, $p=59$ or $p=179$, ... ).
2) Then calculate the index $m$ of $f_m$ (calculate $f_0 = F_0 \mod{p}, ..., f_{p-1} = F_{p-1} \mod{p}$). 
Result:


*

*If $m$ is even, then $n$ is even, too. 

*If $m=1$, try a different prime.

*else $n$ is odd.

