3
$\begingroup$

I was looking at this webpage which lists the first 200 Lucas Numbers color-coded with their prime factors and I noticed that all the Lucas numbers with power of two or prime indexes were relatively prime to all previous Lucas numbers.

Clearly the author(s) of the page know this too because they did the color-coding, which shows the pattern clearly. I was wondering if this pattern holds for all Lucas numbers, and where I might find a proof or counterexample? My Google-Fu hasn't turned up anything on this particular question. Is this an open problem?

$\endgroup$
3
$\begingroup$

The pattern does hold for all Lucas numbers except $L_3=4=L_0^2$. In this paper from the Fibonacci Quarterly, it is proven that

$$\mathbb{gcd}(L_m,L_n)=\left\{ \begin{array}{lr} L_{\mathbb{gcd}(m,n)} & a=b \\ 1~\text{ or } ~2 & a\ne b \end{array} \right.$$ where $a$ and $b$ are the maximum exponents such that $2^a|m$ and $2^b|n$.

Now for the cases we are interested in. As a preliminary result, note that $L_n$ is divisible by $2$ if and only if $3|n$ (this is readily provable with induction).

Note that $L_{\mathbb{gcd}(p,n)}=L_1=1$ for all $n<p$ where $p$ is prime, hence $\mathbb{gcd}(L_p,L_n)=1~\text{or}~2$. However since $2\not|L_p$ for $p\ne 3$ this leaves us with the only option $\mathbb{gcd}(L_p,L_n)=1$ for all $n<p$, so $L_p$ is relatively prime to all previous Lucas numbers (for $p\ne3$).

Similarly when $m=2^c$, then $c=a\ne b$ for all $n<m$. Hence $\mathbb{gcd}(L_{2^c},L_n)=1~\text{or}~2$ for all $n<2^c$, but since $2\not|L_{2^c}$ we have $\mathbb{gcd}(L_{2^c},L_n)=1$ for all $n<2^c$, which again lets us conclude that $L_{2^c}$ is relatively prime to all previous Lucas numbers.

$\endgroup$
  • $\begingroup$ Excellent answer. Going into detail on the two cases I was interested in was especially appreciated. $\endgroup$ – hatch22 May 30 '14 at 21:31

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.