素数全書練習問題1.8 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

問題1.7によく似ているが、与えられた数の素因子のどれか一つはmod 4で1になるという部分がうまくいかないため、全く違う解法となった。

qを $(2\cdot 3 \cdots p)^2+1$ の素因子の一つとすると、 $(2\cdot 3 \cdots p)^2\equiv -1 (mod\quad q)$

一方、フェルマーの小定理より

$(2\cdot 3 \cdots p)^{q-1}\equiv 1 (mod\quad q)$

であるが、もし (q-1)/2 が奇数であると

$(2\cdot 3 \cdots p)^{q-1}\equiv [(2\cdot 3 \cdots p)^2 ]^{(q-1)/2}\equiv (-1)^{(q-1)/2}\equiv -1 (mod\quad q)$

となり、矛盾してしまう。よって(q-1)/2 は偶数であり、q-1は4の倍数となり
q≡1 (mod 4) が結論される。後は問題1.7と同じ論法である。面白いことに素因子はすべてmod 4で1という強い結果が証明されたことになる。

後半のmod 3の場合であるが、 $(2\cdot 3 \cdots p)^2+1$ の形でいけるかと思っていたら

$(2\cdot 3\cdot 5)^2+1 = 901 = 17\cdot 53 \quad\quad 7\equiv 2 (mod\quad 3),\quad 53\equiv 2 (mod\quad 3)$

なのでだめなのである。ちょっとズルイが円分多項式に頼ると

$n=(2\cdot 3 \cdots p)^2+(2\cdot 3 \cdots p)+1$

の形がよい。 $x^3-1=(x^2+x+1)(x-1)$ が成立しているのがミソである。この恒等式を $x=2\cdot 3 \cdot 5 \cdots p$ として、nの任意の素因子qに対して mod q の世界に持ち込むと、

$x^3 -1 \equiv (x^2+x+1)(x-1) \equiv 0 (mod q)$ つまり $x^3 \equiv 1 (mod\quad q)$

もし、q≡2 (mod 3)ならば、q-2=3m として、 $1\equiv x^{q-1}\equiv x^{3m+1}\equiv x\cdot (x^3)^m\equiv x (mod\quad q)$ すわなち $x\equiv 1(mod\quad q)$ であり、 $x^2+x+1\equiv 3(mod\quad q)$ 。これと $x^2+x+1\equiv 0 (mod\quad q)$ は q=3 でない限り矛盾してしまう。よって、q≡1 (mod 3)でなければならない。

この証明の最後のごちゃっとした部分をすっきりさせるには、フェルマーの小定理 $x^{q-1}\equiv 1 (mod\quad q)$ から、mod q の世界では、xの位数 nは q-1の約数であることを利用する。（これの証明は、q-1=mn+r (m,r:整数, 0≠r＜n）と表すと、 $x^r\equiv x^{q-1-mn}\equiv x^{q-1}\cdot (x^n)^{-m}\equiv 1 (mod\quad q)$ となるが、位数の定義と r＜n より矛盾なので、r=0となる。)

これを使えば、前半では、 $x=2\cdot 3 \cdots p$ の位数は4 から 4|(q-1)、後半ではxの位数が3から、3|(q-1) がただちに結論される。