Article 6RACV Lucas numbers and Lucas pseudoprimes

Lucas numbers and Lucas pseudoprimes

by
John
from John D. Cook on (#6RACV)

Lucas numbers [1] are sometimes called the companions to the Fibonacci numbers. This sequence of numbers satisfies the same recurrence relation as the Fibonacci numbers,

Ln+2 = Ln + Ln+1

but with different initial conditions: L0 = 2 and L1 = 1.

Lucas numbers are analogous to Fibonacci numbers in many ways, but are also in some ways complementary. Many sources refer to Lucas numbers as the complement to the Fibonacci numbers, I have not seen a source that explains why they are not simply a complement to the Fibonacci numbers. That is, I have not seen anyone explain why Edouard Lucas chose the particular initial conditions that he did.

Any initial conditions linearly independent from the Fibonacci conditions would produce a sequence complementary to the Fibonacci numbers. Just as a second order linear differential equation has two linearly independent solutions, so a second order linear difference equation has two linearly independent solutions.

Fibonacci and Lucas numbers are analogous to sines and cosines because the former form a basis for solutions to a difference equation and the latter form a basis for solutions to a differential equation. The analogy goes deeper than that [2], but that's a topic for another post.

As with Fibonacci numbers, the ratio of consecutive Lucas numbers converges to the golden ratio. An interesting property of the Lucas numbers, one with no Fibonacci analogy, is that if n is prime, then

Ln 1 mod n.

For example, the 7th Lucas number is 29, which is congruent to 1 mod 7. Maybe this property had something to do with how Lucas chose his starting values, or maybe he chose the starting values and discovered this later. If you know the history hear, please let me know.

The converse of the theorem above is false. That is, the condition

Ln 1 mod n

does not imply that n is prime. Composite numbers satisfying this condition are called Lucas pseudoprimes. The smallest Lucas pseudoprime is 705. The 705th Lucas number

2169133972532938006110694904080729167368737086736963884235248637362562310877666927155150078519441454973795318130267004238028943442676926535761270636

leaves a remainder of 1 when divided by 705.

If is the golden ratio, then Ln is the nearest integer to n for n >= 2. Perhaps this motivated Lucas' definition.

Related posts

[1] The s" in Lucas is silence because Monsieur Lucas was French.

[2] Barry Lewis, Trigonometry and Fibonacci Numbers, Math. Gazette, 91 (July 2007) pp. 216-226

The post Lucas numbers and Lucas pseudoprimes first appeared on John D. Cook.
External Content
Source RSS or Atom Feed
Feed Location http://feeds.feedburner.com/TheEndeavour?format=xml
Feed Title John D. Cook
Feed Link https://www.johndcook.com/blog
Reply 0 comments