群・環・体入門 ：Section 1 整数
from 群・環・体入門
両辺に加える操作していいんやろか....
まあ、証明はすぐできるだろうけど
bからcを直接変形する
0aの0とは、ここでは加法単位元以上の意味を持たない。
そのため、加法と単位元の関連を示す規則（x + (-x) = 0, a + 0 = 0）が重要になる
分配法則は加法と乗法の単位元を示した唯一の法則である。
x + (-x) = 0の方から解析してみた
....？？？
解けぬぇ.......悔しい.......
なぜ解けなかったのだろうか？
0a = 0の証明に、なぜ0 = 0 + aが有効だと気づけるだろうか？
本来の目的を見失って探索してしまった感じがある
x + (-x) = 0で突っかかったときに、その困難をどう言語化するのかな
-(ax) = -(a)xを示す必要があるんだけど、これを示すのに0x = 0が必要
多分これは避けられない
逆元の定義（原理）に基づいてこれを示すと考えた以上
ある演算結果が0になることを示した定理が必須になるのでやっぱりここが必要になる可能性は高い
と思うと、やはりこの方針は避けたい
だから、0 + a = 0の方に着目するべきだった
このように困難があることをまともに捉えなかったのが問題な気がするなあ
(4)は(3)を再利用すれば逆元の記号をなかったことにできる。
ab = acを変形して因数分解
ちょっと迷った
bから変形して直接示すのは難しそうかな
aの条件をうまく活用できない...って思ったけど、できるか
b - c = b - c + 0 = b - c + ab - ac =
a\neq 0の条件を活かせるのはどこかと考えると、IXを使いたくなるので、そこに着目
定義 1.1 整除
b \; | \; a b devides a
a|bかつb|aならa = \pm b
定義に基づいて変形
最大って扱いにくくない...？？？
最小も扱いにくいな
定理で示す時は....背理法で示すといいのか？
ac|bcならばa|b
定義に基づいて計算すればおけ
\lbrack a_1, a_2, a_3\rbrack bがa_1 b, a_2b, a_3bの公倍数であることはわかるので
あとはこれの最小性を示せたらいい
これよりも小さい公倍数d' < \lbrack a_1, a_2, a_3\rbrack bが存在したら？
公倍数になるためには、最低限bの倍数である必要がある。
ということは、d' = d'' bということになる。
d'' < \lbrack a_1, a_2, a_3 \rbrack
いま、d''bはa_1b, a_2b, a_3bの公倍数だが、問1.2の内容から
一見図を書くと、確かに存在しそうに見える...が、これはどうやって証明すればいいんだろう
aに対してqbと(q+1)bの間に収まることを言う？
一応、背理法で解く方法はある（けど、当時の自分は思いついていなかった）
背理法と数学的帰納法を組み合わせて、
aがどの区間\lbrack qb, (q+1)b )にも存在しない
区間\lbrack qb, (q+1)b )は\Zの分割
を示せたら、a \in \Zであることと矛盾。
負の場合も一括で示せるから、こっちの方がパッパと済むけど、割り算の本質は現れない
直観主義論理者に怒られそう
でも、ここから解いてもこの問題の難しさは変わっていないような....。
むむむ
どこに着目すればよかったか
割り算の方法
or 最も簡単な場合について考える（0 \leq a < bのときは、確かに満足する整数q, rが存在する）
なので、そこから数学的帰納法でどんどんaを大きい方へ繋げていって定理を証明すればいい
負の場合は適当に
r = 0のときとそうでない時とで少し扱いが変わる
負の数における余りがどうなっているかにも注目したい
余りの観点からこの問題を解いてみる。
余りを使うとx \not | \; yであるようなyを簡単に表せるようになり、捉えやすくなる。
公倍数mは最小公倍数lの倍数である。
l \not | \; mである時と仮定する。
a_i| l, a_i | m
先に示した除法の定理を使うと、mの倍数関係を簡単に書き下せて
ある余り0 < r < lが存在してr + ql = m
左辺はrのせいでa_iで割れない
割れたとしたら、lの最小性に反する。
従って、mもa_iで割れない。
これはmが公倍数であることと矛盾
(a, b) = (b, r)
(a, b)はb,rの最大公約数か？
公約数であることをまず示す。
a - bq = r
従って、rは(a, b)で整除される。
bも(a,b)で整除される。
従って、(a, b)はr, bの最大公約数
最大性？
仮にこれより大きい数d > (a, b)でb, rが割れたとして
a = bq + r
aはdで割れて、bもdで割れることになるので
dはa, bの公約数。
しかし、これは(a,b)の最大性に反するため矛盾
従って、(a,b)は最大公約数である。
と言いたいところだが、実際には
一つ目の[/ (a,b)が公約数であることをまず示す。] における「最大公約数の最大性」を
(a, b)\leq (b, r)
によって表現し、
(b, r) \leq (a, b)を示しにかかるために
a, bの公約数の一つに(b, r)があることを示しにかかればすぐ済む。
ここあたりの議論にx \leq y \land y\leq x \Rightarrow x = yの論法がよく出てくるのは
O(\log a)（a > b）回の計算で済む。
r \leq a/2であることを示しにかかれば良い。
問1.10の計算問題を追いかけていれば、原理はすぐわかる
これは、(a,b)を表式として表すのにすごく便利
(a, b)の倍数関係を調べるのにすごく役に立つ。
(1)の証明に苦戦
実際には、最大性・最小性を不等式として表して=に持っていけば簡単に解ける
(2)は、定理1.7を拡張すればよい
拡張ユークリッドの互除法の使い方がよくわかる問題
cdを解析するために、d = ax + byを使うとよい
けっこうしんどかった
定義として考えると、最大性・最小性は不等式として捉えるのが自然
問1.11の内容をすぐ再利用できる
これのおかげで整除が扱いやすくなってくる
「互いに素」を現状うまく捉える方法は拡張ユークリッドの互除法しかない
計算結果が(a, b) = 1になることは、基本的に
素因数分解
ユークリッドの互除法を適用した後の結果
としてでしか理解しづらい。
ので、拡張ユークリッドの互除法によって(a, b)の倍数関連をa, bの倍数関連を結びつけて理解するのが手っ取り早い。
線形結合の利点
目的
b = cをどう示したらいいんだろうか
b | c, c | bを示すか？
一番簡単に示せるのはこっちかな...。
b - c = 0を示すか？
でも、減算をどう絡ませるかが謎。
色々考えられる。
与えられている条件が結構整除に関わってくる
互いに素の条件は既約分数であることを意味してるんだろうな〜
分数が整数になることは、通分することで一つの値が割り切れることに帰着したい。
\lbrack b, c \rbrack \; | \; ab' + c'd
少なくとも、
b | ab' + c'd
c | ab' + c'd
b'x + c'y = 1
最小公倍数と今の現状をどう絡ませるかが謎だなあ
2/3 + 1/3
粒度が揃っていないと、そもそも整数に揃わない
b, cについて具体例を当てはめて調べてみる
1/b + 2/cだとどう？
bc|1c+2b
左辺に複数入ってるのが扱いにくいので、
b | 1c+2b
b|2bなので、b|1cで割れなきゃいけない
bと1は互いに素だから....
定理1.10から、b|cで割れる！
c|1c+2b
同じく、定理1.10から、c|bで割れる！
よって、b = c
これだ
どう解けば短時間で解決したか？
b | c, c | bを示す方向に目を向けていたのはよかった。
一部分だけ具体例当てはめて考えればよかったのかもなあ
具体例で当てはめすぎると逆に本質が見えなくなる。
一部を固定して考える
bc|???型を扱いにくいと認識していた
それを、+が原因だと認識していたが、その+を避けて解こうとしていたのが原因
+をなくすために立ち回ればよかった
bc|???から、b|???かつc|???に結びつければ+を消すことができていた。
困難（+）を消すためにはどうすれば良いか？ということに注力するべきだった？
「互いに素」を現状うまく捉える方法は拡張ユークリッドの互除法しかない
最大値が等しいことの証明には不等号を使って対応できる
やっと結びついた...！！
「互いに素」を現状うまく捉える方法は拡張ユークリッドの互除法しかない...が、どんどん扱える方法が広がっていきそうだ
拡張ユークリッドの互助法と右辺左辺の結びつきが重要
定義1.4 素数
p > 1ね
改めて考えると「持たない」って定義難しいな あんまり情報がなさそうに見えるけど
問1.18 エラトステネスのふるい
\sqrt{100} = 10まで調べればいいね
nのときに消すのは、n^2以上の数だけでいい
nm \;(m < n)はすでに消えてる
交換則のおかげでこれが成り立ってるように見える
p\ |\ qならばp = q
p\ |\ qの定義\exists c; cp = qに戻って、素数の定義と照らし合わせる。
問1.20 二つの素数で整除できる時
p\ |\ a, q\ |\ aならばpq\ |\ a
定義に戻る。
a = pc_1 = qc_2と表せることができる
c_1はqで整除できることを示せたらOK
問 1.21
んん？pを素数とした時にp|ab --> p|a or p|bであることをどう示せばいいんだろう
背理法....ダメそう。
aもbもpで割り切れなかったら、この式に矛盾する
ほんと？
a, bの因数p_1, p_2によってpで構成されていた場合は...？
でもそれは素数じゃないもんね
これは一般論か？
ああ、1 \leq p_1, p_2 < pとした上で、
p_1\ |\ a, p_2\ |\ bの条件がついていたら、p_1, p_2 = 1しかないって言えりゃいいのか
「a, bの間に素数pがまたがるようなことがない」....のが本質だけど、それをどう整数の関係で言い表せばいいのか
数pがまたがるってどういう状況だろう？
（....とこう呟いておくことで、一旦気を逸らして夜更かししないようにする 他者に共有すると一旦机から離れやすくなることに気がついた）