2010-10-31

シルヴァーマン 「はじめての数論」第3版 第18章練習問題

18.1
FERMAT (フェルマー)

18.2
(a)共通因数を持たなければ、アルゴリズム17.1が適用できるから。

(b)
暗号化はmを法としているから、mより長いメッセージと、
mを法として合同なメッセージとは区別できない。
だからメッセージはmより短くしなければならない。
アルゴリズム17.1の過程が満たされていれば、
mより短いメッセージは唯一の解に必ず復号できる。


gcd(a,m)=pでも、練習問題17.4により復号できる

(c)
φ(m)=6なので、kの選択肢としてはk=5しかない。
暗号化は359 (mod 18)だが、
gcd(9,18) ≠118は相異なる素数の積でもない(練習問題17.4)のでうまくいかない。
実際、x59 (mod 18)を強引にアルゴリズム17.1で解くと、
x9≠3 (mod 18)となり復号できていない。

18.3, 18.6
ウィキペとか


18.4
(a)
6番目と10番目の暗号は誤植。正しくは
6番目:26945939925、10番目:2163791130(原著者公式参照)。
誤植を直して復号すると
Mathematics is the queen of science and number theory is the queen of mathematics. K. F. Gauss.
(数学は科学の女王であり、数論は数学の女王である。K. F. ガウス)

シルヴァーマン 「はじめての数論」第3版 第17章練習問題2

17.4

(a)
p,qを素数とし、m=pqgcd(m,b)=pとする。
もしq|bならb=pq≡0 (mod m)だから、gcd(b,q)=1である。
gcd(p,q)=1だからku=1+φ(m)=1+φ(p) φ(q)
xbu(mod m)とすると、mod qではq|mより
xk bku(mod q) = b1+φ(p) φ(q)= b (bφ(q) ) φ(p)b(mod q)           (1)
またmod pではp|mgcd(m,b)=pより
xk bku≡0(mod p)                                                           (2)
(1),(2)xkについての連立合同式とみるとgcd(p,q)=1だから、
中国の剰余定理により解はmod pqで唯一に定まる。
具体的に解くと、(2)より
xk =pi (0<i<q)
(1)に代入して
pib(mod q)
つまり0j<pとして
pi=b+qj
gcd(p,q)=1より、py=1+qzの解yが存在するから、このyを用いてi=byと書ける。
よってmod pqで(1)(2)の解は
xkpby=b(1+qz) ≡(gcd(m,b)=pよりp|bだからbq≡0(mod pq))
したがって、xbu(mod m)xkb(mod m)の唯一の解である。

(b)
(a)p=q=3と考えると、φ(9)=6φ(3) φ(3)=4だから(a)の方法はうまくいかない。


17.5
(a) φ(1279)=1278なので、gcd(2, φ(1279))=2≠1となりアルゴリズム17.1が使えない。

(b)
p=2のときはアルゴリズム17.1gcd(2, φ(p))= gcd(2,1)=1だが、
b≠0ならx1 (mod 2)しかないので自明となる。
pp≥3素数ならpは奇数だから、gcd(2, φ(p))= gcd(2, p-1)=2≠1なので、
アルゴリズム17.1は使えない。

(c)
ku=1+φ(m)vに解が存在しないからである。

2010-10-27

証明をどう教えるか

たいていの中学生は、中2でユークリッド幾何学を教わり始め、
証明問題が嫌いになるか、嫌いとは言わんまでも苦手意識を持つ。
まあそりゃ、「証明を書く」段階では、
それまで整数論の式の計算をつかった説明問題とかやったことはあっても、
ずいぶんと慣れないことをたくさんやらされるわけで、
面食らうのはしょうがないだろう。

が、真に大事なのは証明を書く前の段階、
どうして~と~が等しいとわかるのか、
という段階の論理の組み立ての方なわけで、
この点については、それまでやってきたことと変わらない。
もし変わるのだとしたら、それはそれまでの教え方が
「なぜそうなるか」という観点を強調してこなかっただけだ。

