例 8.1
ϕ(5) = 4 134≡1 (mod.5) 134−1 = 5×5712 ϕ(5) = 4 114≡1 (mod.5) 114−1 = 5×2928 ϕ(11) = 10 210≡1 (mod. 11) 210−1 = 11×93 ϕ(12) = 5 55≡1 (mod.12) 55−1 = 12×52 ϕ(60) = 60
µ 1−1
2
¶
× µ
1−1 3
¶ µ 1−1
5
¶
= 16 716≡1 (mod. 60) 716−1 = (7−1)(7 + 1)
×(72+ 1)(74+ 1)(78+ 1)
上の例で13の場合は4乗して初めて1 (mod.5) となるが，11の場合は2乗した段階ですで に 1 (mod.5) である．
aのべきの中でae≡1 (mod. m)となる最小のeをa の法m に関する指数という．
定理 24
aの法mに関する指数をeとする．このとき ak ≡1 (mod. m)となったとすればkは eの 倍数である．特にϕ(m)はeの倍数である．逆にいうと法mに関する指数となりうるのはϕ(m) の約数にかぎる．
証明 kを eで割った商をq，余りを rとする．
1≡ak =aeq+r≡ar (mod. m)
ここで 0<=r <1 であるが，もしr6= 0ならar≡1 (mod. m)となる正の整数rがあることに なりeの最小性に反する．ゆえに r= 0．つまり kはeの倍数である． ■
練習問題 8.1 (解答31)［奈良女子大改題］
(1) 素数pと1<=r <=p−1なる整数rに対して, 二項係数のについての等式rpCr=pp−1Cr−1
を証明し,pCr はpの倍数であることを示せ.
(2) 素数pに対して2p をpで割った余りを求めよ.
(3) 自然数nに対してnp を pで割った余りを推測し,数学的帰納法で証明せよ.
練習問題 8.2 解答32) aの法mに関する指数を eとする．整数ak の指数は e
(k, e) である．
算術級数の定理(ディリクレの定理)
初項a(>0) と公差 d(>0) がともに自然数でかつ互いに素であるような算術級数(無限等差数 列)の項の中には素数が無数に存在する．
算術級数の定理を完全に証明したのはディリクレ(Dirichlet)である(1837)．この定理の証明は 難しい．級数の理論を整数問題に応用する『解析的整数論』の発端となった．ここでa= 1の場合 について証明をしよう．
定理 25
mを任意の自然数とする． mt+ 1 型の素数が無限に存在する．
証明
【1】 4n−1 型の素数が無数にあることを示す．
4n−1型の素数が有限個しかないとし，その最大のものをpとする．4n−1 型の素数すべての 積に4をかけ1を減じた数をaとする．つまり
a= 4(3·7·11· · · ·p)−1 aが素数なら，これがpより大きい4n−1型の素数である．
aは合成数とする．aは4で割ると−1余るので奇数である．したがってその約数はすべて奇数 であるから，4で割って1または−1余る．4k+ 1型の数をいくらかけても4k+ 1型の数になる ので，4n−1 型の数の約数の中には必ず4n−1型の数がある．したがってaが合成数ならその素 因数の中に4n−1型のものがある．
ところがこれは3からpの4n−1型の素数のいずれとも互いに素であるから，それより大きい．
したがって pが4n−1 型の素数の最大のものであることと矛盾した．つまり4n−1 型の素数が 無数にあることが示された．
【2】 4n+ 1 型の素数が無数にあることを示す．
4n+ 1型の素数が無数にあることは簡単ではない．その証明にはフェルマの小定理が必要であ る．フェルマの小定理を応用して4n+ 1 型の素数が無数にあることを証明しよう．
その基本となる事実は，x2+ 1の形をした数の素因数は2 かまたは4n+ 1型の素数にかぎる，
ということである．いくつか調べてみると
12+ 1 = 2, 22+ 1 = 5, 32+ 1 = 2·5, 42+ 1 = 17, 52+ 1 = 2·13, 62+ 1 = 37, · · · で確かにそうなっている．
つねに成立することは，次のように示される．
x2+ 1が 2以外の素数pで割り切れるとする．
x2+ 1≡0 (mod. p) つまり
x2≡ −1 (mod. p) ゆえに
x4≡1 (mod. p)
ところが xの指数は4である．そうでなければ4の約数の1か2の指数で x≡1 (mod. p) , または x2≡1 (mod. p) いずれからも x2+ 1≡0 (mod. p)とあわせて
−1≡1 (mod. p)
となる． p6= 2なのでこれはあり得ない．したがって定理24により，p−1は4の倍数である．
これをp−1 = 4nとすれば
p= 4n+ 1
この事実の応用として4n+ 1型の素数が無数にあることが示される．
4n+ 1型の素数が有限個しかないとする．その最大のものをpとし，2とそれら4n+ 1型の素 数すべての積の平方に1を加えた数をaとする．つまり
a= (2·5·13· · · ·p)2+ 1
このとき，もしaが素数ならa= 4(5·13· · · ·p)2+ 1より4n+ 1 型の素数である．
もし合成数ならその素因数qは奇数であるから2ではなく4n+ 1型の素数である．しかしaは pまでの4n+ 1 型の素数では割り切れないから，q はpより大きい4n+ 1型の素数である．
つまりpが4n+ 1型の素数で最大のものであることに反した．ゆえに4n+ 1型の素数が無数 にあることが示された．
【3】 mt+ 1 型の素数は無数に存在することを示す．
mを2以上の任意の整数とする．初項が1で公差がmの等差数列の中に無数の素数が存在して いる．
この証明は，m= 4の場合つまり4n+ 1型の素数が無数に存在することの証明を一般化する ことで得られる．4n+ 1型の素数が無数に存在することの証明に現れたx2+ 1は何か．それは定 理19のF4(x)に他ならない．1の原始4乗根±iのみを根とする多項式である．
そこで与えられたmに対して Fm(x)を考えよう．まずaを任意の整数としてFm(a)6=±1 の ときFm(a)の素因数はmの約数，またはmt+ 1の型のものにかぎられことを示さなければなら ない．定理22によって次の等式が成り立つ．
xm−1 =Fm(x)G(x) ここで G(x)は xの整数係数の整式である．ゆえに
am−1 =Fm(a)G(a)
において，Fm(a), G(a)は整数であるから，いま素数pを Fm(a)の素因数とすれば，am−1も pの倍数である．つまり
am≡1 (mod. p) aの指数を eとする．定理21からeはmの約数で
m=ef
とおける．ここでm > eとすれば xm−1はxe−1を因数にもつが，一方xe−1とFm(x)は共 通因数をもたないので(Fm(x)の根はm乗してはじめて1となるものであるから)
xm−1 = (xe−1)Fm(x)H(x)
ここでG(x) = (xe−1)H(x)が整数係数なのでH(x)も整数係数の整式である．両辺をxe−1 で 割る．
xe(f−1)+xe(f−2)+· · ·+xe+ 1 =Fm(x)H(x) x=aを代入してae≡1 (mod. p)を用いれば
f ≡Fm(a)H(a)≡0 (mod. p) ゆえに pはf の約数，したがって m=ef の約数である．
次にm=eならmがaの指数であるからmはp−1の約数である．つまりp=mt+ 1と書け る．ゆえに，Fm(a)6=±1のときFm(a)の素因数はmの約数，またはmt+ 1の型のものである ことが示せた．特に aをmに含まれるすべての素因数の積の倍数とすれば，am≡1 (mod. p) より(a, p) = 1なのでpは mの約数ではあり得ない．したがってこのようなaをとるならpは 必ずmt+ 1の型の素数である．
例えばm= 12とする．
x12−1 = (x6−1)(x6+ 1) = (x6−1)(x2−1)(x4+x2+ 1) で F12(x) =x4+x2+ 1 ．a= 6とすると
F12(6) = 64−62+ 1 = 1261 = 13×97 で
13≡1, 97≡1 (mod. 12)
Fm(a)6=±1 を仮定しているが，Fm(a) =±1となる a はもちろん有限個なのでそれ以外のa はをとればよい．ゆえに任意の整数m に対してmt+ 1型の素数が存在することが示された．
もしmt+ 1 型の素数が有限個しかなければ，最大のものをp=mt+ 1とする．
m は任意なので m の代わりにmpをとると p0 =mpt+ 1 型の素数もまた存在する．ところ が p0 は mt+ 1型の素数でもありしかもpより大きい．したがってpの最大性と矛盾するので，
mt+ 1 型の素数は無数に存在する． ■
次の練習問題と演習問題は，『めざせ，数学オリンピック』(J.コフマン，現代数学社)に教えら れた．
練習問題 8.3 (解答33) 因数分解
x2k+1+ 1 = (x+ 1)(x2k−x2k−1+x2k−2− · · · −a+ 1)
を活用して，任意の自然数 nに対して(n!)2+ 1の素因数はすべて4n+ 1型の素数であることを 示せ．これから4n+ 1 型の素数が無数にあることを示せ．