Why do prime factors of odd term Lucas numbers only end in 1 or 9?

Question

I'm working on a problem, which I've eventually reduced to the following question: show that every odd term Lucas number has a prime factor that ends with either 1 or 9. Here the Lucas sequence is defined by the recursion: $$a_0=2, a_1=1, a_{n+1}=a_n+a_{n-1}.$$

I looked up a list of prime factorizations of Lucas numbers on the following page:

https://r-knott.surrey.ac.uk/Fibonacci/lucas200.html

Surprisingly, I find all the odd term Lucas numbers to have only prime factors that end with either 1 or 9, with the exception that $a_{6k+3}$ is also divisible by 4. It's easy to show using modulo arithmetic that all $a_{6k+3}$ are divisible by 4 and no higher powers of 2, while all other odd term Lucas numbers are odd. If we count out those factors of 4, all the other prime factors of the odd term Lucas numbers seem to end only with 1 or 9. This is a curious observation, but I don't know how one can prove this. Can anyone help please!

Answer 1

This paper has some clues, but does not seem to quite get to the point where it can be used to prove this conjecture. But I think that understanding this paper would give you insight into this conjecture.

It lays out how (odd-indexed) Lucas numbers are mostly factored using factors of earlier (odd-indexed) Lucas numbers, with some additional "primitive" prime factors. So along with induction, it allows you to study only these primitive prime factors.

Theorem 3 on page 255 says something relevant, breaking down some cases where a primitive prime factor might be $\pm1$ or $\pm3$ mod $10$. Your conjecture is that the $\pm3$ case is vacuous when $n$ is odd, but the authors of this paper don't appear to notice that.

At the end there is a table of Lucas number factorizations up to $L_{500}$. I did not verify the conjecture through this table, but you might examine that. The notation in the table has some factors in parentheses that are referencing an earlier factorization in the table. For example $L_{495}$ is the product of five earlier Lucas numbers with "495A" and "495B", which in turn are defined using more recursive notation.

Answer 2

I made another Conway Topograph diagram for $x^2 - 5 y^2$ The $x,y$ pairs are written vertically in green. The values of $x^2 - 5 y^2$ are in pink.

Right, see displayed $11^2 - 5 \cdot 5^2 = -4, \; \; $ $29^2 - 5 \cdot 13^2 = -4, \; \; $ $199^2 - 5 \cdot 89^2 = -4, \; \; $ $521^2 - 5 \cdot 233^2 = -4, \; \; $

Also, $38^2 - 5 \cdot 17^2 = -1, \; \; $ and doubling this gives $76^2 - 5 \cdot 34^2 = -4, \; \; $

If $x$ is one of your alternate Lucas numbers, there is a Fibonacci number $y$ such that $$ x^2 - 5 y^2 = -4 $$ From $x^2 = 5 y^2 - 4, $ we see $x^2 = 5 y^2 - 2^2 = - (2^2 - 5 y^2 )$ and $$ x | 2^2 - 5 y^2 $$ Now if there is any prime $q$ with $q \equiv \pm 2 \pmod 5,$ and if $q | x,$ then $$ q | 2^2 - 5 y^2 $$ However, for any such prime, Legendre symbol $(20|q) = -1.$ This forces $q | y $ along with $q | 2.$

Thus, it is allowed for $x$ to be even (divisible by 2) and divisible by primes $p \equiv 1,4 \pmod 5,$ but not by $q \equiv \pm 2 \pmod 5$ when $q > 2$

On this site, you may have seen this fact: for a prime $r \equiv 3 \pmod 4,$ if $r | u^2 + v^2,$ then both $r|u$ and $r|v$ This is a general thing about the Legendre symbol.