[ 新着記事
| 数学・プログラミング
| 天文・暦
| シリア語・Unicode・詩
| ジョーク
| 漫画・アニメ
| 字幕
| 哲学・ファンタジー
| 全記事
| チラ裏 ]
チラ裏
「チラ裏」は適当な走り書き。誤字、誤記、脱線が多いです！
2022-01-26 げんしこん（その7） 異議ありっ！ 矛盾です！
…というわけで、教科書のやり方は、それなりにエレガントだし有益だが、「もうちょっと分かりやすくできないの？」という感じもする。非構成的なくせに、原始根のレシピを細かく記述してるところが、回りくどい。
【1】 直線的に、いきなり核心を否定して「もしも原始根がなかったら…」と考えてみよう。つまり p を3以上のとある素数として、mod p において、最大の位数は p−1 より小さいと仮定する。位数は p−1 の約数（補助定理1.1）…それが最大でも p−1 未満ってことは…。その世界では、位数は最大でも (p−1)/2、下手すりゃ (p−1)/3 や (p−1)/4 かもしれない…。こう考えた瞬間、反射的に
異議ありっ！ 矛盾です！
と思わないだろうか。例えば、もし仮に何でもかんでも (p−1)/2 乗で ≡ 1 になってしまうとすると、それは x = 1, 2, 3, …, p−1 の p−1 種類の元が
x(p−1)/2 ≡ 1
を満たすということ。上記は (p−1)/2 次方程式なので、解の種類は (p−1)/2 個以下のはずであり、「そんなわけない」という強い直感が働く。
【2】 このスピード感を実際の証明とするには、次のテクニカルなハードルをクリアする必要がある。
テクニカル命題 mod p において、全種類の元の位数を調べたら、一番でかい位数は d だった…とする（位数 d の元の一つを a とする）。この世界において、任意の元 b（0 と合同でないとする）の位数 e は、d の約数。
解説 実際には、既に d = p−1 であること（＝原始根の存在）を証明済みだし、任意の位数は p−1 の約数であることも、補助定理1.1の段階で分かっている。よって、この命題はもっと具体的な形で証明済みなのだが、そのことを一時的に少し忘れて、d の値がまだ分からないふりをしよう。ひょっとしたら d = (p−1)/2 などかもしれない…。それでも上の命題が成り立つとすれば: 最大位数が d なら任意の位数は d の約数（例えば d/2 や d/3）ということになり、上述の「異議ありっ」の論証が成立する。変数名 d は (ichiban) dekai isū から。
《例》 mod 19 の最大位数が、実際の値 18 ではなく、その半分の 9 だったとしよう。この仮想世界において、上のテクニカル命題によれば、任意の元（≢ 0）の位数が 1, 3, 9 のどれかになる。ある元 b の位数が 9 なら、もちろん b9 ≡ 1。別の元 c の位数が 3 なら、c3 ≡ 1 だが、その両辺を3乗することで、やはり c9 ≡ 1。位数 1 の場合も同様。結局、0 と不合同な元を 9 乗すれば常に ≡ 1 になるが、それは「mod 19 において、9次方程式が18種類の解を持つ」という、とんでもない主張であり、解の個数に関する根本法則に反している。別の角度から言えば「x9 ≡ 1 の解はちょうど 9 種類」という補助定理2とも、矛盾する。
このテクニカル命題は「これを指摘することで、大々的に矛盾が発生する」という「秘孔」に当たる。「原始根など存在しない！」という敵の主張は、この一点だけで粉々になり、背理法によって、原始根の存在が確定する。おまえはもう、矛盾している…。
【3】 この秘孔を突くには（つまりテクニカル命題を証明するには）、「b の位数 e が d の約数ではない」ということの不可能性、すなわち「d が e で割り切れない」ということの不可能性を示せばいい。
そもそも「d が e で割り切れない」とは、どういう場合か？
例えば d = qrs と、3個の素数の積に分解されるとしよう。e = qr などなら、d/e は（約分が成立して）割り切れる。一方、分母 e の因子として q, r, s のどれとも違う素数 w が含まれていたら、約分は成立せず（分母の w を分子でキャンセルできず）、この分数は割り切れない。
ここで d = qrs などの数は、位数（要するに指数）の計算に関するものであり、普通の整数の世界の話。mod p の世界における 1/w のような計算とは、関係ない。変数名 w は wake no wakaran sosū から。
仮に e = qw としてみる。その想定が実は無理であることは、次のように示される。
仮定により be = bqw = (bq)w ≡ 1
だから (bq) の位数は w
d = qrs と w は互いに素なので、補助定理3により a(bq) の位数は dw
位数 dw の元の存在は「a の位数 d が一番でかい」という仮定に反し、不合理。つまり e = qw と考えると、矛盾が生じる。
【4】 より一般的に、d の因数分解も素数 w を含む…という可能性も考慮しよう、d = qrsw2 のように。その場合でも、e がさらに多くの個数の w を含んでいれば（例: e = qw3）、d/e は割り切れない。すなわち、ある素数 w について、d の素因数分解に含まれる w のべきを V = wj として、e の素因数分解に含まれる w のべきを W = wk としたとき、j < k であれば（つまり V < W であれば）、d/e は割り切れない。…素数 w のべき以外にも、分母には割り切れない原因が二重・三重にあるかもしれないが、いずれにしても少なくとも一つの素数べきについて「分母の方が指数が大きい」ということが、「割り切れない」という状況の必要十分条件。【3】では、その特別な場合として、j = 0, k = 1（つまり V = 1, W = w）のケースを考察したのだった。
対応する全部の素数べきについて、分子側の指数が分母側の指数以上なら、その分数は割り切れる。
例えば (p3q1r5) / (p3q0r2) = q1r3 のように。
今、仮に a の位数 d = qrsV が「一番でかい位数」だとしよう（実際には qrs の部分は、w を含んでいなければ何でもいい）。そして b の位数 e = qW が「d の約数ではない位数」の例だとしよう（実際には q の部分は、w を含んでいなければ何でもいい）。この場合、次のようにして、容易に位数 qrsW の元を構成でき、それは「d = qrsV が一番でかい位数」という前提と矛盾する。
仮定により ad = aqrsV = (aV)qrs ≡ 1
だから (aV) の位数は qrs
仮定により be = bqW = (bq)W ≡ 1
だから (bq) の位数は W
qrs と W は互いに素なので、(aV)(bq) の位数は qrsW
要するに「位数 e（それは d の約数ではない）の元が存在し得る」という仮定は無理であり、前記のテクニカル命題を受け入れざるを得ない。すなわち、原始根の存在が再び示された。□
【5】 次のタイプの議論についての補足。
「仮定により be = bqw = (bq)w ≡ 1
だから (bq) の位数は w」
この場合、(bq) を w 乗すれば ≡ 1 なのは明白として、もっと小さい指数で ≡ 1 になる可能性はないか？
例えば (bq)v ≡ 1, v < w ‥‥「？！」
という事態になれば、(bq) の位数は w より小さい。その可能性を考慮しなくていいのか？
実は「？！」の場合には、bqv ≡ 1 となるから、b の位数も qv 以下となり、e = qw より小さい。「b の位数は e」が議論の前提であり、その前提に反する「？！」の想定は、論理的に許されない。
「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです…
![2016 = (28+28+28)×[28−(28+28+28+28)/28]](/image/2016/2016-28.png)
Map の長所、splice より速い要素挿入法も紹介。 〔最終更新: 2016年4月10日〕bdi 要素と Unicode 6.3 の新しい双方向アルゴリズム (2012-12-04)dir 属性は落とし穴が多い。HTML5 の <bdi> は役立つ。近い将来、「ユーザー入力欄などの語句は、このタグで隔離」が常識になるかも。 〔最終更新: 2014年4月27日〕
fad() は濁りやすい。各種の代替手段を紹介。forum.doom9.org / videolan.org
Tor Project | Anonymity Online / 
Tor Browser
The SeaMonkey® Project
LibreWolf Browser