多項式x²-x+1 の反復合成と素数の無限性証明

f(x)=x^2 - x + 1 として、f^2(x)=f(f(x)), f^3(x)=f(f(f(x))), ... を計算してみる。
f^2(x)=x^4 - 2*x^3 + 2*x^2 - x + 1
f^3(x)=x^8 - 4*x^7 + 8*x^6 - 10*x^5 + 9*x^4 - 6*x^3 + 3*x^2 - x + 1
f^4(x)=x^16 - 8*x^15 + 32*x^14 - 84*x^13 + 162*x^12 - 244*x^11 + 298*x^10 - 302*x^9 + 258*x^8 - 188*x^7 + 118*x^6 - 64*x^5 + 30*x^4 - 12*x^3 + 4*x^2 - x + 1
どれも定数項が1となっている。
証明してみよう。定数項とはx=0を代入した値だから、
任意の自然数ｎで f^n(0)=1 であることを示せばよい。
f(0)=1, f(1)=1 だから、
f^n(0)=f^{n-1}(1)=1. よって示された。

数列{a_n}を
a_0=2, a_{n+1}=f(a_n) と定義する。
a_n≠1 が帰納的に分かり、またf^k(x)の定数項が1であることより、
m≠n なら a_m, a_n は互いに素。
よって各a_n の素因数に同じものは登場しないから素数を無限に生成できる。

※なぜ互いに素か？
m≠nのとき、m>nとしてよく、m-n=kとおくとk>0だからa_m=a_{n+k}=f^k(a_n)≡1(mod a_n) よって互いに素。