Remainders of Fibonacci numbers

Question

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$?

We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. There can only be finitely (around $a^2$) such pairs. So some two pairs coincide. Once we have that, we also have periodicity backward/forward. But it's still not clear for which $a,b$ we'll have $F_i\equiv b\pmod a$.

Answer 1

I used the following lua code to generate all the possible values of a and b where a > b up to 100. Then, show the result of b modulo a. The results are here (please note that in the results, the percentage sign is used as the modulo operator). Below is the code i used to generate it. (the .. is the concatenation operator (joins 2 pieces of text together))

strin=""
for a = 1, 100 do
    for b = 0 (a-1) do
        strin = strin .. "a=" .. a .. " b=" .. b .. "   b%a=" .. b%a .. "\010"
    end
end
print(strin)

And, here is the code I used to check to make sure a > b is always true for the numbers generated by the code in the previous (above) paragrah. Even thou this code doesn't use any external variables so it will always display the same output, you can still check it again if you want using this code. Just enter the code into a lua compiler and if there are any times when a < b then it will show you the value of a and of b.

strin=""
for a = 1, 100 do
    for b = 0, (a-1) do
        if a > b then
            strin = strin .. "a=" .. a .. " b=" .. b .. "\010"
        end
    end
end
print(strin)

Then, we want to know what the total number of possible values for a and b are when a or b are no more than 100. So, i modified the coding a little bit, and found that the total possible values for a and b up to 100 is $5050$. The code I used to find it is as follows.

num = 0
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        num = num + 1
    end
end
print(num)

Next, to check for Fibonacci numbers. All Fibonacci numbers ( not Fibonacci sequence ) less than or equal to 100 are: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, and 89. Thus, I created a lua program to figure out which b modulo a are Fibonacci. The results are here. The total amount of Fibonacci numbers found is 986 ( $19.\overline{5247}$% of the total numbers tested ). The following is the code I used.

fibs = {0;1;1;2;3;5;8;13;21;34;55;89}
strin=""
for a = 1, 100, 1 do
    for b = 0, (a-1), 1 do
        for k, v in pairs(fibs) do
            if b % a == v then
                strin = strin .. "a=" .. a .."  b=" .. b .. "   b%a=" .. b%a .. "\010"
            end
        end
    end
end
print(strin)

All-In-All, yes, because there are tons of Fibonacci numbers that are b modulo a ( and even a modulo b ) just in the first 100 values of a and b numbers alone.

In a related topic, I just switched it around a little bit to see a modulo b up to 100 where a > b. The result is here. The following is the code I used.

local strin=""
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        strin = strin .. "a=" .. a .. " b=" .. b .. "   a%b=" .. a%b .. "\010"
    end
end
print(strin)

Then, pulling the Fibonacci numbers out of that was just another simple program. The results can be found here. The total matches is 2399 ( almost half - $ 47.\overline{5049} $% ). The following is the code I used to generate it.

fibs = {0;1;1;2;3;5;8;13;21;34;55;89}
strin = ""
for a=1, 100, 1 do
    for b = 0, (a-1), 1 do
        for k, v in pairs(fibs) do
            if a%b==v then
                strin = strin .. "a=" .. a .. " b=" .. b .. "   a%b=" .. a%b .. "\010"
            end
        end
    end
end
print(strin)

Answer 2

There are infinitely counterexamples, and many can be found as follows. First, for a positive integer $a$, let $\kappa(a)$ denote the period of the Fibonacci numbers modulo $a$. That is, it is the smallest positive integer such that $F_{\kappa(a)+n}=F_n$ for all $n$. The number $\kappa(a)$ is known as the Pisano period, or the Wall number of $a$. As the values of the Fibonacci sequence modulo $a$ repeat after $\kappa(a)$, it can only have at most $\kappa(a)$ residues modulo $a$. So, as long as $\kappa(a) < a$ then there must exist $b < a$ such that no Fibonacci number is equal to $b$ mod $a$.

Actually, we can do a bit better as many of the residues modulo $a$ will be repeated within each period. We have,

• $F_1=F_2=1$.
• $F_{\kappa(a)-n}\equiv (-1)^{n-1}F_n$.

The first of these reduces the number of residue classes of the Fibonacci sequence by 1, and the second reduces it by the number of odd $n < \kappa(a)/2$, and there are $\lceil\kappa(a)/4-1/2\rceil$ possible values of $n$. Also, as long as $\kappa(a) > 3$, these relations are all independent, so there are at least \begin{align} a-\kappa(a)+1+\lceil\kappa(a)/4-1/2\rceil=\lceil a-3\kappa(a)/4+1/2\rceil&&{\rm(1)} \end{align} values of $b < a$ such that no Fibonacci number is equal to $b$ modulo $a$. Note also that $F_3=2\not\equiv0$ for any $a > 2$, so we have $\kappa(a) > 3$ for all $a > 2$. So, there exists at least one $b < a$ such that no Fibonacci number is equal to $b$ modulo $a$ so long as $\kappa(a) < (4a+2)/3$.

To quickly compute upper bounds for $\kappa(a)$ the following facts can be used (summarised in this paper by Elsenhans and Jahnel).

1. $\kappa(2)=3$, $\kappa(5)=20$.
2. For prime $p\equiv\pm1$ (mod 5), then $\kappa(p)\mid(p-1)$
3. For odd primes $p\equiv\pm2$ (mod 5), then $\kappa(p)\mid2(p+1)$
4. For prime $p$ and $r\ge1$ then, $\kappa(p^r)\mid\kappa(p)p^{r-1}$.
5. If $a=a_1a_2\cdots a_N$ where $a_i$ are pairwise coprime, then $\kappa(a)$ divides the least common multiple of $\kappa(a_1),\kappa(a_2),\ldots,\kappa(a_N)$.

Just the second statement above is enough to generate infinitely many examples. For any prime $p\equiv\pm1$ (mod 5), we have $\kappa(p)\le p-1$, so there exists at least $(p+5)/4$ values of $b < p$ such that no Fibonacci number is equal to $b$ mod $p$. For example, taking $p=11$, a quick calculation shows that this is the case with $b=4,6,7,9$. We can also find examples by using statement 5 above and multiplying together comprime $a_i$ where the $\kappa(a_i)$ have plenty of common factors.