証明を教えるときに、証明をしっかり書く、証明の形式を整える、
という事に力点が行き過ぎると、
生徒は面白くもなんともないだろうし、証明が嫌いになるだろう。
それは論理的思考を学べないという不幸だ。
そりゃ理屈ばっかり言ってる奴は嫌われるが、
ここというときに大切なことを論理的に語れない奴は軽く見られる。
テストや高校入試で必ず出るのだから、
証明の答案の形式を練習しなければならないのは当然だが、
より重要視しなければならないのは、証明を書く前の段階だ。


中学のそれまでの数学の勉強では、「問題」があり、「途中計算」があり、「答え」があった。
いつも自分は、「途中計算」の部分、
つまり「なぜその答えになるのか」の部分が最も大事と教えている。
論理の組み立てを行うことが今までの「途中計算」に当たる部分、
証明の文章は、今までの「答え」の部分がちょっと大きくなっただけ。
こういう説明をすると、生徒は証明を書く段階の前が大事なんだなと、
なんとなく意識してくれるようになる。
「今までと全く違うことをやらされている」感をできるだけ減らす効果もあるようだ。、


中には、問題を読んだら考えもしないうちに、とりあえず形式的に
証明を書き始める生徒もいる。
話の順序をしっかりさせてから書き始めろよと口を酸っぱくして言っている。
なにしろその順序が最も大事なわけで。

そこで論理とは何か、を中学生に最初に教えようと思ったら、
「話の順番のこと」だと教え込んでいる。
1回言っただけではではわからないから、
中2の後半のほとんど、数カ月かけて。
そのためには、証明の形式面については、ある程度おおらかにしないとなぁ。
バランスが難しい。

このあたり、教科書には証明というのは「筋道の立った説明」だと書いてある。
まー正しいし、教科書的にはそんな感じに書かざるを得ないだろうが、
そう言って中学生がわかるのかと言ったらまずわからない。
そりゃそうだ、今までそんなことほとんど考えたことないのが普通だし。

「筋道の立った」=「話の順序がしっかりしたストーリーになっている」
だと、ほんの少しピンと来る子も出る。
クイズ本やゲームとかで、話の順序をバラバラにした物語を、
正しい順序に直す問題があるが、あれをやるんだよ、と言うと、
もうちょっと興味をもつ子も出てくる。うへえという子もいるがw
話の要素を順番に矢印でつないで、最後(結論)までつなげるゲーム、
という図を書いてやると、だいぶイメージしやすいようだ。

ちょっと複雑な証明になると、一部分のつながりの要素
(対頂角とか平行線の錯角とか)はわかっても、
それら全体がどうつながるのかは、すぐにはわからない。
そんな時に、もうちょっとで解けるという希望を持たせながら、
しかも自分でつながりを考え出せるように、どう導くかが、
証明問題に苦手意識を持たせないためのポイントになるのだろう。

そんなことがいつも出来れば理想的だが、
中学レベルの証明問題は自分にはすぐ答えがわかってしまうだけに、
ついつい子供の論理構築可能速度を上回った説明をしてしまうこともままある。
やはり子供の気持ちになってあげることが肝心。
・・・ていうかそういうお題目よりもっと具体的には例えば、
0
シルヴァーマン
はじめての数論 第3版
自分自身が他の進んだ数学の勉強をして、
証明問題で悩む日常を送る、というのが良い気がしている。

最近代数学の勉強を始め、特にいままであまり馴染みのなかった数論を、
シルヴァーマン「はじめての数論」の、
豊富で自分的には適切なレベルの練習問題を、
時間のある時に解いていっている。
中学の時初めて証明問題に突き当たった時はすぐ通り過ぎてしまった、
まったく慣れない分野の証明のストーリーをどう組み上げればいいか、
一部の要素は見えるのだが全体がよくわからない、という気持ちを、
再体験している。

LINK
ポリア
数学の問題の
発見的解き方1
教え子たちもこんな気持でうんうん唸っているんだなぁと思うと、
数論や代数学の勉強以上に、教育の勉強にもなっている。


