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 Tortorella 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$).

-