基礎数学 (7/12) 略解, 補足等 今日の授業では, フェルマーの小定理について学習しました. これは, 素数 p と p で 割れない整数 a に対し, ap−1 ≡ 1 (mod p) が成り立つというものでした. 問題 12.1 はフェルマーの小定理を確認する, と言う問題です. いろいろと方法があ りますが, 整数 k に対し, a ≡ a + km (mod m) (1) が成り立つことを用いると, 例 12.6 の計算に帰着できます. なお, 合同式 (1) ですが, (a + km) − a = km は m で割り切れることから, 合同式の意味を考えると従います. 問題 12.1 の解答. 4 ≡ −3 (mod 7) ですので, 46 ≡ (−3)6 = 36 (mod 7) となります. すでに例 12.6 で計算したように, 36 ≡ 1 (mod 7) ですので, 46 ≡ 1 (mod 7) を得ます. 同様に, 5 ≡ −2 (mod 7), 6 ≡ −1 (mod 7) を用いると, 56 ≡ 1 (mod 7), 66 ≡ 1 (mod 7) が確認できます. 問題 12.2 の解答. フェルマーの小定理を活用する問題でした. 29 は素数, 6 は 29 で 割り切れないので, フェルマーの小定理から, 628 ≡ 1 (mod 29) (2) が分かります. これを活用して 6100 ÷ 29 の余りを計算しましょう. 100 ÷ 28 を計算 して 100 = 28 × 3 + 16 に注意します. すると, 指数法則から 6100 = 628×3+16 = 628×3 × 616 = (628 )3 × 616 を得ます. 後は合同式 (2) を活用すると, 6100 ≡ 13 × 616 = 616 (mod 29) を得ます. 62 = 36 ≡ 7 (mod 29) だから, 616 ≡ (62 )8 ≡ 78 1 (mod 29). 72 = 49 ≡ 20 ≡ −9 (mod 29) だから, 78 = (72 )4 ≡ (−9)4 = 94 (mod 29). 92 = 81 ≡ 81 − 29 × 3 = −6 (mod 29) だから, 94 = (92 )2 ≡ (−6)2 = 36 ≡ 7 (mod 29) となります. 以上の計算から, 6100 ≡ 7 (mod 29), つまり, 6100 ÷ 29 の余りは 7 となることが分かりました. 今日の授業では, 合同式では一般には割り算はできないが, 適切な条件がつくと割 り算できる, ということも学びました. 具体的に言うと, gcd(d, m) = 1 かつ da ≡ db (mod m) が成り立つなら a ≡ b (mod m) が成り立つ, ということを学びました. 割 りたい数 d が法 m と互いに素の時, 割り算をしていい, ということになります. この ことについて, 次の問題を考えてみましょう. 問題. 次の合同式を d で割ることはできるか. • 定理 12.2 を使うことができて, d で割った結果が正しいものは○, • 定理 12.2 を使うことはできないが, d で割った結果が正しいものは△, • 定理 12.2 を使うことができず, かつ d で割った結果が間違っているものは× をつけよ. (1) (2) (3) (4) 5 ≡ 25 4 ≡ 28 4 ≡ 28 9 ≡ 72 (mod (mod (mod (mod 4), 4), 4), 7), d = 5, d = 2, d = 4, d = 9. 解. まず, 割りたい数 d と法 ( mod の直後の数字) が互いに素であるかをまずチェック すると, gcd(4, 5) = gcd(7, 9) = 1 ですので (1) と (4) は互いに素となっています. よっ て, (1) と (4) は○, つまり, 定理 12.2 を適用することで合同式 (1), (4) をそれぞれ 5, 9 で割った 1 ≡ 5 (mod 4), 1 ≡ 8 (mod 7) も正しい, ということが分かります. (2) を考えてみましょう. gcd(2, 4) = 2 ですので定理 12.2 を適用できません. 定理 12.2 を使うことはできませんが (2) の両辺を強引に 2 で割ってみると, 2 ≡ 14 (mod 4) 2 となり, これは正しい合同式であることが分かります. よって, (2) は△となります. (3) を考えてみましょう. この場合も gcd(4, 4) = 4 ですので定理 12.2 を適用できま せん. (3) の両辺を強引に 4 で割ってみると 1 ≡ 7 (mod 4) となりますが, もはや正しい合同式ではありません. よって, (3) は×となります. 3
© Copyright 2024 ExpyDoc