・・・と思っていたら、最近ポリア「数学の問題の発見的解き方」(1962)という、
数学教師の養成を行っていた人の本が再版されていた。
数学教育に関する古典的名著のようで、
同じく古典的名著とされる同じ著者の「いかにして問題を解くか」は
自分もタイトルは知っている程度に有名。
数学を学習している高校生あたり向けの本なのかなと思ってたが、
数学教育法についての本だったのか。
LINK
ポリア
いかにして
問題を解くか
ともかく「数学の問題の発見的解き方」の前書きにある
「教師が通ってきた教育課程では・・・
彼の能力・推論する能力・問題を解く能力・創造的な思考に対しては、
全くと言って良いくらい注意が払われなかった。
・・・この欠陥を補うには、教員の養成課程の中に、
適当なレベルの上で創造的仕事を行う機会を設けるべきだ。」
には、ああやっぱりそうなんだなと感銘を受けた。
解法を創造することを教えるには、
自らが常に解法を創造し続けていなければならない、ということだろう。
うん、その通り。
この本の中にも解き甲斐のある問題が色々あるなあ、面白そう。

完全数定理

LINK
ユークリッド
原論

ユークリッド「原論」の第1クライマックスは定理4-10,11だが、
第2クライマックスは定理9-36の、メルセンヌ素数絡みの完全数定理。
その前の定理9-35で等比級数が構成され、
5~9巻の比と整数論の知識が縦横に使われて完全数が構成される。

見事な証明だと思う一方で、メルセンヌ素数はともかく
完全数ってそれほど重要か?という思いもよぎる。
ましてや友愛数や社交数になってくると、
「だから何」という感覚が拭えない。この辺は、
数論の論理→人間理性の到達点→その理性理解を入れた哲学思想
という文脈の話の中での重要性、という話なのだろうなあ。
「220と284のような友愛」と言われてもなんか回りくどくて・・・。

いやまあ、例えばフェルマーの大定理(ワイルズの定理)なんて、
あまり重要とは思えない孤立した問題と思われていたそうだが、
それがいきなり、谷山・志村予想→ラングランズ・プログラム
(内容は理解していないw)という
なにやら壮大っぽい中心部に躍り出た、なんて話もあるんだから、
単に自分が無知なだけなのだろうけど。

奇数完全数はABC予想というのと関係するらしいが、
そのABC予想と他の数学のつながりはよくわからない・・・。

シルヴァーマン「はじめての数論」第3版 練習問題の解答例

これは言い訳だが、慣れない分野なので、用語や論理が適切かとか、
解き方がうまいかとかは自信がない。


あとこれも言い訳だが、過度に厳密にならないように書いているつもり、
っていうか面倒だし。どの程度厳密にやるかはその日の気分で違うので、
証明の粒度はまちまちであるw

シルヴァーマン 「はじめての数論」第3版 第17章練習問題1

17.1
1147=31·37, 329=7·47なのでgcd(329,1147)=1
またφ(1147)=30·36=1080なので、gcd(113, φ(1147))=1だから、
アルゴリズム17.1によって解を求めることができ、
x4521229≡763 (mod 1147)

17.2
(a)
113, 347, 463は素数だから、アルゴリズム17.1によって解を求めることができ、
x347323≡37 (mod 463)

(b)
588=22·3·72より、φ(588)=168=23·3·7gcd(139,588)=gcd(275, φ(588))=1なので、
アルゴリズム17.1によって解を求めることができ、
x≡13911≡559 (mod 588)


17.3
(a)
xkb (mod m)の解として、アルゴリズム17.1でのuから得られるu =u0を用いた解
x0bu0(mod m)と異なる解xx1 (mod m)があったとする。
bux1kux11+φ(m) v (mod m)と書けるので、uku-φ(m) v=1の解の一つu =uで、
x0x1は異なるから、lを用いてu’= u0+φ(m)lである。ところが、
x1bu= bu0+φ(m)l= bu0x0 (mod m)となるから、xkb (mod m)の解はmod mでただ一つである。

(b)

gcd(k,φ(m))=q, k= kq, φ(m) = fq, ku‘=1+ fvとし、xkb (mod m)の解xx0がもしあれば、
k‘, u‘, f‘,qを使って別の解が作れることを示すのだと思うが、うまくいかないなあ。




