$\\\{F_n\\\}$, $\\\{L_n\\\}$ をそれぞれFibonacci数列とLucas数列とする．すなわち，
- $F_0 = 0$, $F_1 = 1$, $n \geq 0$ について $F_{n+2} = F_{n+1} + F_{n}$
- $L_0 = 2$, $L_1 = 1$, $n \geq 0$ について $L_{n+2} = L_{n+1} + L_{n}$

とする．このとき，$n \geq 1$ について
$$a_{n+2} + 1 = (a_{n+1} + 1) + (a_{n} + 1),\quad b_{n+2} - 1 = (b_{n+1} - 1) + (b_{n} - 1)$$

であることから，$a_n = F_{n+2} -1$, $b_n = F_{n-1}+1$ と計算できる．\
　すると，Fibonacci数列の一般項による表示を用いて，以下の事実を確かめることができる：
- $a_{4n+1} = F_{4n+3} - 1 = F_{2n+2}L_{2n+1}$
- $b_{4n+1} = F_{4n} + 1= F_{2n-1}L_{2n+1}$

なお，一般に $F_{n+m}+(-1)^mF_{n-m}=F_nL_m$ が成り立つ．したがって，
$$\gcd(a_{4n+1}, b_{4n+1}) = L_{2n+1}\cdot\gcd(F_{2n+2}, F_{2n-1})$$
である．さらに，
$$
\gcd(F_{n+3}, F_{n}) = \gcd(F_{n}+2F_{n+1}, F_{n}) = \gcd(2F_{n+1}, F_{n})
$$

であり，$\gcd(F_{n+1}, F_{n}) = 1$ より $\gcd(F_{n+3}, F_{n}) = \gcd(F_{n}, 2)$ である．ここで周期性より $F_n$ が偶数であることと $n$ が $3$ の倍数であることが同値なので，$\gcd(F_{n}, 2)$ は $n$ が $3$ の倍数のとき $2$, それ以外で $1$ である．\
　さて $N=123456789$ について，$M = (N-1)\/4$ とおくと $M$ は整数で，$2M-1$ は $3$ の倍数であるから，
$$
\gcd(a_{N}, b_{N}) = L_{2M+1}\cdot \gcd(F_{2M+2}, F_{2M-1}) = L_{2M+1}\cdot \gcd(F_{2M-1}, 2) = 2L_{2M+1}
$$

と計算できる．\
　あとは $2L_{2M+1}$ を $957=3\times 11 \times 29$ で割った余りを求めるとよい．$\bmod 3$, $\bmod {11}$, $\bmod {29}$ でのLucas数列の周期がそれぞれ $8$, $10$, $14$ であることが確かめられ，それにより以下がわかる：
- $2M+1 \equiv 3 \pmod 8$ より， $L_{2M+1} \equiv 1 \pmod 3$
- $2M+1 \equiv 5 \pmod {10}$ より， $L_{2M+1} \equiv  0 \pmod {11}$
- $2M+1 \equiv 1 \pmod {14}$ より， $L_{2M+1} \equiv 1 \pmod {29}$

よって，中国剰余定理により $L_{2M+1} \equiv 88 \pmod {957}$ と求められるから，答えは $\textbf{176}$ である．
公式解説
https://onlinemathcontest.com/contests/omc112/editorial/3383
　数列 $\\\{a_n\\\}$, $\\\{b_n\\\}$ を以下のように定めます：
- $a_1 = 1$, $a_2 = 2$, $n \geq 1$ について $a_{n+2} = a_{n+1} + a_{n} + 1$
- $b_1 = 1$, $b_2 = 2$, $n \geq 1$ について $b_{n+2} = b_{n+1} + b_{n} - 1$

$a_{123456789}$ と $b_{123456789}$ の最大公約数を $957$ で割った余りを求めてください．