11
$\begingroup$

Let $L_n$ be the Lucas series: $L_0=2,L_1=1,L_n=L_{n-1}+L_{n-2}(n>1).$

$p$ is a prime number and $p\equiv3,7\pmod {20}$, hence $\exists x,y\in \mathbb Z:2p=x^2+5y^2.$

Is it true that $$\begin{eqnarray} L_{\frac{p+1}4}\equiv \begin{cases} (-2)^\frac{p+1}4\pmod p & y\equiv \pm\frac{p-1}2\pmod 8, \\ -(-2)^\frac{p+1}4\pmod p & y\not \equiv\pm\frac{p-1}2\pmod 8. \end{cases} \end{eqnarray}$$

Example:If $p=23$, then $2p=1^2+5\cdot3^2$, hence $y=\pm3\equiv \pm \frac{p-1}2\pmod 8,L_{\frac{p+1}4}=L_6=18\equiv(-2)^{\frac{p+1}4}=2^6\pmod p.$

This is true for $p<4000$.

Add: A proof to $p\equiv3,7\pmod {20}\implies\exists x,y\in \mathbb Z:2p=x^2+5y^2.$

$p\equiv3,7\pmod {20}\implies \left(\dfrac{-5}p\right)=1\implies\exists t\in \mathbb Z:t^2\equiv-5\pmod p.$

Lemma1: If $p$ is a prime, $t\in \mathbb Z$, then $\exists x,y\in \mathbb Z: 0 <y<\sqrt p,-\sqrt p<x<\sqrt p,yt\equiv x\pmod p.$ You can prove this by Pigeonhole principle.

Hence $x^2\equiv -5y^2\pmod p\implies x^2+5y^2=np.(0<n<6.)$

Lemma2: $x^2+5y^2\equiv 0,1,4\pmod 5.$

If $n=2$ then we are done.

If $n=1$ then $x^2+5y^2=p\equiv \pm2 \pmod 5,$ a contradiction.

If $n=4$ then $x^2+5y^2=4p\equiv \pm2 \pmod 5,$ a contradiction.

If $n=5$ then $x^2+5y^2=5p,5\mid x,$ let $x=5x_1$ then $y^2+5x_1^2=p,$ a contradiction.

If $n=3$ then $x^2+5y^2=3p\implies 3\mid (x+y)(x-y),$ if $3\mid x-y,$ let $y_1=-y$ then $3\mid x+y_1$ and $x^2+5y_1^2=3p,$ hence WLOG we can assume $3\mid x+y,$ hence $3\mid x-5y,$ then $$(\dfrac{x-5y}{3})^2+5(\dfrac{x+y}{3})^2=2p,$$ we are done.

$\endgroup$
5
  • $\begingroup$ Could you please add your proof about the existence of $x$ and $y$? $\endgroup$
    – chubakueno
    Jul 28, 2013 at 17:53
  • $\begingroup$ @chubakueno Have edited. $\endgroup$
    – lsr314
    Jul 29, 2013 at 3:49
  • 2
    $\begingroup$ Thank you, here is some C code to verify your conjecture up to $1000000$ codepad.org/6tvDa7ip. It can be verified up to larger values, but the runing time goes horrible(already near to 1 min in the 1M case)due to the modular exponentiation and the modular lucas number calculation. $\endgroup$
    – chubakueno
    Jul 29, 2013 at 5:06
  • 1
    $\begingroup$ My old code compiled with gcc conj.c -o conj.exe -O3 ran in $51.5$ secs in my machine, but the new code here (codepad.org/rUWmYlUh) inspired by the fibonacci fast doubling algorithm here (nayuki.eigenstate.org/page/fast-fibonacci-algorithms) (traduced his recursive algorithm at (nayuki.eigenstate.org/res/fast-fibonaccialgorithms/…) into an iterative one, then used $L_n=2F_{n+1}-F_{n}$) compiled with the same options took $0.52$ secs, a solid $100x$ speedup :). $\endgroup$
    – chubakueno
    Aug 2, 2013 at 21:20
  • 1
    $\begingroup$ corrected third link: (nayuki.eigenstate.org/res/fast-fibonacci-algorithms/…). (5 minutes have passed after my last comment) $\endgroup$
    – chubakueno
    Aug 2, 2013 at 21:48

0

Your Answer

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