この「 \( n^4+n^3+n^2+n+1 \) 」に関する３つの記事は
円分多項式\(F_{k}(x)\)とは方程式\(F_{k}(x)=0\)が1の原始k乗根全てが根であるような多項式のことです。 (1の原始k乗根は1のk乗根で、k乗して初めて1になるような数) 。
円分多項式と \( n^4+n^3+n^2+1+1 \) の素因数分解の間にはどんな関係があるのでしょうか。
後で%orという論理演算子を使いたいので、それを定義しているto_poly_solveパッケージを読み込んでおきます。
(%i1) load(to_poly_solve);
次に円分多項式を定義します。この定義はこちらのブログ記事からお借りしました。
(%i2) cyclotomic(k, z) := trigrat(product(if gcd(j, k) = 1 then z - exp(2*%pi *%i*j/k) else 1, j, 1, k));
$$ \tag{%o2} \mathrm{cyclotomic}\left(k , z\right):= \\ \mathrm{trigrat}\left(\mathrm{product}\left(\mathbf{if}\;\mathrm{gcd}\left(j , k\right)=1\;\mathbf{then}\;z-\exp \left(\frac{2\,\pi\,i\,j}{k}\right)\;\mathbf{else}\;1 , j , 1 , k\right)\right) $$
この定義でk=5とすることで、1の原始5乗根を全て根として持つ円分多項式 \( F_{5}(x) \) を求めることができます。
(%i3) define(F[5](x), cyclotomic(5,x));
$$ \tag{%o3} F_{5}(x):=x^4+x^3+x^2+x+1 $$
そうなんです。\( n^4+n^3+n^2+1+1 \) は実は \( F_{5}(n) \) そのものだったのです。そして円分多項式では次のことが成り立ちます。
任意の自然数kについて、任意の素数pについて適当な自然数nがあり下記の(%o4)の式が成立するならば(%o5)が成り立ちます。また逆に(%o5)の後半が成り立つ素数pについてある自然数nで(%o4)が成り立ちます。
(%i4) mod(F[k](n),p)=0;
$$ \tag{%o4} F_{k}(n) \rm{mod} p=0 $$
(%i5) (mod(k,p)=0) %or (mod(p,k)=1);
$$ \tag{%o5} \left(k \rm{mod} p=0\right) \lor \left(p \rm{mod} k=1\right) $$
既にk=5の場合に(%i4)⇒(%i5)を見てきました。ではk=6ではどうでしょうか。やってみましょう。k=6として円分多項式を求め、そこにx=1,,,25を代入し、素因数分解してみます。
(%i6) k:6;
$$ \tag{%o6} 6 $$
(%i7) maxN:25;
$$ \tag{%o7} 25 $$
以下にk=6での円分多項式を求めます。
(%i8) define(F[k](x), cyclotomic(k,x));
$$ \tag{%o8} F_{6}(x):=x^2-x+1 $$
1,,,25を全て含むリストを作ります。
(%i9) makelist(i,i,1,maxN);
$$ \tag{%o9} \left[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , \\ 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 \right] $$
\(F_{6}(x)\) をリストの要素に適用します。
(%i10) map(F[k],%);
$$ \tag{%o10} \left[ 1 , 3 , 7 , 13 , 21 , 31 , 43 , 57 , 73 , 91 , 111 , 133 , 157 , 183 , 211 , \\ 241 , 273 , 307 , 343 , 381 , 421 , 463 , 507 , 553 , 601 \right] $$
リストの要素をifactors()という関数で素因数分解します。factors_onlyの値をtrueとしておくことで冪乗を無視して素因数だけを求めることが出来ます。
(%i11) map(ifactors,%), factors_only:true;
$$ \tag{%o11} \left[ \left[ \right] , \left[ 3 \right] , \left[ 7 \right] , \left[ 13 \right] , \left[ 3 , 7 \right] , \left[ 31 \right] , \left[ 43 \right] , \left[ 3 , 19 \right] , \left[ 73 \right] , \\ \left[ 7 , 13 \right] , \left[ 3 , 37 \right] , \left[ 7 , 19 \right] , \left[ 157 \right] , \left[ 3 , 61 \right] , \left[ 211 \right] , \left[ 241 \right] , \left[ 3 , 7 , 13 \right] , \\ \left[ 307 \right] , \left[ 7 \right] , \left[ 3 , 127 \right] , \left[ 421 \right] , \left[ 463 \right] , \left[ 3 , 13 \right] , \left[ 7 , 79 \right] , \left[ 601 \right] \right] $$
全部一つのリストにします。
(%i12) apply(append,%);
$$ \tag{%o12} \left[ 3 , 7 , 13 , 3 , 7 , 31 , 43 , 3 , 19 , 73 , 7 , 13 , 3 , 37 , 7 , 19 , 157 , 3 , \\ 61 , 211 , 241 , 3 , 7 , 13 , 307 , 7 , 3 , 127 , 421 , 463 , 3 , 13 , 7 , 79 , 601 \right] $$
そして重複要素を捨てて、小さい順にソートします。
(%i13) sort(unique(%));
$$ \tag{%o13} \left[ 3 , 7 , 13 , 19 , 31 , 37 , 43 , 61 , 73 , 79 , 127 , 157 , 211 , 241 , \\ 307 , 421 , 463 , 601 \right] $$
各要素をpとしてmod(p,6)を計算してみます。
(%i14) map(lambda([p],mod(p,k)),%);
$$ \tag{%o14} \left[ 3 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 \right] $$
確かに、pを6で割ると1余るか、6を割り切る3であるか、どちらかですね。
