基礎数学 (7/19) 略解, 補足等問題 13.1 は, 前回紹介したフェルマーの

基礎数学 (7/19) 略解, 補足等
問題 13.1 は, 前回紹介したフェルマーの小定理の復習に関する問題でした. フェル
マーの小定理とは, 素数 p と, p で割れない a ∈ Z に対し,
ap−1 ≡ 1
(mod p)
が成り立つというものでした. これを用いると, 問題 13.1 は次のように解答できます.
問題 13.1 の解答例. 37 は素数, 10 は 37 で割れないので, フェルマーの小定理から,
1036 ≡ 1
(mod 37).
(1)
100 を 36 で割って, 100 = 36 × 2 + 28 より,
10100 = 1036×2+28 = 1036×2 × 1028 = (1036 )2 × 1028 .
合同式 (1) を適用して,
10100 ≡ 1028
(mod 37).
(2)
102 , 103 を 37 で割った余りを計算していくと,
102 = 100 ≡ 26
3
10
(mod 37),
= 10 × 10 ≡ 26 × 10 = 260 ≡ 1 (mod 37).
2
よって, 28 = 3 × 9 + 1 に注意し, 103 ≡ 1 (mod 37) を合同式 (2) に用いると,
1028 ≡ 10 (mod 37)
よって, 10100 ≡ 10 (mod 37), 即ち, 求める余りは 10 である.
注 1. 上の解答例は, 運良く (?)103 ≡ 1 (mod 37) を見つけることができた場合のも
のです. 実は, その場合, 10100 = 103×33+1 と書くことにより, フェルマーの小定理を
用いる必要もありません.
ただし, a□ ≡ 1 (mod p) を満たす □ として, 小さい数が取れる保証はないことに
注意しておきます. 例えば, 2□ ≡ 1 (mod 37) を満たす最小の正整数 □ は 36 です.
今日の授業では, 写像の考え方について学習しました. X, Y を集合とするとき, X
の各元に対し Y の元を唯一つに対応させる規則 f のことを, X から Y への写像と言
いました. X から Y への写像であることを強調するとき, f : X → Y などと書きま
した. また, x ∈ X が f により対応する Y の元を f (x) などと書きました.
f : X → Y に対し, f (X) = {f (x)|x ∈ X} を f の値域と言いました. 問題 13.2 は,
この「値域」の意味を確認する問題です.
1
問題 13.2 の解答例.
g(X) = {g(1), g(2), g(3), g(4)} = {a, b, c, d},
h(X) = {h(1), h(2), h(3), h(4)} = {d, d, a, a} = {a, d}.
有限個の元から成る集合 (有限集合と言いました)X に対し, X の元の総数を |X| で
表しました. 問題 13.3 はこれを確認する問題です.
問題 13.3 の解答例. (1) {a, b, c, d, e} は 5 つの元から成る集合なので, 答えは 5.
(2) {n ∈ Z| − 3 ≤ n < 2} = {−3, −2, −1, 0, 1} で, これは 5 つの元から成る集合なの
で, 答えは 5.
問題 13.4 は次回の準備となる問題です. f (n) の n に 0 から 6 までを代入して計算
してみましょう.
問題 13.4 の解答例. X の各元を f に代入すると,
f (0) = (0 ÷ 7 の余り) = 0,
f (1) = 3,
f (2) = 6,
f (3) = 2,
f (4) = 5,
f (5) = 1,
f (6) = 4
となる. n に異なる値を代入すると, X の異なる元に対応しているので単射である.
また, f (n) の n に 0 から 6 を代入した結果, 0 から 6 がすべて出ているので全射であ
る. 故に, f は全単射である.
問題 13.5 は, 写像の個数の数え上げの問題です. 高校数学の「場合の数」の初歩を
理解していれば, 容易に解答可能です.
問題 13.5 の解答例. X から Y への写像の総数を計算する. X から Y の写像は, X の
各元に対し Y のどの元を対応させるかで決まる. |Y | = 2 であるので, X の各元に二
通りの対応がある. 以上より, 求める写像の個数は, 24 = 16 個.
次に, X から Y への全射な写像の総数を計算する. X から Y への写像で, 全射で
ないものは X の各元にすべて a を対応させるものと, すべて b を対応させるものの二
つである. 故に, X から Y への写像で全射なものの総数は, 16 − 2 = 14 個.
注 2. X と Y を有限集合とし, |X| = m, |Y | = n とします. このとき, X から Y への
写像の総数は, nm 個となります. これは, X の各元に対し, 対応させる Y の元の可能
性は n 通りあることから分かります.
また, m ≤ n とするとき, X から Y への単射な写像の総数は,
n Pm
= n(n − 1)(n − 2) · · · (n − m + 1)
通りになります. X = {1, 2, . . . , m}, Y = {1, 2, . . . , n} として考えてみてください.
2
一方, m ≥ n とするとき, X から Y への全射な写像を数えるのは簡単ではありま
せん. 問題 13.5 は, |Y | = 2 だったので難しくありませんでした. 興味のある人は, ま
ず n が小さい場合に検討してみてください. さらに興味のある人は, (第 2 種) スター
リング数なる用語を調べてみてください.
3

Download Report