(c)

lとする。

一般論として分かること
 m=pが素数なので、b=0ならすべてのk≥2に対しx≡0 (mod p)のみが解。
 m=pが素数なので、Fermatの小定理からk=(p-1) l=φ(p)l (l>1)のとき
xkb (mod p)の解はb=1ならすべてのx≡1,2,.. p-1 (mod p)b>1なら解はない。
 Fermatの小定理によって、kpに対してはmod φ(p)で考えれば十分なので、
2k p-1としてよい。

m=2のときφ(2)=1なので、すべてのk≥2に対しgcd(k,φ(2))=1
xk≡0 (mod 2)の解はすべてのk≥2に対しx≡0
xk≡1 (mod 2)の解はすべてのk≥2に対しx≡1


m=3のときφ(3)=2k=2l+1に対しgcd(k,φ(3))=1なので解はただ一つ。
また、k=2l対しgcd(k,φ(3))=lなので解は一つではない。
xk≡0 (mod 3)の解はすべてのk≥2に対しx≡0
xk≡1 (mod 3)の解は
k=2l対しx≡1, 2
k=2l+1に対しx≡1
xk≡2 (mod 3)の解は
k=2l対し解なし。
k=2l+1に対しx≡2

m=5のときφ(5)=4k=4l+1, 4l+3に対してはgcd(k,φ(5))=1なので解はただ一つ。
また、k=4l , 4l+2対しgcd(k,φ(5))=4or2なので解は一つではない。
xk≡0 (mod 5)の解はすべてのk≥2に対しx≡0
xk≡1 (mod 5)の解は
k=4lに対しx≡1,2,3,4
k=4l+1対しx≡1
k=4l+2対しx≡1,4
k=4l+3対しx≡1
xk≡2(mod 5)の解は
k=4lに対し解なし。
k=4l+1対しx≡2
k=4l+2対し解なし。
k=4l+3対しx≡3
xk≡3(mod 5)の解は
k=4lに対し解なし。
k=4l+1対しx≡3
k=4l+2対し解なし。
k=4l+3対しx≡2
xk≡4(mod 5)の解は
k=4lに対し解なし。
k=4l+1対しx≡4
k=4l+2対しx≡2,3
k=4l+3対しx≡4

m=7のときφ(7)=6k=6l+1, 6l+5に対してはgcd(k,φ(7))=1なので解はただ一つ。
また、k=6l , 6l+2, 6l+3, 6l+4対しgcd(k,φ(7))>1なので解は一つではない。
xk≡0 (mod 7)の解はすべてのk≥2に対しx≡0
xk≡1 (mod 7)の解は
k=6lに対しx≡1,2,3,4,5,6
k=6l+1対しx≡1
k=6l+2対しx≡1,6
k=6l+3対しx≡1,2,4
k=6l+4対しx≡1,6
k=6l+5対しx≡1
xk≡2(mod 7)の解は
k=6lに対し解なし。
k=6l+1対しx≡2
k=6l+2対しx≡3,4
k=6l+3対し解なし。
k=6l+4対しx≡2,5
k=6l+5対しx≡4
xk≡3(mod 7)の解は
k=6lに対し解なし。
k=6l+1対しx≡3
k=6l+2対し解なし。
k=6l+3対し解なし。
k=6l+4対し解なし。
k=6l+5対しx≡5
xk≡4(mod 7)の解は
k=6lに対し解なし。
k=6l+1対しx≡4
k=6l+2対しx≡2,5
k=6l+3対し解なし。
k=6l+4対しx≡3,4
k=6l+5対しx≡2
xk≡5(mod 7)の解は
k=6lに対し解なし。
k=6l+1対しx≡5
k=6l+2対し解なし。
k=6l+3対し解なし。
k=6l+4対し解なし。
k=6l+5対しx≡3
xk≡6(mod 7)の解は
k=6lに対し解なし。
k=6l+1対しx≡6
k=6l+2対し解なし。
k=6l+3対しx≡3,5,6
k=6l+4対しx≡2解なし。
k=6l+5対しx≡6

bk乗根はmを法として0gcd(k, φ(m))?