NF杯2023(G)

　$F_N$ が $2$ で割り切れる回数と $3$ で割り切れる回数を求めればよい．結論から述べれば，一般に $${\rm ord}_2(F_{6m})={\rm ord}_2(m)+3, \quad {\rm ord}_3(F_{4m})={\rm ord}_3(m)+1$$ が成立する．このことを示す．まず，$\alpha=\dfrac{1-\sqrt{5}}{2},~\beta=\dfrac{1+\sqrt{5}}{2}$ とすると， $$F_n=\dfrac{\beta^n-\alpha^n}{\beta-\alpha}$$ となる．ここで，$L_n:=\alpha^n+\beta^n$ と定める．
　このとき，$L_n\mod{4}$ および $F_n\mod{4}$ は，以下によりともに周期 $6$ をもつ． $$\begin{array}{c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots \\ \hline L_n \mod{4} & 2 & 1 & 3 & 0 & 3 & 3 & 2 & 1 & \cdots \\ \hline F_n \mod{4} & 0 & 1 & 1 & 2 & 3 & 1 & 0 & 1 & \cdots \\ \end{array}$$ 　$x_n=F_{6n}/8$ とおくと，$x_0=0, ~ x_1=1, ~ x_{n+2}=18x_{n+1}-x_n$ であるから，$m$ が奇数のとき $F_{6m}/8$ は奇数である．すなわち，$F_{6m}$ は $2$ でちょうど $3$ 回だけ割れる．さらに，$n$ が $6$ の倍数であるとき， $$\dfrac{F_{2n}}{F_n}=L_n\equiv 2\pmod{4}$$ であるため，$F_{2n}/F_n$ は $2$ でちょうど $1$ 回だけ割れる．以下，帰納的に議論することで， $${\rm ord}_2(F_{6m})={\rm ord}_2(m)+3$$ が従う．
　$L_n\mod{9}$ および $F_n\mod{9}$ は，以下によりともに周期 $24$ をもつ． $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline L_n \mod{9} & 2 & 1 & 3 & 4 & 7 & 2 & 0 & 2 & 2 & 4 & 6 & 1 & 7 & 8 & 6 \\ \hline F_n \mod{9} & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 4 & 3 & 7 & 1 & 8 & 0 & 8 & 8 \\ \end{array}$$ $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c} n & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & \cdots \\ \hline L_n \mod{9} & 5 & 2 & 7 & 0 & 7 & 7 & 5 & 3 & 8 & 2 & 1 & \cdots \\ \hline F_n \mod{9} & 7 & 6 & 4 & 1 & 5 & 6 & 2 & 8 & 1 & 0 & 1 & \cdots \\ \end{array}$$ 　$n$ が $4$ の倍数であって $3$ の倍数でないとき，表により $F_n \mod{9}=3,6$ である．すなわち，$F_n$ は $3$ でちょうど $1$ 回だけ割り切れる．
　また，$n$ が $4$ の倍数であるとき， $$\dfrac{F_{3n}}{F_n}=\alpha^{2n}+\alpha^n\beta^n+\beta^{2n}=L_{2n}+1$$ となる．ここで，$2n$ は $8$ の倍数であることに注意すると，表から $$L_{2n}+1\equiv 2+1\equiv 3\pmod{9}$$ となるため，$F_{3n}/F_n$ は $3$ でちょうど $1$ 回だけ割り切れる．よって帰納的に $${\rm ord}_3(F_{4m})={\rm ord}_3(m)+1$$ が成り立つ．
　$N$ は $6$ の倍数であり，かつ $N$ が $2$ で割り切れる回数は $97$ 回なので，$F_N$ が $2$ で割り切れる回数は $97-1+3=99$ 回である．また，$N$ は $4$ の倍数であり，$N$ が $3$ で割り切れる回数は $48$ 回なので，$F_N$ が $3$ で割り切れる回数は $48+1=49$ 回である．$99,49\lt N=100!$ に注意すると， $${\rm gcd}(F_N,6^N)=2^{99}\cdot 3^{49}$$ なので，正の約数の個数は $(99+1)\times (49+1)=\bm{5000}$ である．