Suppose $p$, $q$ are primes such that $p=qk+1$. If $a$ is not $0$, $1,$ or $-1$, then $a^q\equiv1\pmod p$ if and only if $a$ is a $k$-th power residue modulo $p$, so that $a^{p-1}\equiv1\pmod p$.
Similarly, for the Fibonacci and Lucas sequences ($F(n)$ is the $n$th Fibonacci number, $L(n)$ the $n$th Lucas number) and their generalizations: if $q$ is a Sophie Germain prime and $p=2q+1$, then $L(q)\equiv0 \pmod p$ if and only if $p\equiv4\pmod 5$, which is the same as $q\equiv4\pmod 5$. Suppose however, $p=4q+1$ with $p$, $q$ primes. Given that $p\equiv4\pmod 5$, how do you determine whether $p$ divides $L(q)$ or $F(q)$?
Another example, given primes $p$, $q$, where $p\equiv4\pmod 5$, and $p=6q+1$. How do you determine whether or not $p$ divides $L(q)$?
Any ideas or help? Thanks!