, = = 7 6 = 42, =

志村 真帆呂

プリント置場

1

第

₁

章 数の合同

2016.9.26, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.1

九去法

計算結果が正しいかどうか確認するには検算を行います．その際，なるべ く簡単な方法で検算ができると便利です． 例 1 (九去法) 214× 132 = 28258 それぞれ数字の各桁を足して一桁の数にします．掛け算はそのまま行い，そ の結果も同様に一桁の数にします． (左辺)：(2 + 1 + 4)× (1 + 3 + 2) = 7 × 6 = 42, 4 + 2 = 6 (右辺)：2 + 8 + 2 + 5 + 8 = 25, 2 + 5 = 7 左辺は 6, 右辺は 7 となり，数字が一致していないので計算が間違っているこ とがわかります． (注意) 実は，九去法で最後に得られる一桁の数は，元の数 (式) を 9 で割っ た余りと一致します (正確には，余りが 0 のときは 9 になる)．つまり，九去 法は左辺と右辺を 9 で割った余りを求め，それが違っていたら計算の間違い がわかるという方法です．だから，計算が間違っていたとしても 1/9 の確率 で間違いが検出できないという欠点もあります．

解説 例 1 の方法でなぜ 9 で割った余りが求まるのか考えてみよう． 28258 = 2× 10000 + 8 × 1000 + 2 × 100 + 5 × 10 + 8 = 2× (9999 + 1) + 8 × (999 + 1) + 2 × (99 + 1) + 5 × (9 + 1) + 8 = 9× (2 × 1111 + 8 × 111 + 2 × 11 + 5 × 1) + (2 + 8 + 2 + 5 + 8) よって，28258 を 9 で割った余りは 2 + 8 + 2 + 5 + 8 を 9 で割った余りと等しくなる． (注意) 掛け算をしてから余りを求めるのと，余りを求めてから掛け算をし， その余りを求めるのとで結果は同じになります． 理由を考えてみてください．

1.2

数を数える

代数学の基本は数を数えることです．まずは簡単な例から見てみよう． 例 2 2016 年 9 月 30 日は 2016 年 9 月 26 日の何日後ですか． 解答 1 30− 26 = 4 なので，4 日後になります． では，次の問題はどうでしょう． 例 3 2016 年 9 月 26 日から 2016 年 9 月 30 日までの日数を求めてください． 解答 2 30− 26 = 4 なので 4 日，ではなく 5 日あります． 解説 同じような問題なのに，なぜ 1 日のずれがあるのでしょうか．こういっ たときは，もっと簡単な場合を考えると理解しやすくなります． 28 日は 26 日の 2 日後です．これは，28− 26 = 2 と計算できます．26 日か ら 28 日までの期間は 3 日あります．これは，28− 26 = 2 という計算だけで は求まりません．これには 26 日を数えるかどうかの違いが影響しています． 日付 26 日 27 日 28 日 29 日 30 日 何日後 0 日後 1 日後 2 日後 3 日後 4 日後 日数 1 日目 2 日目 3 日目 4 日目 5 日目 結局，26 日から 30 日までの期間の日数は 30− 26 + 1 = 5 という計算で得られることがわかります．1 を足すのは初日である 26 日を数 えているからです．

1.3. 倍数と約数，整数の商と余り 3 計算法が正しいかどうか迷ったときに役に立つ技術 簡単な状況を考え，その計算法が正しいかを確認する． この説明では，26 日と 28 日という簡単な状況を考えた． 問題 1 次の問いに答えてください． (i). 2016 年 9 月 29 日は 2016 年 9 月 26 日の何日後ですか． (ii). 2016 年 9 月 26 日から 2016 年 9 月 29 日までの日数を求めてください． (iii). 2016 年 10 月 26 日は 2016 年 9 月 26 日の何日後ですか． (iv). 2016 年 9 月 9 日から 2016 年 10 月 26 日までの日数を求めてください．

1.3

倍数と約数，整数の商と余り

定義 1 (倍数，約数) a, b を整数とする． ある整数 n があって b = na となるとき，b を a の倍数，a を b の約数という． また，a が b の約数のとき，a は b を割り切るという． 例 4 91 は 13 の倍数であることを示してみよう． (証明) 整数 13 と 91 に対し，整数 7 があって 91 = 7× 13 となる． よって，倍数の定義より 91 は 13 の倍数である． (注意) a = 13, b = 91, n = 7 と対応させると，倍数の定義を満たしている ことがわかります． 問題 2 (i). 18 は 3 の倍数であることを示してください． (ii). 7 は 35 の約数であることを示してください． (iii). 0 は全ての整数の倍数であることを示してください． (iv). 1 は全ての整数の約数であることを示してください．

補題 1 (割り算の原理) 整数 a と，自然数 b に対し，次の式を満たす整数 q と 0≤ r < b となる自然数 r があります． a = qb + r. この r を a を b で割った余り，q を商といいます． (注意) これは明らかに思えますが，証明の必要なことです． 例 5 17 を 3 で割った余りと商，−17 を 3 で割った余りと商を求めてみよう． 17 = 5× 3 + 2 つまり，17 を 3 で割った余りは 2，商は 5. −17 = (−6) × 3 + 1 よって，_{−17 を 3 で割った余りは 1，商は −6} 余りは負にならないので，_{−17 = (−5) × 3 − 2 ではないことに注意．} (計算法) 負の数を割った余りを求めるには次のようにします． まず，マイナスを取って，割り算をします． 17 = 5× 3 + 2 両辺を (−1) 倍すると，−17 = (−5) × 3 + (−2) 余りが 0 以上の数になるように，余りに割る数 3 を加え，商から 1 を引く． −17 = (−5) × 3 − 3 + (−2) + 3 = (−5 − 1) × 3 + (−2) + 3 −17 = (−6) × 3 + 1 問題 3 次の a, b に対し，上記の条件を満たす q, r をみつけて a = qb + r の 形で表してください． (i). a = 12, b = 5. (ii). a =−23, b = 12.

1.4. 曜日を計算する 5

1.4

曜日を計算する

予定を立てるときなどに，その日が何曜日かを知りたいことがよくありま す．もちろん，カレンダーがあればカレンダーを見れば済む話なのですが，い つでもカレンダーが用意されているとは限りません． そこで，効率的に曜日の計算をする方法を考えてみましょう．

1.5

曜日計算のための予備知識

曜日の計算をする前に，いくつかの必要な知識を列挙しておきましょう． 閏 (うるう) 年 定義 2 グレゴリオ暦では，閏年の年の 2 月は 29 日になります． その年が閏年かどうかは次の規則で定まります． • 西暦年が 4 で割り切れる年は，閏年． • ただし，西暦年が 4 で割り切れても，100 で割り切れる年は閏年で はない． • ただし，西暦年が 100 で割り切れても，400 で割り切れる年は閏年． (注意) 春分から一年後の春分までの日数は，約 365.2422 日です．小数点以 下のずれを補正するために閏年を設けています． 例 6 以下は，閏年かどうかの計算例です． • 1968 年は，1968 = 492 × 4, 1968 = 19 × 100 + 68． つまり，4 で割った余りが 0，100 で割った余りが 68̸= 0． よって，4 で割り切れるけれど，100 で割り切れないので閏年． • 1700 年は，1700 = 425 × 4, 1700 = 17 × 100, 900 = 4 × 400 + 100 な ので閏年ではない． • 2000 年は，2000 = 500 × 4, 2000 = 20 × 100, 2000 = 5 × 400 なので 閏年． 問題 4 次の年が閏年かどうかを判定してください．

各月の日数 定義 3 一年の各月の日数は，次の表のようになります． 月 1 2 3 4 5 6 7 8 9 10 11 12 日数 31 28, 29 31 30 31 30 31 31 30 31 30 31 (注意) 31 日まである月を「大の月」，そうでない月を「小の月」といいま す．「小の月」は「にしむくさむらい (西向く士)」という語呂合わせで覚えら れます．「に (二)) し (四) む (六) く (九) さむらい (十一)」

1.6

曜日計算の方法

