n ≧ 1 とする。

(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

で求まる。