基礎数学 (7/26) 略解, 補足等
今日はフェルマーの小定理の証明を行いました. この証明の鍵となるのは次の二点
でした.
• 合同式においては無条件に辺々を割ることはできないが, 特殊な状況では割り
算ができた (定理 14.2).
• X を有限集合とするとき, X から X への写像が全射であることと単射であるこ
とは同値であった (定理 14.3).
証明は少々難しく, 聞いただけでは分からなかったかもしれません. 証明を理解した
いと思う人は, 定期試験がすべて終わった後にでも, プリントやノートを参考に考え
直してみるといいと思います.1 何か分からないことがあれば, 夏休み中でも質問を
受け付けますので, アポイントを取っていらしてください.
以下, 29 ページの問題の略解を与えておきます.
問題 14.1 の解答例. a, p を問題文のように取る. プリント 28 ページと同様, r(n) =
(n ÷ p の余り) とおく. 補題 14.4 から,
1 ∈ {1, 2, . . . , p − 1} = {r(a), r(2a), . . . , r((p − 1)a)}
が成り立つ. これは, r(na) = 1 を満たす n ∈ {1, 2, . . . , p − 1} があることを意味する.
この n に対し 1 = r(na) ≡ na (mod p) だから, 結論を得る.
注 1 (発展). 実数の世界では, 0 でないすべての実数 a に対し, ax = 1 を満たす実数
x が (ただ一つ) 存在しました. ax = 1 を満たす実数 x を a−1 と書き, a の逆元 (また
は逆数) と言いました.
素数 p を一つ取り固定し, 同様のことを mod p の世界で考えてみましょう. まず,
p で割り切れる整数は, mod p すると 0 と合同であることに注意します. これを踏ま
えると, 問題 14.1 の主張は, 「 mod p の世界でも, 0 以外のすべての数は逆元を持つ」
と言い換えることができます.
何を言っているのか分かりづらいかもしれませんので, mod p の世界での逆元の例
を一つ与えます. mod 5 の世界で 2 の逆元を求めてみると,
2×3≡1
(mod 5)
ですので, mod 5 の世界では 2 の逆元は 3 となります.
問題 14.2 の解答例. X から Y への写像の個数を数える. 1 に a ∼ d のいずれか, 2 に
a ∼ d のいずれかを対応させることにより X から Y への写像ができるので, 写像の
総数は,
42 = 16(通り)
1
フェルマーの小定理の証明は試験範囲にしませんので, 試験前に取り組む必要はありません.
1
となる.
次に, X から Y への写像のうち, 単射なものの総数を数える. これは a ∼ d から異
なる 2 つを取り, それを一列に並べる場合の個数と等しい. よって, 単射の総数は,
4 P2
= 4 × 3 = 12(通り)
である.
注 2. 単射の個数の数え方について, 少し補足しておきます. a ∼ d から異なる 2 つを
取りそれを一列に並べた結果, d
a と並んだとしましょう. この場合, これに対応す
る写像 f は f (1) = d, f (2) = a と考えます. a ∼ d から異なる二つを取っているので,
対応する写像は単射となります. 数え漏らしがないことも, よく考えれば理解できる
と思います.
問題 14.3 の解答例. f : Z → Z を f (n) = 2n で定める. f (m) = f (n) と仮定すると,
2m = 2n, 即ち m = n である. つまり, 「f (m) = f (n) ならば m = n」が成り立つ.
よって, この対偶命題「m ̸= n ならば f (m) ̸= f (n)」も正しい.
f (n) = 1、即ち 2n = 1 を満たす n ∈ Z はないことから, f は全射でない.
問題 14.4 の解答例. f が全射であることを証明する. k ∈ Z を勝手に取る. このとき,
f (n) = k となる n ∈ Z が存在することを証明すれば良い. 2k は偶数だから,
f (2k) =
2k
= k.
2
よって, n = 2k ととれば f (n) = k が成り立つ.
f の定義から容易に f (1) = f (2) = 1 が分かる. これは f が単射でないことを意味
する.
2
© Copyright 2024 ExpyDoc
