Archive for April, 2022

Find the Last Three Digits of the 2022nd Fibonacci Number

Posted: April 29, 2022 in Mathematics
Tags: , , ,
0

So, here is the problem. Given that F_n = \{1, 1, 2, 3, 5, 8, \ldots\}. We want to find F_{2022}\pmod{1000}

By Binet’s formula (click here for explanation), we have

\displaystyle F_n = \frac{1}{\sqrt5} \left(\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n\right)

Hence, the 2022nd Fibonacci number would be

\displaystyle F_{2022} = \frac{1}{2^{2022}\sqrt5} \left(\left(1+\sqrt5\right)^{2022}-\left(1-\sqrt5\right)^{2022}\right)

Expand it using Binomial Theorem and take mod 125, we get

\displaystyle 2^{2021} F_{2022} \equiv \binom{2022}{1} + \binom{2022}{3}5 + \binom{2022}{5}25 \pmod{125}

Since 2 and 5 are relatively prime, we apply the Euler’s theorem to reduce 2^{2021}.

\phi(125) = 125 \cdot \frac45 = 100

\therefore 2^{2021} \equiv 2^{21} \equiv (2^{10})^2\cdot2 \equiv 24^2\cdot2 \equiv 576 \cdot 2 \equiv 152 \equiv 27 \pmod{125}

Calculate the rest of the terms on the right,

2022 \equiv 22 \pmod{125}

\displaystyle \binom{2022}{3}5 \equiv \frac{2022\cdot2021\cdot2020\cdot5}{6} \equiv 337 \cdot 21 \cdot 20 \cdot 5 \equiv 8700 \equiv 75 \pmod{125}

\displaystyle \binom{2022}{5}25 \equiv \frac{22\cdot21\cdot20\cdot19\cdot18\cdot25}{5\cdot4\cdot3\cdot2} \equiv 88 \cdot 450 \equiv 88\cdot75 \equiv 100 \pmod{125}

Hence,

27 F_{2022} \equiv 22+75+100 \equiv 72 \pmod{125}

3 F_{2022} \equiv 8 \pmod{125}

So, there exists an integer k such that

3F_{2022} = 125k + 8

Then take mod 3 to find k,

0 \equiv 2k + 2 \pmod{3}

k \equiv 2 \pmod{3}

So,

3F_{2022} = 258

F_{2022} \equiv 86 \pmod{125}

Next, we have to find F_{2022} \mod{8}

F_n = \{1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, \ldots \} \pmod{8}

So, the period is 12 and 2022 \equiv 6 \mod{12} hence

F_{2022} \equiv 0 \pmod{8} \equiv 86 \pmod{125}

For some integers a and b we have

F_{2022} \equiv 8a \equiv 125b + 86 \pmod{1000}

0 \equiv 5b + 6 \pmod{8}

b\equiv 2 \pmod{8}

Therefore,

F_{2022} \equiv 125b + 86 \equiv 125\cdot2+86 \equiv 336 \pmod{1000}

So the last three digits of the 2022nd Fibonacci number is 336.