西暦 2010 年 9 月 27 日 (月曜日) を基準にして，他の日が何曜日かを計算し てみよう． 例 7 2010 年 10 月 8 日は， 9/27 9/28 9/29 30 10/1 2 3 4 5 6 7 8 9 月 火 水 木 金 土 日 月 火 水 木 金 土 よって，金曜日． 解説 例 7 では，順番に曜日を数えて答えを求めています． この例のように 10 日後くらいならこの方法でもすぐに求まりますが，もっ と先の日が何曜日かを求めようとすると時間がかかります． そこで，もっと簡単に求められる方法がないかと考えてみましょう． 一週間は 7 日なので，7 日経つと同じ曜日になります．よって，基準の日 から何日経ったかを求め，それを 7 で割った余りを計算すれば曜日がわかり ます． 9/27 7 日 z }| { 9/28 9/29 9/30 10/1 2 3 4 5 6 7 8 9. 10 月 8 日は 9 月 27 日から数えて 11 日後. 11 = 1× 7 + 4. より，7 で割った余りは 4．これを下の表と照合すると，10 月 8 日は金曜日 だとわかります． 曜日 月曜 火曜 水曜 木曜 金曜 土曜 日曜 7 で割った余り 0 1 2 3 4 5 6

1.6. 曜日計算の方法 7 また，過去の日付の曜日を求めるにはマイナスの数を利用すると上の表が そのまま使えて便利です． たとえば，9 月 27 日を基準にして 9 月 17 日の曜日を計算するには 17− 27 = −10 = (−2) × 7 + 4. つまり，10 日前を−10 日後と考えます． 余りが 4 なので，表から 9 月 17 日は金曜日だとわかります． 慣れないうちは，一週間くらい前までの日付について以下のような表を書 いて仕組みを理解するとよいでしょう． 日付 9/17 18 19 20 21 22 23 24 25 26 27 曜日 金 土 日 月 火 水 木 金 土 日 月 日数 _{−10 −9 −8 −7 −6 −5 −4 −3 −2 −1} 0 7 で割った余り 4 5 6 0 1 2 3 4 5 6 0 問題 5 次の日付の曜日を求めてください． (i). 西暦 2014 年 4 月 23 日． (ii). 西暦 2014 年 6 月 30 日． (iii). 西暦 2014 年 3 月 14 日． 例 8 西暦 2020 年 4 月 14 日は何曜日でしょうか． これに答えるためには，閏年が何年あるのか (正確には，閏日が何日ある か) が必要になります． 年 2014 2015 2016 2017 2018 2019 2020 日数 365 365 366 365 365 365 366 7 で割った余り 1 1 2 1 1 1 2 西暦 2014 年 4 月 14 日 (月曜日) を基準にすると， 261 + 365 + 366 + 365 + 365 + 365 + 105 = 2192. つまり，2192 日後になります． ( 最初の 261 は，2014 年の残りの日数，最後の 104 は 2020 年に含まれる日 数です ) これを 7 で割って， 2192 = 313× 7 + 1. よって，火曜日になります．

実は，この計算よりも効率がよい方法があります． それは，各年の日数を 7 で割った余りを足してから，さらに 7 で割った余り を求める方法です． 261 = 37× 7 + 2, 105 = 15 × 7 実際に計算してみると， 2 + 1 + 2 + 1 + 1 + 1 + 0 = 8 = 1× 7 + 1. よって，余りが 1 なので火曜日． さらに効率を上げるなら，年数を求め，その中に何年閏日があるかを数え ます．365 = 52× 7 + 1, 366 = 52 × 7 + 2 より，閏年でないなら 1 年で曜日 は 1 日ずれ，閏年なら 1 年で曜日は 2 日ずれます．よって曜日の計算は次の 計算で求めた余りから簡単にわかります． (年数) + (閏日の日数) を 7 で割った余り この問題では，翌年の 4 月 14 日までを一かたまりにして，1 年ずつ数える と年数が 6 年，閏日が 2 日なので， 6 + 2 = 8 = 1× 7 + 1. よって，余りが 1 となり火曜日と簡単に計算できます． 解説 (i). 日数を全部計算してから 7 で割る． (ii). 各年ごとの日数を 7 で割り，その余りを全部足してから 7 で割る． (iii). 年数を求め，さらに閏日の日数を求めて，全部足して 7 で割る． どの方法も正しい答えが求まりますが，下に行くに従って，計算が簡単に なることがわかります． ただし，同時になぜそれで答が求まるのかはわかりにくくなります． (注意) これらの計算が正しいことは，問題を解いてみれば何となくわかる と思います．ただし，数学ではこれを証明することにより，はじめて安心し て使えるようになります． つまり，証明というのは試験に出るから覚えるといったものではなく，計 算法などを安心して使うための心のよりどころだと思ってください． 問題 6 (i). 西暦 2036 年 9 月 26 日は何曜日ですか． (ii). 西暦 3016 年 9 月 26 日は何曜日ですか． (iii). 西暦 1980 年の体育の日は何曜日ですか． (iv). 西暦 1945 年の体育の日は何曜日ですか． (v). 自分の生年月日は何曜日ですか．

1.7. 数の合同 9 2016.9.29, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.6.1

倍数の個数を数える

ある区間に 4 の倍数がいくつあるかを数えるには次のように倍数に番号を つけて数えるとわかりやすくなります．植木算と同じ原理です． 例 9 127 から 321 までの間に 4 の倍数がいくつあるかを考えよう． 127 = 4× 31 + 3 321 = 4× 80 + 1 よって， 128 = 4× 32 .. . 320 = 4× 80 までには， 80− 32 + 1 = 49 個の 4 の倍数がある． (注意) 80− 32 + 1 = 49 と 1 を足す理由は，2 から 6 までにいくつ数があ るかを計算すると，6− 2 + 1 = 5 という計算になることからもわかります． 6− 2 = 4 だと 2 を数えていないことに注意しよう．

1.7

数の合同

余りだけが必要なとき，余りが同じ数を同じものだと思って計算すると便 利なことがあります． 曜日計算では，日数の差を 7 で割った余りが等しければ曜日が同じでした． 定義 4 (合同) 自然数 m, 整数 a, b に対し，整数 q1, q2と自然数 0≤ r1, r2< m があって { a = q1m + r1, b = q2m + r2. と表せる． r1= r2が成り立つとき， a≡ b (mod m).

と書くことにします． これを a と b は m を法として合同といい，この式を合同式といいます． (注意) つまり，m で割った余りが等しい数を等しいとみなす記号です． a≡ b (mod m) は，a − b が m で割り切れると言い換えることもできます． 問題 7 a≡ b (mod m). ならば，a− b が m の倍数であることを示してください． 例 10 { 31 = 2× 13 + 5, −34 = (−3) × 13 + 5. なので， 31≡ −34 (mod 13). となります． このことは，次の等式からもわかります． 31− (−34) = 65 = 5 × 13. 問題 8 次の二つの数が，法 11 で合同かどうかを調べてください．もし合同 だったら，それを 合同式で表してください． (i). 123, 1124. (ii). −23, 54.

1.8

合同式の性質

補題 2 a,a′, b, b′を整数，m 自然数とする． { a≡ a′ (mod m), b≡ b′ (mod m). ならば，次が成り立つ． (i). a + b≡ a′+ b′ (mod m).

1.8. 合同式の性質 11 (ii). ab≡ a′b′ (mod m). 例 11 (補題 2 の応用例) 23895257 と 153121423 の和と積を 13 で割った余 りを求めてみよう． 普通に計算すると，非常に桁数の大きな計算になります． 23895257 + 153121426 = 177016683 = 13616667× 13 + 12 23895257× 153121426 = 3658875826476482 = 281451986652037 × 13 + 1 しかし，先に 13 で割って余りを求めると， 23895257 = 1838096× 13 + 9 153121426 = 11778571× 13 + 3 よって， 23895257 + 153121426≡ 9 + 3 = 12 (mod 13) 23895257× 153121426 ≡ 9 × 3 = 27 ≡ 1 (mod 13) と非常に簡単に計算ができます． 解説 例 11 でわかるように，余りだけの計算 (剰余計算といいます) は桁数 を小さくできます．この性質は，メモリやレジスタの長さに限りがあるコン ピュータと非常に相性が良いものです． 実際，多くの高速なアルゴリズムが剰余計算を利用しています． 補題 2 の証明 { a≡ a′ (mod m), b≡ b′ (mod m). より，次の 等式が得られます． { a′− a = q1m, b′− b = q2m. よって，次の 等式が得られます． { a′ = q1m + a, b′= q2m + b. この式から a′+ b′を計算すると， a′+ b′= (q1m + a) + (q2m + b) = (q1+ q2)m + (a + b).

よって，

a + b≡ a′+ b′ (mod m). また，

a′b′ = (q1m+a)(q2m+b) = q1q2m2+bq1m+aq2m+ab = (q1q2m+bq1+aq2)m+ab. よって， ab≡ a′b′ (mod m) 2. 問題 9 次の数を 7 で割った余りを求めてください． (i). 213 + 567 (ii). 75318× 3488 解説 (補題 2 の証明の解説) a≡ a′ (mod m) を言葉で表すと， 「a と a′は，m の倍数の差を無視すると同じ数」 となります． だから，ある整数 q1を用いて a′ = q1m + a と表せます．a を移項すると a′− a = q1m となり，m の倍数なのがわかります．同様に，b≡ b′ (mod m) から，ある整数 q2があって，b′ = q2m + b と表せます．よって，a′+ b′ = (q1+ q2)m + (a + b) となるので，a + b≡ a′+ b′ (mod m) が示せます． a′ z }| { | {z } q1m | {z } a b′ z }| { | {z } q2m | {z } b ab 面積 = q1q2m2 (m の倍数) 面積 = bq1m (m の倍数) 面積 = aq2m (m の倍数) 表 1.1: ab≡ a′_b′ _{(mod m) の説明図} 全体の面積は a′b′．白い長方形の面積は ab なので ab と a′b′の差は網がけ 部分の面積ですが，網がけの 3 つの長方形は辺の長さが m の倍数なので，面 積も m の倍数となり，網がけ部分の面積も m の倍数． よって，ab≡ a′_b′ _{(mod m) となります．}

1.9. 合同式の応用 (倍数の判定) 13

1.9

合同式の応用

(

倍数の判定

)

例 12 k + 1 個の自然数 0≤ n0, n1,· · · , nk ≤ 9, (nk ̸= 0) を用いて k + 1 桁 の自然数 a が次のように表せます． a = n0+ n1× 10 + n2× 102+· · · + nk10k. このとき，次の合同式が成り立ちます． a≡ n0+ n1+ n2+· · · + nk (mod 9). これは，10− 1 = 9 より次の合同式が成り立つからです． 10≡ 1 (mod 9). 両辺を i 乗すると 10i≡ 1i= 1 (mod 9). よって， ni× 10i ≡ ni× 1 (mod 9). 全部足すと， a≡ n0+ n1+ n2+· · · + nk (mod 9). が得られます． たとえば， 1241 = 9× 137 + 8 ですが，割り算をしなくても， 1241≡ 1 + 2 + 4 + 1 = 8 (mod 9) なので，余りは 8 とわかります． 問題 10 次の数を 9 で割った余りを求めてください． (i). 1234567 (ii). 75318× 3488 問題 11 1, 2, · · · , 9 までの数字を一回ずつ使って 9 桁の数を作ります．たと えば 148259367 などです． このとき，その数が必ず 9 で割り切れることを示してください． 問題 12 自然数 a を，k 個の自然数 0≤ n0, n1,· · · , nk−1≤ 9, (nk−1̸= 0) を 用いて次のように表します． a = n0+ n1× 10 + n2× 102+· · · + nk₋₁10k−1. このとき，次の 合同式が成り立つことを示してください． a≡ n0− n1+ n2+· · · + (−1)k−1nk−1 (mod 11).

2016.10.3, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/ 合同式の世界 (鑑賞用) 定理 1 (フェルマーの小定理) p を素数，a を p の倍数でない整数とする と次の合同式が成り立つ． ap−1≡ 1 (mod p) 定理 2 (ウィルソンの定理) p を素数とすると次の合同式が成り立つ． (p− 1)! ≡ −1 (mod p)

1.10

最大公約数

定義 1 [倍数，約数 (定義 1 再掲)] a, b を整数とする． ある整数 n があって b = na となるとき，b を a の倍数，a を b の約数という． また，a が b の約数のとき，a は b を割り切るという． (注意) この定義は，論理記号を用いて表すとわかりやすくなります． 「a∈ Z が b ∈ Z の約数」⇐⇒ def. ∃n ∈ Z s.t b = an. 定義 5 (公約数) 「d∈ Z が，a, b ∈ Z の公約数」⇐⇒ def. 「d∈ Z が a ∈ Z の 約数」かつ「d∈ Z が b ∈ Z の約数」 定義 6 (最大公約数) 「d∈ Z が，a, b ∈ Z の最大公約数」⇐⇒ def. 「d∈ Z は a, b∈ Z の一番大きい公約数」 a, b∈ Z の最大公約数を，(a, b) (あるいは，gcd(a, b) ) で表します． 例 13 72 と 120 の最大公約数 (72, 120) は，次のように計算できます． 72 = 23· 32, 120 = 23· 3 · 5. よって，2 のベキ乗のうちで最大の公約数は 23_{, 3 のベキ乗のうちで最大の} 公約数は 32_{と 3 = 3}1_{の小さい方なので 3, 5 のベキ乗のうちで最大の公約数}

1.11. 互除法 15 は 1 = 50_{と 5 = 5}1_{の小さい方なので 1.} よって，最大公約数は 23_{· 3 = 24.} このように，素因数分解がわかっていると最大公約数は簡単に求まります． 問題 13 次の値を素因数分解を用いて計算してください． (i). 486 と 63 の最大公約数 (486, 63) (ii). 456 と 1193 の最大公約数 (456, 1193) 解説 最大公約数は，今後様々な場面で重要な役割をします． そのために効率的に最大公約数を求める計算法が必要になります．それが互 除法です．

1.11

互除法

この節では，整数 a, b の最大公約数 (a, b) を効率的に求める方法，互除法 を学びます． 定義 7 (約数の記号) a, b を整数とする． a が b の約数であることを a|b で表し，a は b を割り切るという． 補題 3 a, b, n∈ Z に対し，次の等式が成り立つ． (a, b) = (a− nb, b). (証明) (a, b) = d とすると，∃x, y ∈ Z s.t. a = dx, b = dy.

a− nb = dx − n(dy) = d(x − ny) より，d|(a − nb, b)．

逆に，(a− nb, b) = d′_{とすると，∃x}′_{, y}′_{∈ Z s.t. a − nb = d}′_x′_{, b = d}′_y′_. a = (a− nb) + nb = d′x′+ n(d′y′) = d′(x′+ ny′) より，d′|(a, b)． よって，d = d′となり，等号成立． ₂ 解説 証明は以上の通りですが，慣れないと何をやっているのかわからな いものです． ポイントとなる事実として次を用いています． d, d′を自然数，d|d′_かつ，d′_{|d ならば，d = d}′ この証明では，(a, b) = d, (a− nb, b) = d′_{なので，d と d}′_{が互いの約数と} なることを示せば，(a, b) = (a− nb, b) が言えます．

a,b∈ Z について次のような割り算を考える． a = q1b + r1, 0≤ r1<|b|. a1:= b, b1:= r1. a1= q2b1+ r2, 0≤ r2< b1. a2:= b1, b2:= r2. a2= q3b2+ r3, 0≤ r3< b2. .. . ... |b| > r1> r2>· · · ≥ 0 より，最後には rn+1= 0 となる an₋₁ = qnbn₋₁+ rn, 0≤ rn< bn₋₁. an:= bn−1, bn:= rn. an= qn+1bn. 補題 3 より， (a, b) = (a− q1b, b) = (r1, b) = (r2, b1) =· · · = (rn, bn−1) = rn. よって，rn= (a, b) が得られました． この方法を互除法といいます． 例 14 最大公約数 (391, 221) を求めてみよう． 391 = 1× 221 + 170. (a = 391, b = 221, q1= 1, r1= 170) 221 = 1× 170 + 51. (a1= b = 221, b1= r1= 170, r2= 51) 170 = 3× 51 + 17. (a2= b1= 170, b2= r2= 51, r3= 17) 51 = 3× 17. よって， (391, 221) = 17. (注意) 互除法による最大公約数の計算は，素因数分解による計算に比べて 非常に速いものです． 問題 14 次の最大公約数を計算してください． (i). (48,36) (ii). (1813,777) (iii). (11753,8687) 問題 15 次の分数を約分してください．

(i). 51 119 (ii). 133 209

1.12. Mathematica のコマンド 17 2016.10.6, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.12

Mathematica

のコマンド

Mathematica は非常に高機能で，整数論に関する関数も充実しています． Windows の場合は，「左下の Windows アイコン >Wolfram Mathematica」 を選択して起動します．

1.12.1

Mathematica の基本操作

• 「ファイル > 開く (あるいは 新規作成 > ノートブック (.nb))」を選択 し，ファイルを開く． • コマンドを入力する (大文字と小文字は区別されるので気をつけること) 用意されている命令は大文字から始まります (FactorInteger のように， 途中に大文字が入る命令もあります) • カーソルをコマンドの位置に合わせ，「Shift キー」を押しながら「Enter キー」を押すことでコマンドが実行されます． (* 7 を法として 100 は 2 と合同 *) Mod[100,7] 2 (* 2x mod 7 に x=0, 1, 2, 3, 4, 5, 6 を代入したリストを表示する *) Table[Mod[2*x, 7],{x,0,6}] {0, 2, 4, 6, 1, 3, 5} (* a=, 2, 空白, Table[Mod[2*x, 7],{x,0,6}] の順で表示している *) Print["a=", 2," ", Table[Mod[2*x, 7],{x,0,6}]] a=2 {0, 2, 4, 6, 1, 3, 5} (* 指定した範囲の操作を繰り返す *)

a=0 {0, 0, 0, 0, 0, 0, 0} a=1 {0, 1, 2, 3, 4, 5, 6} a=2 {0, 2, 4, 6, 1, 3, 5} a=3 {0, 3, 6, 2, 5, 1, 4} a=4 {0, 4, 1, 5, 2, 6, 3} a=5 {0, 5, 3, 1, 6, 4, 2} a=6 {0, 6, 5, 4, 3, 2, 1}

1.13

剰余環

Z/N Z

定義 8 (倍数の記号 N Z) Z を整数全体の集合，N を自然数としたとき，N Z で N の倍数全体の集合を表すことにします．集合として定義すると次のよう になります． N Z :={aN | a ∈ Z} = {· · · , −2N, −N, 0, N, 2N, · · · }. 定義 9 (Z/N Z) N を自然数とします． N を法とした余りは，次の N 個になります． 0, 1, 2,· · · , N − 1 よって，整数全体の集合 Z は，余りがどれになるかで分類できます． N Z ={· · · , −kN, · · · , −2N, −N, 0, N, 2N, · · · , kN, · · · } は，N を法として余りが 0 になる整数全体です．この集合を 0 で表し，0 の 属する剰余類と呼びます． また，他の元 kN を用いて kN と書いても 0 を意味します． 同様に，N を法として余りが a になる整数全体

a+N Z ={· · · , a−kN, · · · , a−2N, a−N, a, a+N, a+2N, · · · , a+kN, · · · }

を a で表し，a の属する剰余類と呼びます． また，他の元 a + kN を用いて a + kN と書いても a を意味します． 集合 {0, 1, · · · , N − 1, } を，Z/N Z という記号で表します． (注意) 本当は，Z/N Z の元は x のように書かないといけませんが，面倒な ので単に x と書くことも多いです． Z/N Z ={0, 1, 2, · · · , N − 1}.

1.14. Z/N Z の加法表と乗積表 19 定義 10 (Z/N Z の演算) Z/N Z には，次のようにして加法と乗法が定義さ れます． 加法 x + y := x + y. 乗法 x y := xy. 例 15 N = 8 として，Z/8Z での計算例を見てみよう． (i). 5 + 7 = 5 + 7 = 12 = 4. Z/8Z では，12 と 4 は，12 = 1× 8 + 4 なので同じ数です． (ii). 5× 5 = 5 × 5 = 25 = 1. Z/8Z では，25 と 1 は，25 = 3× 8 + 1 なので同じ数です． 問題 16 Z/13Z で次の計算を行ってください．答えは，0 から 12 を用いて 表すこと． (i). 23 + 4 (ii). 16− 3 (iii). 8× 5 (iv). 34

1.14

Z/N Z

の加法表と乗積表

例 16 Z/5Z の加法表と乗積表を書いてみよう． 表 1.2: 加算表 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

表 1.3: 乗積表 × 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 問題 17 同様に，Z/6Z の加算表と乗積表を書いてください． 問題 18 Z/5Z と Z/6Z の乗積表の違いを探してください． 問題 19 Z/N Z の乗積表が，Z/5Z のパターンになるのはどのようなときで しょうか． 問題 20 Z/N Z の乗積表が，Z/6Z のパターンになるのはどのようなときで しょうか．

1.15. Z/N Z の世界について 21 2016.10.10, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.15

Z/N Z

の世界について

Z/N Z の世界は，N = 0 となっている数の世界です． 解説 N = 8 の場合を考えます．8 = 0 となっている数の世界，つまり Z/8Z の世界では次のような等式が成り立ちます． 26 = 2 なぜなら 8 = 0 なので， 26 = 3× 8 + 2 = 0 × 3 + 2 = 2 となるからです． 大切なことは，Z/N Z の世界でも足し算と掛け算がうまく定義できること です． Z/8Z の世界では，26 = 2,−3 = 5 26 + (−3) = 2 + 5, 26 × (−3) = 2 × 5 は計算しなくても成り立つ． より一般的に書くと Z/N Z の世界で，a = a′, b = b′が成り立つとすると a + b = a′+ b′, ab = a′b′は計算しなくても成り立つ． これだけ見ると整数の世界とあまり変わらないように思えますが，違うとこ ろもあります． 解説 Z/N Z の世界では，不等式はうまく定義できない． 実際，Z/13Z の世界で，普通の整数の世界のように 2 < 7, 3 < 6 としたとする． 整数の世界では 2× 3 < 7 × 6, 6 < 42 が成り立つ． しかし，Z/13Z の世界では， 42 = 13× 3 + 3 = 3 なので 6 < 42 = 3 となるので最初の 3 < 6 と矛盾してしまい，不等号がうまく定まらない．

(注意) Z/N Z の世界では順序が定まらないことを利用して暗号が作られた りします．

1.16

整数解と不定方程式

定義 11 (不定方程式) 変数が 2 つで，方程式が 1 つのように，変数の数が式 の数より多い方程式を不定方程式といいます (さらに，整数解 (定義 12) を求 める場合に限定して不定方程式というのが普通です) 例 17 以下の変数 x,y についての方程式は，それぞれ不定方程式です． • 3x + 4y = 5 • x2_{+ y}2_{= 13} 定義 12 (整数解) 全ての変数の値が整数になっている解を，その方程式の整 数解といいます． 例 18 (整数解の例) (x, y) = (2,−3) は，方程式 5x + 3y = 1 の整数解になっています． (x, y) = ( 1,−4 3 ) は，この方程式の解になっていますが，y の値−4 3 が整 数でないので整数解ではありません． 解説 世の中には，解が整数解でないと意味がない問題があります．上の不 定方程式は，ラグビーの試合で A チームと B チームのトライ数の差が x 回 (追加の 2 点は全て失敗とする)，ペナルティキック数の差が y 回で，A チー ムが 1 点勝ちという状況を表しています． このとき x や y の値が整数でなかったら意味がないことは明白です．

1.17

不定方程式

ax + by = c

の解法

例 14 では，391 と 221 の最大公約数 (391, 221) = 17 を互除法を用いて計 算しました． 実は，この計算から 391x + 221y = 17. を満たす x, y∈ Z が求められます． このことは，互除法の計算を逆にたどっていけば求まります．また，行列 表示をすると見通しがよくなります．

1.17. 不定方程式 ax + by = c の解法 23 例 14 の互除法の計算を行列で書いてみると次のようになります． 391 = 1× 221 + 170 ↔ ( 391 221 ) = ( 1 1 1 0 ) ( 221 170 ) . 221 = 1× 170 + 51 ↔ ( 221 170 ) = ( 1 1 1 0 ) ( 170 51 ) . 170 = 3× 51 + 17 ↔ ( 170 51 ) = ( 3 1 1 0 ) ( 51 17 ) . (注意) 例えば， 170 = 3× 51 + 17 ↔ ( 170 51 ) = ( 3 1 1 0 ) ( 51 17 ) という対応は次のようになっています． { 170 = 3× 51 + 1 × 17 51 = 1× 51 + 0 × 17 これを行列で表すと，次のようになります． ( 170 51 ) = ( 3× 51 + 1 × 17 1× 51 + 0 × 17 ) = ( 3 1 1 0 ) ( 51 17 ) (注意) これらの行列表示に現れるベクトルは，互除法の計算に現れる数を 二つずつ順に並べたものになっています． この例だと， 391, 221, 170, 51, 17 の順に数が現れますが，それに応じてベクトルも ( 391 221 ) , ( 221 170 ) , ( 170 51 ) , ( 51 17 ) の順に現れます． ( 391 221 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 3 1 1 0 ) ( 51 17 ) .

よって， ( 51 17 ) = ( 3 1 1 0 )₋₁( 1 1 1 0 )₋₁( 1 1 1 0 )₋₁( 391 221 ) . ( 51 17 ) = ( 0 1 1 −3 ) ( 0 1 1 −1 ) ( 0 1 1 −1 ) ( 391 221 ) . ( 51 17 ) = ( −1 2 4 −7 ) ( 391 221 ) = ( 391× (−1) + 221 × 2 391× 4 + 221 × (−7) ) . 第 2 成分より， 17 = 391× 4 + 221 × (−7). となります． これにより，391 と 221 の最大公約数 (391, 221) = 17 が 391x + 221y, x, y∈ Z の形で書けました． (注意) ここに現れるベクトルは，次の最大公約数の等式に対応しています． (391, 221) = (221, 170) = (170, 51) = (51, 17). また，行列を用いると，計算の仕組みが見易くなり，しかも計算を間違えに くくなる効果があります． 解説 例 14 の互除法の計算を行列で書いてみると次のようになります． ( 391 221 ) = ( 1 1 1 0 ) ( 221 170 ) . これは，互除法の以下の計算を行列で書いたものです． { 391 = 1× 221 + 1 × 170, 221 = 1× 221 + 0 × 170. 以下同様に， ( 221 170 ) = ( 1 1 1 0 ) ( 170 51 ) . { 221 = 1× 170 + 1 × 51, 170 = 1× 171 + 0 × 51. ( 170 51 ) = ( 3 1 1 0 ) ( 51 17 ) { 170 = 3× 51 + 1 × 17, 51 = 1× 51 + 0 × 17.

1.17. 不定方程式 ax + by = c の解法 25 ax + by = c の解法 ax + by = c の整数解は，次の手順で得られます． (i). 最大公約数 (a, b) = d を互除法で求める． (ii). c が d の倍数でなければ解なし． (iii). c が d の倍数ならば，両辺を d で割った式を考える． つまり，a = da′_{, b = db}′_{, c = dc}′_{とすると，a}′_{x + b}′_{y = c}′を考 える． (iv). 互除法の計算の行列表示を用いて a′x0+ b′y0= 1 となる x0, y0を 求める． (v). (x, y) = (x0c′, y0c′) が一つの解となる． (vi). 全ての解は， (x, y) = (x0c′+ b′t, y0c′− a′t). ただし，t はパラメータとなる． 不定方程式 ax + by = c の解法は，次の方針で行います． 不定方程式 ax + by = c の解法の方針 (i). 互除法で a, b の最大公約数 (a, b) を求める． (ii). 互除法の計算を用いて，ax + by = c の解を一つ見つける． (iii). パラメータを用いて，ax + by = c の解を全て求める． 解を全て求めるところでは，次の補題を用います． 補題 4 a, b を整数．d を a と b の最大公約数とする． 不定方程式 ax + by = 0 の解は，a = da′, b = db′とすると { x = b′t y =−a′t, (t∈ Z はパラメータ) となる．

(証明) ax + by = 0 da′x + db′y = 0 両辺を d で割ると， a′x + b′y = 0 d が a と b の最大公約数だったので，a′と b′は互いに素． a′x =−b′y より左辺は b′の倍数ですが，(a′, b′) = 1 から x が b′の倍数． よって，x = b′t, t∈ Z と表せる． これを a′x =−b′y に代入すると，a′b′t =−b′y より y =−a′t. x = b′t, y =−a′t となり，補題が示せました． 解説 (全ての解の求め方) ax + by = c の一つの解を x = x0, y = y0と する． ax + by = c の全ての解は，x0, y0を用いて次のように求められます． ax + by = c ax0+ by0= c 両辺を引くと， a(x− x0) + b(y− y0) = 0 よって，補題の形になるので x− x0= b′t, y− y0=−a′t これより，x = x0+ b′t, y = y0− a′t が全ての解になる． 解説 実際に整数解を求めるときには，a, b の最大公約数 d が求まった時点 で ax + by = c の両辺を d で割ってから計算するとわかりやすい． もちろん，c が d で割れない場合は「解なし」となります． 例 19 391x + 221y = 34 の整数解を求めてみよう． 互除法により (391, 221) = 17 なので，方程式の両辺を 17 で割る． 23x + 13y = 2

1.17. 不定方程式 ax + by = c の解法 27 例 14 の互除法の計算を行列で書いてみると次のようになります． ( 391 221 ) = ( 1 1 1 0 ) ( 221 170 ) . これの両辺を 17 で割ると， ( 23 13 ) = ( 1 1 1 0 ) ( 13 10 ) . となり，掛けられる行列は変わりません． 以下同様に， ( 13 10 ) = ( 1 1 1 0 ) ( 10 3 ) . ( 10 3 ) = ( 3 1 1 0 ) ( 3 1 ) ( 23 13 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 3 1 1 0 ) ( 3 1 ) ( 3 1 1 0 )₋₁( 1 1 1 0 )₋₁( 1 1 1 0 )₋₁( 23 13 ) = ( 3 1 ) ( 0 1 1 −3 ) ( 0 1 1 −1 ) ( 0 1 1 −1 ) ( 23 13 ) = ( 3 1 ) ( −1 2 4 −7 ) ( 23 13 ) = ( 3 1 ) ( 23× (−1) + 13 × 2 23× 4 + 13 × (−7) ) = ( 3 1 ) よって，23× 4 + 13 × (−7) = 1 を得る． つまり，23 と 13 の最大公約数を 23x + 13y の形で表せた． 求めたいのは 23x + 13y = 2 の解なので，両辺を 2 倍すると 23× 4 × 2 + 13 × (−7) × 2 = 1 × 2 23× 8 + 13 × (−14) = 2 よって，x = 8, y =−14 という一つの解が求まりました．

(注意) 行列 ( a b c d ) は，ad− bc ̸= 0 のとき逆行列を持ち， ( a b c d )₋₁ = 1 ad− bc ( d −b −c a ) となります． よって，行列 ( a 1 1 0 ) の逆行列は次のようになります． ( a 1 1 0 )₋₁ = 1 a× 0 − 1 × 1 ( 0 −1 −1 a ) = ( 0 1 1 −a ) . 例 20 391x + 221y = 35 の整数解を求めてみよう． 互除法により (391, 221) = 17 なので，方程式の両辺を 17 で割ろうとする と左辺は 17 の倍数なのに，右辺が 17 の約数でないので整数解なしとなり ます． 17(23x + 13y) = 35 このように書くと，35 が 17 で割れないと整数解が存在しないことがよくわ かります． (注意) ax + by = (da′)x + (db′)y = d(a′x + b′y) より，ax + by は必ず d の倍数になるので，もし c が d の倍数でなければ，解 は存在しません． 上記の手順で全ての解を求まるのはなぜでしょうか． それには直前に求めた一つの解 (x, y) = (x0, y0) を利用するのが簡明です． これ以外の解を (x, y) = (x1, y1) とします．当然，これらは次の等式を満 たします． { ax1+ by1= c ax0c′+ by0c′ = c. 辺々を引くと， a(x1− x0c′) + b(y1− y0c′) = 0.

1.17. 不定方程式 ax + by = c の解法 29 を得ます． a, b の最大公約数 (a, b) = d を用いて a = da′, b = db′と書けるので， da′(x1− x0c′) + db′(y1− y0c′) = 0. 両辺を d で割って， a′(x1− x0c′) + b′(y1− y0c′) = 0. 移項すると， a′(x1− x0c′) =−b′(y1− y0c′). (a′, b′) = 1 (もし 1 より大きいとすると，d が a,b の最大公約数に反する) よ り，(x1− x0c′) は b′の倍数，(y1− y0c′) は a′の倍数になる． よって， x1− x0c′= b′t とすると， y1− y0c′=−a′t となり，任意の解 (x1, y1) は必ず次のように書けます． (x1, y1) = (x0c′+ b′t, y0c′− a′t). よって，全ての解は， (x, y) = (x0c′+ b′t, y0c′− a′t), (t∈ Z, t : パラメータ). 例 21 次の方程式を解いてみよう． 391x + 221y = 34. 例 14 の計算より，(391, 221) = 17. 17| 34 より解はある． 17 = 391× 4 + 221 × (−7). 34 = 17× 2 より， (x, y) = (8,−14). が一つの解． 391 = 17× 23, 221 = 17 × 13. より，全ての解は，t をパラメータとして (x, y) = (8 + 13t,−14 − 23t).

問題 21 次の不定方程式を解いてください． (i). 3x + 2y = 0 (ii). 18x + 15y = 0 (iii). 7x + 5y = 1. (iv). 7x + 5y = 3 (v). 18x + 15y = 3 (vi). 18x + 15y = 2 (vii). 209x + 57y = 19. (viii). 209x + 57y = 17. (ix). 209x + 57y = 76.

1.18. 前回の補足 31 2016.10.17, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.18

前回の補足

解説 ax + by = 0 の全ての解は，d = (a, b), a = da′, b = db′ とすると { x = b′t y =−a′t (t∈ Z) となるのでした． { x = bt y =−at (t ∈ Z) は，ax + by = 0 の解にはなりますが，d > 1 のときは全ての解になりません． 例 22 391x + 221y = 0 の全ての整数解について調べてみよう． 391 = 17× 23, 221 = 17 × 13, 34 = 17 × 2. 上記の記号を用いると，a = 391, b = 221, d = 17, a′ = 23, b′= 13 です. { x = 221t y =−391t (t ∈ Z) を 391x + 221y = 0 の左辺に代入すると， 391× 221t + 221 × (−391t) = (391 × 221 − 221 × 391)t = 0 よって解になることはわかります． しかし， { x = 13t y =−23t (t ∈ Z) で表せる解 (具体的には t = 1 を代入して得られる解) { x = 13 y =−23 は， { x = 221t y =−391t (t ∈ Z) の形では表せません． つまり，全ての解を表せないことがわかります．

解説 (全ての解の求め方 (再掲)) ax + by = c の一つの解を { x = x0 y = y0 とします． すると， ax + by = c の全ての解は，x0, y0を用いて次のように求められ ます．ここで，d = (a, b), a = da′, b = db′です． { x = x1 y = y1 を任意の解とします． ax1+ by1= c ax0+ by0= c 両辺を引くと， a(x1− x0) + b(y1− y0) = 0 X = x1− x0, Y = y1− y0とすると，方程式は aX + bY = 0 の形になります． これの解は，X = b′t, Y =−a′t 元に戻すと，x1− x0= b′t, y1− y0=−a′t よって任意の解が次のように表されます． { x = x0+ b′t y = y0− a′t (t∈ Z) 例 23 391x + 221y = 34 の整数解を求めてみよう． 391 = 17× 23, 221 = 17 × 13, 34 = 17 × 2. よって，d = 17, a′ = 23, b′ = 13, c′= 2 となります. 前もって求めた 23x + 13y = 1 の一組の解 x0= 4, y0=−7 を用いると． 全ての解は， { x = 8 + 13t y =−14 − 23t (t ∈ Z)

1.19. 不定方程式の演習 33

1.19

不定方程式の演習

問題 22 次の最大公約数を求めてください． (i). (1204, 817). (ii). (2747, 804). 問題 23 次の不定方程式に解があるかどうか判定してください． (i). 1204x + 817y = 83. (ii). 2747x + 804y = 603. 問題 24 次の a, b に対し，d = (a, b), a = da′, b = db′となる整数 a′, b′, d を 求めてください． (i). a = 1204, b = 817. (ii). a = 2747, b = 804. 問題 25 次の不定方程式の解を一つ見つけてください． (i). 28x + 19y = 1. (ii). 2747x + 804y = 67. 問題 26 次の不定方程式の解を一つ見つけてください． (i). 28x + 19y = 3. (ii). 2747x + 804y = 268. 問題 27 次の不定方程式の解を，全て求めてください． (i). 28x + 19y = 0. (ii). 2747x + 804y = 0. 問題 28 次の不定方程式の解を，全て求めてください． (i). 28x + 19y = 3. (ii). 2747x + 804y = 268. 問題 29 次の不定方程式の解を，全て求めてください． (i). 11x + 9y = 4. (ii). 1909x + 1162y = 498. (iii). 13332x + 6767y = 11817.

2016.10.20, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.20

Z/N Z

の世界

有理数の世界では，1 7 という数は整数ではありません．では，Z/15Z の世 界ではどうでしょうか． ここで，分数 1 7 を次の方程式の解と考えます． 7x = 1. Z/15Z の元 13 を選び，x に代入すると 7× 13 = 91 = 15 × 6 + 1 = 1. となり，確かに上の方程式の解になっています．つまり，Z/15Z の世界では 1 7 = 13 となるわけです． まだ，解 13 を見つける方法はわかりませんが，解であるのはわかります． 問題 30 Z/15Z の世界で，次の数はどのように書けるでしょうか． Z/15Z ={0, 1, 2, · · · , 14} の範囲で答えてください． (i). − 18 (ii). 1 2 (iii). 4 5 N を自然数とすると，Z/N Z という数の世界を定義できます． Z/N Z には整数全体 Z と同じように和と積が定義されますが，大きな違い が一つあります．それは，1 を N 個足すと次のように 0 になってしまう性質 です． 1 = 1, 1 + 1 = 2, 1 + 1 + 1 = 3, · · · , N z }| { 1 + 1 + 1 +· · · + 1 = N = 0. 解説 以前，Z/N Z = {0, 1, 2, 3, · · · , N − 1} と書きましたが，本当は， Z/N Z に N という数が含まれていないわけではありません．N もあるけ れど，0 と一致してしまうというわけです．

1.21. Mathematica のコマンド 35 このように，Z/N Z の世界では分数で書かれていて Z/N Z には含まれない ように見えても，実は Z/N Z に含まれることがあります． そこで，分数とは何かを今一度考えてみましょう． 一般に，数 a,b があったとき，分数 b aは次の方程式の解で定義します． ax = b. (注意) もちろん，a = 0, b̸= 0 のときのように，解が無い場合もあります． そのときは，分数 b aは存在しません． また，Z/N Z の世界だと a̸= 0 でも，分数 b aが存在しない場合があります． 例 24 Z/15Z の世界でも，1 7 は次の方程式の解． 7x = 1. そこで，Z/15Z の乗積表の 7 の列を見ると，1 があるのは 13 の列．そこで， 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 7 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8 Z/15Z の元 13 を選び，x に代入すると 7× 13 = 91 = 15 × 6 + 1 = 1. となり，確かに上の方程式の解になっています．つまり，Z/15Z の世界では 1 7 = 13 問題 31 Z/7Z の世界で，次の数はどのように書けるでしょうか． Z/7Z ={0, 1, 2, 3, 4, 5, 6} の範囲で答えてください． (1) 1 4. (2) 4 5.

1.21

Mathematica

のコマンド

Mathematica は非常に高機能で，整数論に関する関数も充実しています． Windows の場合は，「スタート > すべてのプログラム > アプリケーション」 など (マシンによって異なる場合もある) から Mathematica を選択して起動 します．

1.21.1

Mathematica の基本操作

• 「file>open(あるいは new)」を選択し，ファイルを開く． • コマンドを入力する (大文字と小文字は区別されるので気をつけること) 用意されている命令は大文字から始まります． • カーソルをコマンドの位置に合わせ，「Shift キー」を押しながら「Enter キー」を押すことでコマンドが実行されます． (* 7 を法として 100 は 2 と合同 *) Mod[100,7] 2 (* 2x mod 7 に x=0, 1, 2, 3, 4, 5, 6 を代入したリストを表示する *) Table[Mod[2*x, 7],{x,0,6}] {0, 2, 4, 6, 1, 3, 5} (* a=, 2, 空白, Table[Mod[2*x, 7],{x,0,6}] の順で表示している *) Print["a=", 2," ", Table[Mod[2*x, 7],{x,0,6}]] a=2 {0, 2, 4, 6, 1, 3, 5} (* 指定した範囲の操作を繰り返す *)

Do[Print["a=",a ," ",Table[Mod[a*x, 7],{x,0,6}]], {a,0,6}] a=0 {0, 0, 0, 0, 0, 0, 0} a=1 {0, 1, 2, 3, 4, 5, 6} a=2 {0, 2, 4, 6, 1, 3, 5} a=3 {0, 3, 6, 2, 5, 1, 4} a=4 {0, 4, 1, 5, 2, 6, 3} a=5 {0, 5, 3, 1, 6, 4, 2} a=6 {0, 6, 5, 4, 3, 2, 1}

1.22. Z/N Z での逆数の計算 37

1.22

Z/N Z

での逆数の計算

a∈ Z/NZ, (a ̸= 0) の逆数 1 a は次の方程式を解いて得られます． ax = 1. 最も簡単な解法は，Z/N Z の乗積表を作って a の列に 1 を探し，もし見つかっ たら 1 のある行が 1 aに対応します．例題 24 参照． 例 25 Z/N Z の面白いところは， a∈ Z/NZ, (a ̸= 0) でも逆数 1 aが存在す るとは限らないことです． 実際，Z/15Z で，5 の行を見ると 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10 となるので，1 5 は存在しません． では，どのようなときに逆数が存在しないのでしょうか． それには，方程式 ax = 1 をもう一度見直す必要があります． この方程式は，Z/N Z の世界での方程式ですが，整数の世界に戻してやると ax≡ 1 (mod N) という合同式の方程式になります． さらに，これは ax と 1 が N の倍数だけ差があると考えると， ax + N y = 1 という不定方程式の整数解を求めることと同じになります． 結局，前節で学んだ不定方程式の解法によって逆数が計算できるわけです． この考え方が素晴しいのは，逆数の計算が乗積表を作成するのに比べてと ても速くなることと，理論的に扱うのが便利になるという二つの利点がある からです． 例 26 Z/13Z において，1 7 を計算しよう． 7x + 13y = 1

13 = 7× 1 + 6 7 = 6× 1 + 1 6 = 1× 6. ( 13 7 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 6 1 ) . ( 6 1 ) = ( 1 1 1 0 )₋₁( 1 1 1 0 )₋₁( 13 7 ) = ( 1 −1 −1 2 ) ( 13 7 ) . 7× 2 + 13 × (−1) = 1. よって， 1 7 = 2. 問題 32 Z/21Z で，次の数を計算してください． (1) 1 11. (2) 1 3. (3) 4 5. 問題 33 0 以外の元が Z/N Z で必ず逆数を持つための N の条件を求めてく ださい．

1.23. 前回のまとめ 39 2016.10.24, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.22.1

Mathematica の文法

Print (文や計算結果の表示) 文法：Print[文や式] 文や式は”,”(カンマ) で区切る． 改行したいときは，文の中で”Yn” と記述する． Print 終了時には改行が入る． 動作: 文や式を表示する． 例: 入力:Print["HelloYn”, 2+3, " end."] 出力: Hello 5 end. Table (リストの作成)

文法：Table[式,{n, n_min, n_max}]

動作: 式を n_min から n_max まで並べたリストを作成する． 例:

入力: Table[2^n,{n,1,5}] 出力: {2, 4, 8, 16, 32}

Do (繰り返し演算)

文法：Do[命令,{n, n_min, n_max}]

動作: 命令を n_min から n_max まで繰り返し実行する． 例: 入力: Do[Print[n,"番目の素数=",Prime[n]],{n,1,5}] 出力: 1 番目の素数=2 2 番目の素数=3 3 番目の素数=5 4 番目の素数=7 5 番目の素数=11

1.23

前回のまとめ

(注意) x∈ Z/NZ ならば，x は {0, 1, 2, · · · , N − 1} の中の一つで表せる． よって，_{{0, 1, 2, · · · , N − 1} の範囲で解を表すように指示されたときは，こ} の範囲から等しい数を選んで答えること．

a, b∈ Z とする．Z/NZ の世界で，b aは ax = b の解を意味する．これは，Z の世界では ax + N y = b を解くのと同じ． 解説 (a, N ) = d とする． (d = 1 のとき) ax + N y = b には解があり，b a ∈ Z/NZ となる． (d > 1 のとき) (d∤ b のとき) 解なし．b a ̸∈ Z/NZ となる． (d| b のとき) 解 Z/N Z の世界でも複数ある． b aが一つに定まらないので b a̸∈ Z/NZ と考える． 例 27 Z/21Z の世界, (b a = 3 11のとき，(11, 21) = 1) 11x + 21y = 3 には解 x = 6, y =−3 があり， 3 11 = 6 となる． (d > 1 のとき) (b a= 2 3 のとき，(3, 21) = 3 > 1, 3∤ 2) 解なし．2 3 ̸∈ Z/21Z となる． (b a= 3 6 のとき，(6, 21) = 3 > 1, 3| 3) 6x + 21y = 3 の解は x = 4, 11, 18 となり，Z/21Z の世界でも複 数ある． 3 6 が一つに定まらないので 3 6 ̸∈ Z/21Z と考える．

1.24. 今までのまとめ 41 2016.10.27, 代数学序論 (情報数理学科) 担当：志村真帆呂 http://www.ss.u-tokai.ac.jp/~mahoro/2016Autumn/alg_intro/

1.24

今までのまとめ

1.24.1

定義について

例 28 (倍数) 「18 が 9 の倍数であることを示せ」 このような問題にどう答えたらよいかは，作法を知らないとわかりません． ポイントは，「倍数」の定義にあてはめることです． a, b∈ Z に対し，ある n ∈ Z があって b = na となるとき，「b は a の倍数」 という． これが倍数の定義でした．だから，a, b, n を適切に選んで定義の条件を満 たすことを示せば証明が完了します． 9, 18∈ Z に対し，2 ∈ Z があって 18 = 2 × 9 となるので，倍数の定義を満 たし，18 は 9 の倍数となる． 例 29 (割り算の商と余り) 整数 a と，自然数 b に対し，次の式を満たす整数 q と 0≤ r < b となる自然数 r があります．a = qb + r. この r を a を b で割った余り，q を商といいます． a が負の値でも r は正の値です．

1.25

曜日計算

解説 (閏年の定義) • 西暦年が 4 で割り切れる年は，閏年． • ただし，西暦年が 4 で割り切れても，100 で割り切れる年は閏年では ない． • ただし，西暦年が西暦年が 100 で割り切れても，400 で割り切れる年は 閏年． ある期間にある閏年の年数は次のように求まります． (4 の倍数の個数)− (100 の倍数の個数) + (400 の倍数の個数)

解説 (日数と曜日) 曜日は，基準とした日の曜日から何日ずれているかで計 算できます．また，7 日で元の曜日に戻るので，日数そのものではなく，日数 を 7 で割った余りを求めればよいことがわかります． たとえば，1 年は 365 日，365 = 7× 52 + 1 なので，1 年で曜日は 1 日分ず れるといった具合です． 解説 (過去の曜日) 日数を 7 で割った余りが重要なので，過去の日付の場合 はマイナス何日後と数えると未来の曜日計算と同じになります． 解説 曜日計算の手順をまとめると次のようになります． (i). 基準となる日の年から，求めたい日の年までが何年後かを数える． (ii). その間に閏日が何日あるかを数える． (iii). 年は無視して基準となる日から求めたい日までが何日後かを数える． (iv). (何年後)+(閏日の日数)+(年数を無視して何日後)．この値を 7 で割る．

1.26

数の合同

曜日計算のように，余りだけが必要なとき，余りが同じ数を同じものだと 思って計算すると便利なことがあります．これが合同式の計算です． 定義 13 (合同) 自然数 m, 整数 a, b に対し，整数 q1, q2と自然数 0≤ r1, r2< m があって { a = q1m + r1, b = q2m + r2. と表わせる． このとき，r1= r2が成り立つことを a≡ b (mod m). と書くことにします． このことを a と b は，m を法として合同といい，この式を合同式といいます． (注意) つまり，m で割った余りが等しい数を等しいとみなす記号です． a≡ b (mod m) は，a − b が m で割り切れると言い換えることもできます．

1.27. Z/N Z 43

1.26.1

合同式の性質

a,a′, b, b′を整数，m 自然数とする． { a≡ a′ (mod m), b≡ b′ (mod m). ならば，次が成り立つ． (i). a + b≡ a′+ b′ (mod m). (ii). ab≡ a′b′ (mod m). 例 30 (九去法) 合同式の簡単な応用として，ある数を 9 で割った余りを簡単 に求める方法があります． k 個の自然数 0≤ n0, n1,· · · , nk₋₁≤ 9, (nk₋₁̸= 0) を用いて k 桁の自然数 a が次のように表わせます． a = n0+ n1× 10 + n2× 102+· · · + nk−110k−1. このとき，次の 合同式が成り立ちます． a≡ n0+ n1+ n2+· · · + nk−1 (mod 9).

1.27

Z/N Z

N を自然数とし， Z/N Z :={0, 1, 2, · · · , N − 2, N − 1} と定義するのでした． Z/N Z は足し算と掛け算ができる集合になります．

1.28

互除法と不定方程式

Z/N Z の世界での計算を効率的に行うには，次の形の不定方程式の整数解 を求める必要があります． ax + by = c. そのために用いられるのが，互除法です．

1.28.1

互除法

a,b∈ Z について次のような割り算を考える． a = bq1+ r1, 0≤ r1<|b|. a1:= b, b1:= r1. a1= b1q2+ r2, 0≤ r2< b1. a2:= b1, b2:= r2. a2= b2q3+ r3, 0≤ r3< b2. .. . ... |b| > r1> r2>· · · ≥ 0 より，最後には rn+1= 0 となる an−1 = bn−1qn+ rn, 0≤ rn< bn−1. an:= bn₋₁, bn:= rn. an= bnqn+1. 補題 3 より， (a, b) = (a− bq1, b) = (r1, b) = (r2, b1) =· · · = (rn, bn−1) = (rn). よって，rn= (a, b) が得られました． この方法を互除法といいます． 例 31 最大公約数 (391, 221) を求めてみよう． 391 = 221× 1 + 170. 221 = 170× 1 + 51. 170 = 51× 3 + 17. 51 = 17× 3. よって， (391, 221) = 17.

1.28. 互除法と不定方程式 45

1.28.2

不定方程式 ax + by = c の解法

例 14 の互除法の計算を行列で書いてみると次のようになります． ( 391 221 ) = ( 1 1 1 0 ) ( 221 170 ) . これは，互除法の以下の計算を行列で書いたものです． { 391 = 1× 221 + 1 × 170, 221 = 1× 221 + 0 × 170. 以下同様に， ( 221 170 ) = ( 1 1 1 0 ) ( 170 51 ) . { 221 = 1× 170 + 1 × 51, 170 = 1× 171 + 0 × 51. ( 170 51 ) = ( 3 1 1 0 ) ( 51 17 ) { 170 = 3× 51 + 1 × 17, 51 = 1× 51 + 0 × 17. (注意) ここに現われるベクトルは，次の等式に対応しています． (391, 221) = (221, 170) = (170, 51) = (51, 17). また，行列を用いると，計算の仕組みが見易くなり，しかも計算を間違えに くくなる効果があります． 上記の行列の式を次々と代入していくと，次の式が得られます． ( 391 221 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 3 1 1 0 ) ( 51 17 ) . よって， ( 51 17 ) = ( 3 1 1 0 )−1( 1 1 1 0 )−1( 1 1 1 0 )−1( 391 221 ) . ( 51 17 ) = ( 0 1 1 −3 ) ( 0 1 1 −1 ) ( 0 1 1 −1 ) ( 391 221 ) . ( 51 17 ) = ( −1 2 4 −7 ) ( 391 221 ) = ( 391× (−1) + 221 × 2 391× 4 + 221 × (−7) ) .

第 2 成分より， 17 = 391× 4 + 221 × (−7). となります． これにより，391 と 221 の最大公約数 (391, 221) = 17 が 391x+221y, x, y∈ Z の形で書けました． 解説 (ax + by = c の解法) ax + by = c の整数解は，次の手順で得られる のでした． (i). 最大公約数 (a, b) = d を互除法で求める． (ii). c が d の倍数でなければ解なし． (iii). c が d の倍数ならば両辺を d で割る． a′x + b′y = c′という形になる．(a′, b′) = 1 (iv). 互除法の計算の行列表示を用いて a′x0+ b′y0 = 1 となる x0, y0を求 める． (v). c = dc′とすると，(x, y) = (x0c′, y0c′) が一つの解となる． (vi). 全ての解は，a = da′, b = db′とすると， (x, y) = (x0c′+ b′t, y0c′− a′t). ただし，t はパラメータとなる． (注意) ax + by = (da′)x + (db′)y = d(a′x + b′y) より，ax + by は必ず d の倍数になるので，もし c が d の倍数でなければ，解 は存在しない． 例 32 次の方程式を解いてみよう． 391x + 221y = 34. 例 14 の計算より，(391, 221) = 17. 17| 34 より解はある． 両辺を 17 で割って 23x + 13y = 2

1.29. Z/N Z の世界 47 ここで， 23x + 13y = 1 の解は互除法の計算により 23× 4 + 13 × (−7) = 1 なので，(x, y) = (4,−7) が一つの解になる． 23x + 13y = 2 の一つの解は，34 = 17× 2 より，23x + 13y = 1 の解 (x, y) = (4, −7) を 2 倍 して (x, y) = (8,−14). となる． 391 = 17× 23, 221 = 17 × 13. より，全ての解は，t を整数全体を動くパラメータとして次のように表せる． (x, y) = (8 + 13t,−14 − 23t), (t ∈ Z)

1.29

Z/N Z

の世界

有理数の世界では，1 7 という数は整数ではありません．では，Z/15Z の世 界ではどうでしょうか． ここで，分数とは何かを考えると次の方程式の解だと言うことができます． 7x = 1. そこで，Z/15Z の元 13 を選び，x に代入すると 7× 13 = 91 = 15 × 6 + 1 = 1. となり，確かに上の方程式の解になっています．つまり，Z/15Z の世界では 1 7 = 13

となるわけです． Z/15Z の世界で1 7を考える． ⇐⇒ Z/15Z の世界で 7x = 1 の解を求める． ⇐⇒ 7x ≡ 1 (mod 15) の解を求める． ⇐⇒ 7x + 15y = 1 の整数解を求める． このことを一般的に書くと， Z/N Z の世界で1 aを考える． ⇐⇒ Z/NZ の世界で ax = 1 の解を求める． ⇐⇒ ax ≡ 1 (mod N) の解を求める． ⇐⇒ ax + Ny = 1 の整数解を求める． となり，今までの互除法を用いた不定方程式の計算と Z/N Z の世界で逆数を 求める計算がつながります．

1.29.1

Z/N Z での逆数の計算

a∈ Z/NZ, (a ̸= 0) の逆数1 aは次の方程式を解いて得られます． ax = 1. 最も簡単な解法は，Z/N Z の乗積表を作って a の列に 1 を探し，もし見つかっ たら 1 のある行が1 a に対応します．ですが，不定方程式の解法によって逆数 が計算できるわけです． この考え方が素晴しいのは，逆数の計算が乗積表を作成するのに比べてとて も速くなることと，理論的に扱うのが便利になるという二つの利点があるか らです． 例 33 Z/13Z において，1 7 を計算しよう． 7x + 13y = 1 13 = 7× 1 + 6 7 = 6× 1 + 1 6 = 1× 6.

1.30. 小テスト一覧 49 ( 13 7 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 6 1 ) . ( 6 1 ) = ( 1 1 1 0 )−1( 1 1 1 0 )−1( 13 7 ) = ( 1 −1 −1 2 ) ( 13 7 ) . 7× 2 + 13 × (−1) = 1. よって， 1 7 = 2. 解説 Z/N Z の世界では，(a, N ) > 1 という形の分数 b a は考えません．なぜ なら，1 aが存在しないからです．

1.30

小テスト一覧

問題 34 a を整数，b を自然数としたとき，a を b で割ったときの商を q, 余 りを r(ただし，0≤ r < b) とすると a = qb + r と表せます． 以下の a, b について，a を a = qb + r の形で表してください． (i). a = 13, b = 5 (ii). a =−26, b = 7 問題 35 (i). 0≤ x ≤ 10 の範囲に含まれる整数は何個ありますか． (ii). 12≤ x ≤ 22 の範囲に含まれる偶数は何個ありますか． (iii). −50 ≤ x ≤ 50 の範囲に含まれる 5 の倍数は何個ありますか． 問題 36 9 を法として 4 と合同な数を以下の数の中から全て選んで○をつけ てください． −77, −5, 22, 287, 36472