0204132人目の素数さん
2019/12/03(火) 23:58:51.62ID:b5QWSNPE(3 + Sqrt[5])^n = a_n + b_n * Sqrt[5]
a_n, b_n ∈ {1, 2, …}
と書けます。
正の整数列 (a_n), (b_n) を↑で定義します。
a_1 = 3
b_0 = 1
です。
明らかに、
(3 - Sqrt[5])^n = a_n - b_n * Sqrt[5]
が成り立ちます。
(3 + Sqrt[5])^n + (3 - Sqrt[5])^n = 2*a_n
が成り立ちます。
5 < 3^2 より、 Sqrt[5] < 3
∴ 0 < 3 - Sqrt[5]
2 = Sqrt[4] < Sqrt[5]
∴ 3 - Sqrt[5] < 1
∴ 0 < 3 - Sqrt[5] < 1
∴ 0 < (3 - Sqrt[5])^n < 1
∴ 0 < 2*a_n - (3 + Sqrt[5])^n < 1
∴ 2*a_n - 1 < (3 + Sqrt[5])^n < 2*a_n
∴ (3 + Sqrt[5])^n の整数部分は 2*a_n - 1 である。
以上より、 a_n が計算できれば、 (3 + Sqrt[5])^n の整数部分を 1000 で割った余りは、
2*a_n - 1 mod 1000
で求まる。