(3+√5)^1000の一の位，十の位、百の位を求めたいのですが分かりません。

(3+√5)^2=6*(3+√5)-4
を使うんでしょうけれど、√の処理が難しくて普通の合同式の
mod 1000っぽく計算できません…