IBM Ponder This #277 · May 2021

The Fibonacci sequence is defined by $F_0=0,F_1=1$ and the recurrence relationship $F_n=F_{n-1}+F_{n-2}$.

We call any sequence $A_0,A_1,A_2,\dots$ Fibonacci-like if it satisfies the recurrences $A_n=A_{n-1}+A_{n-2}$ for all $n\ge 2$.

The Fibonacci sequence contains many prime numbers. For instance, $F_3=2,F_{11}=89$, etc. Our goal is to see how to generate a fibonnaci-like sequence without any prime numbers and relatively prime initial elements. This amounts to finding suitable relatively prime $A_0$ and $A_1$.

The main step in the generation is finding a set [(p_1, m_1, a_1), (p_2, m_2, a_2),..., (p_t, m_t, a_t)] of triplets of the form (p_k, m_k, a_k) such that:1. $1\le a_k\le m_k$. 2. For every natural number n, we have that for some k, n is equivalent to $a_k$ modulo $m_k$ (i.e. $m_k$ divides $n-a_k$). 3. $p_k$ is a prime divisor of the Fibonacci number $F_{m_k}$ 4. All the $p_k$ are distinct (the $m_k$ and $a_k$ can be non-distinct)

Given this set, one can generate $A_0$ and $A_1$ that satisfy1. $A_0$ is equivalent to $F_{m_k-a_k}$ modulo $p_k$ 2. $A_1$ is equivalent to $F_{m_k-a_k+1}$ modulo $p_k$

and one can prove that this sequence does not contain any primes by using the following easy-to-prove identity, which holds for any Fibonacci-like sequence: $A_{m+n}=A_m{F}_{n-1}+A_{m+1}{F}_n$.

Your goal is to find the set [(p_1, m_1, a_1),..., (p_t, m_t, a_t)] of triplets satisfying conditions 1-4 described above. (Hint: A set of 18 elements exists where the only primes dividing its $m_k$ elements are 2,3 and 5).

A bonus "*" will be given for computing $A_0$ and $A_1$ from the found set, and explaining why every element of $A_n$ is divisible by one of the $p_k$ elements, but not equal to it.

Solution

Best opened after a real attempt

To be added.