# Relatively prime numbers formula

Here is a problem I cannot manage with:

Find two relatively prime positive numbers $p$, $q$ that satisfy:

Sequence $\{pn + q\}_{n=0,1,2,\ldots}$ does not contain any Fibonacci number.

Any ideas how to touch it?

-
Probably the index should be $n$. – Giuseppe Apr 21 '12 at 17:45

Write down the Fibonacci sequence modulo the first few primes, and note the periods (A060305):

modulo 2  -- period 3
modulo 3  -- period 8
modulo 5  -- period 20
modulo 7  -- period 16
modulo 11 -- period 10


So the Fibonacci sequence modulo 55 has period 20. That is not long enough to hit all of the 40 numbers between 0 and 55 that are relatively prime to 55.

(But in fact already the sequence modulo 11 itself is too short to hit everything, because there are necessarily repetitions in it. Indeed, neither of $4$, $6$, $7$, nor $9$ are in the sequence, so there is no Fibonacci number of the forms $11n+4$, $11n+6$, $11n+7$, or $11n+9$).

-

P=2-2(N+1)+3-(3(2N+1))+(6N±1)-{(6N±1)•(6n±1)}, where P does not equal 1, and where P equals all prime numbers, and where N equals all natural whole numbers from 1, 2, 3... Etc.

To think that something deemed so complex could be reduced to such a simple and complete formula. My, my.

-
It is difficult to tell what you are trying to say. – robjohn Nov 4 '12 at 3:17