# Finding $a \bmod b$ where $a,b$ are large Fibonacci numbers

For moderately large values of $b$ we can use Chinese Remainder Theorem, by factorizing $b$. But for very large values of $b$, (for example $b$ is the 1000th Fibonacci number) factorization will take a lot of time. Is there any other efficient way of finding $a \bmod b$ ( remainder of $b$ divide $a$ ). Does the problem become simple (when compared to the problem for any integer $b$) given the fact that $b$ is a Fibonacci number?

-

$F_n\equiv 0 \pmod {F_n}$ and $F_{n+1}\equiv F_{n-1}\pmod {F_n}$ means that by induction: $F_{n+k}\equiv F_kF_{n-1}\pmod{F_n}$.

Then, again by an induction argument, we can see that if $m=nq+r$ then $F_{m} \equiv F_r F_{n-1}^q \pmod {F_n}$

This is made easier because $F_{n-1}^2 \equiv (-1)^n \pmod {F_n}$.

-
Nice, this just shows that $F_{nq+r}\pmod{F_n}\in\{\pm F_r,\pm F_{n-r}\}$ since we can take always even $q$s by tweaking $r$, allowing it to be negative but with $|r|<n$. – Jack D'Aurizio Jul 20 '14 at 22:15

Well, Euclid's algorithm is an efficient way to compute $a \pmod{b}$ given any $a$ and $b$ ... much better than factoring.

The fact that the numbers are Fibonacci simplifies the algorithm somewhat, but if $a < b$ then you're just asking for the value of $a$, so you'll always have to compute some potentially big Fibonacci numbers.

Note that $F_{n+1} = F_n + F_{n-1} \equiv F_{n-1} \pmod{F_n}$. Similarly, $F_{n+2} \equiv F_{n-1} \pmod{F_n}$. If you think about the pattern a little bit, you'll realize that modulo $F_{n-1}$ we have that $F_{n+k} = F_k * F_{n-1}$. You can keep recursing more if you like, so you never have to compute any Fibonacci numbers greater than $b$.

-

Have a look here:

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)

-