演習問題

F12(x) = (x¹²−1)(x²−1)

(x⁶−1)(x⁴−1) =x⁴−x²+ 1 pが素数なら

Fp(x) = x^p−1

x−1 =x^p−1+x^p−2+· · ·+ 1 Fp^e(x) = x^pe−1

x^pe−1−1 =x^{pe−1(p−1)}+x^{pe−1(p−2)}+· · ·+ 1 練習問題 7.1 (解答27) Fn(x)の定数項はn= 1の場合以外+1であることを示せ．

練習問題 7.2 (解答28) Fn(x)の第二項(ϕ(n)−1次の項)の係数は−µ(n)に等しいことを示せ．

つまり1の原始n乗根の和はµ(n)である．

練習問題 7.3 (解答29) αを1の原始n乗根とすれば α^k (k= 0, 1, · · ·, n−1)

がすべてのn 乗根で，そのうち(k, n) = 1なるkに対するものがちょうど原始 n乗根になるこ とを示せ．

練習問題 7.4 (解答30) 次のことを示せ．

(1) 互いに素な二つの整数a, bに対し，1の a乗根とb 乗根をすべての組合せについて掛けて 得られるab 個の積が1のab乗根の全部になる．

(2) 1の 原始a乗根と 原始b 乗根をすべての組合せについて掛けるなら1の 原始ab乗根の全 部が得られる．

(4) mをnと互いに素な正の整数とする．このとき，(1 +α^m)(1 +α^2m)· · ·(1 +α^(n−1)m)の値 を求めよ．

演習問題 26 (解答26)［01京大理系］

p を2以上の整数とする．2以上の整数 n に対し，次の条件(イ)，(ロ)をみたす複素数の組 (z1, z2, · · ·, zn)の個数を an とする．

(イ) k= 1, 2, · · ·, nに対し，zkp= 1かつ，zk6= 1 (ロ) z1z2· · ·zn= 1

このとき次の問いに答えよ．

(1) a3を求めよ．

(2) an+2 をan ， an+1 の一方または両方を用いて表せ．

(3) an を求めよ．

演習問題 27 (解答27)［01京都府立医大］

0でない複素数からなる集合Gは次を満たしているとする．

Gの任意の要素z, wの積zwは再びGの要素である．

(1) ちょうどn個の複素数からなる Gの例をあげよ．

(2) ちょうどn個の複素数からなる Gは (1)の例以外にないことを示せ．

8 フェルマの小定理

8.1 フェルマの小定理

ここではいわゆる「フェルマの小定理」呼ばれる定理の証明とその応用を学ぶ．「フェルマの小定 理」は高校数学の範囲で十分証明できる．それを練習問題にしておいた．その解答は合同式の記号 も使わないでしておいた．「フェルマの小定理」の意味はさらに次節で学ぶ．まず「フェルマの小定 理」とそれを一般的にした「オイラーの定理」を証明しよう．その応用として，「4n+1型の素数が 無限に存在すること」，および循環小数への応用を学ぼう．

定理 23 (オイラーの定理)

mを正整数とし aをmと互いに素な整数とする．このとき

a^ϕ(m)≡1 (mod. m) (32)

が成り立つ．とくに m=p(素数)に対しては, (a, p) = 1のとき

a^p−1≡1 (mod. p) (33)

が成り立つ．これをフェルマの定理という．

証明 mを法とする既約類の個数はϕ(m)個ある．その一組を x1, x2, · · ·, xϕ(m)

とする．このとき

ax1, ax2, · · ·, axϕ(m)

もまた一組の既約剰余系である．なぜなら (a, m) = 1より

x≡y (mod. m) ⇐⇒ ax≡ay (mod. m)

であるから xが剰余系ならax も剰余系である．つまりxと m を法として合同な整数の集合と すれば，その集合の要素にすべてaを乗じた整数の集合は確かにaxと合同な整数の全体なってお り,axも剰余系である．さらにxがmと互いに素ならaxも mと互いに素なので，既約剰余系 からは既約剰余系が得られることもわかる．

したがって二つの数の集合

{x1, x2, · · ·, xϕ(m)} と {ax1, ax2, · · ·, axϕ(m)} の各要素はmを法として互いに合同なものが一対一に対応している．

その積はmを法として互いに合同である．つまり

x1x2· · ·xϕ(m) ≡ ax1ax2· · ·axϕ(m) (mod. m)

≡ a^ϕ(m)x1x2· · ·xϕ(m) (mod. m) (x1x2· · ·x_ϕ(m), m) = 1であるから

a^ϕ(m)≡1 (mod. m) である．オイラーの定理(32)が示された．

m=pならϕ(p) =p−1であるから，オイラーの定理の特別な場合としてフェルマの定理(33)

が成り立つ． ■ 

例 8.1

ϕ(5) = 4 13⁴≡1 (mod.5) 13⁴−1 = 5×5712 ϕ(5) = 4 11⁴≡1 (mod.5) 11⁴−1 = 5×2928 ϕ(11) = 10 2¹⁰≡1 (mod. 11) 2¹⁰−1 = 11×93 ϕ(12) = 5 5⁵≡1 (mod.12) 5⁵−1 = 12×52 ϕ(60) = 60

µ 1−1

2

¶

× µ

1−1 3

¶ µ 1−1

5

¶

= 16 7¹⁶≡1 (mod. 60) 7¹⁶−1 = (7−1)(7 + 1)

×(7²+ 1)(7⁴+ 1)(7⁸+ 1)

上の例で13の場合は4乗して初めて1 (mod.5) となるが，11の場合は2乗した段階ですで に 1 (mod.5) である．

aのべきの中でa^e≡1 (mod. m)となる最小のeをa の法m に関する指数という．

定理 24

aの法mに関する指数をeとする．このとき a^k ≡1 (mod. m)となったとすればkは eの 倍数である．特にϕ(m)はeの倍数である．逆にいうと法mに関する指数となりうるのはϕ(m) の約数にかぎる．

証明 kを eで割った商をq，余りを rとする．

1≡a^k =a^eq+r≡a^r (mod. m)

ここで 0<=r <1 であるが，もしr6= 0ならa^r≡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に対して2^p をpで割った余りを求めよ.

(3) 自然数nに対してn^p を pで割った余りを推測し,数学的帰納法で証明せよ.

練習問題 8.2 解答32) aの法mに関する指数を eとする．整数a^k の指数は e

(k, e) である．