Here we shall aim to generalise the corollary from the last post, and on the way generalise some other important properties of the Fibonacci sequence, to general Fibonacci-like sequences.
Consider a sequence with and for , where such that . Let be the roots of . Then
Let be an odd prime. Suppose and have a common factor. By Dedekind’s factorisation criterion, is either prime or it factors into two (not necessarily distinct) prime ideals each with norm . In the first case, we must have i.e. , taking ideal norms. In the second case, if one of the prime factors of divides , then (again taking norms) must divide .
So we take which ensures that and are coprime. Thus we deduce from the general exponent lifting result,
Lemma 1. If is a prime factor of such that , then .
Next, recalling the proof of the corollary from last time, we seem to require the condition .
Lemma 2. If , then for all .
Proof. First, it is clear that , where , and that . Thus .
Let be a prime factor of . Then for ,
If and share a common factor, then (taking ideal norms,) . Hence , a contradiction as .
Hence and by the Euclidean algorithm we get . Thus , as desired.
Now we define to be the least such that , and we are ready for our generalisation!
Theorem. Let be given by and for , where are coprime integers such that . Then for an odd prime for which exists,
Proof. If , then . By definition of , . Hence , which is impossible as . Thus and the proof of the corollary in the previous post now applies.