講義と演習「代数系入門｣ - 1082477703

1：приезд(☆4) （DTxrDxh6）：2004/04/21(水) 01:15: 第一章　整数
§1　集合
よく区別で切るものの集まりを集合と言うことにしましょう.
大きな自然数の集まりは集合とはいえない,
百万以上の自然数全部の集まりは集合といえる程度の.
それ以上の議論はいわばスレ違いということで.

集合を構成する個々のメンバーをその集合の元といいます.
集合は普通ローマンの大文字,元は普通ローマンの小文字で書きます.

xが集合Sの元であることを
x∈S
と書きます.

xがSの元でないことを
x∉ฺS
と書きます.

ボールドのN,ボールドのZ,ボールドのQ,ボールドのR,ボールドのC
はそれぞれ自然数全体の集合,整数全体の集合,有理数全体の集合,
実数全体の集合,複素数全体の集合を表します.
ボールドは出ないのでローマンと区別がつきにくいですが
文脈で判断してください.紛らわしいときはいちいち断ります.
85：quindecim(☆6) （DTxrDxh6）：2004/05/24(月) 00:20: >>84
あ、そうですね。
Φ≠{ｂ_1, …, ｂ_n}⊂J
だからJには正の最小元dが存在する。

でないといけないですね。すみません。
86：quindecim(☆6) （DTxrDxh6）：2004/05/24(月) 00:30: あり？ここのカウンタも変なのでは？
87：LAR-men （lBLdA0dk）：2004/05/24(月) 00:32: ＞Φ≠{ｂ_1, …, ｂ_n}⊂J
だからJには正の最小元dが存在する。

Jには正の元が存在するから正の最小元も存在する
ということでしょうか？
88：quindecim(☆6) （DTxrDxh6）：2004/05/24(月) 00:35: >>87
そうです。J∩N∩{0}^c≠ΦだからJ∩N∩{0}^cには最小元が存在すると。
89：LAR-men （lBLdA0dk）：2004/05/24(月) 00:39: >>88
了解です。
90：まほろ：2004/05/26(水) 22:57: 問題１．
(1)Euclidの互助法を用ゐて
7935=1×5796＋2139
5796=2×2139＋1518
1518=2×621＋276
621=2×276＋69
276=4×69＋0
∴(7935,5796)=69 Ans.

(2)同様に
(39600,32670)=990
(25542,16863)=33
補題Ａを応用して
(39600,32670,25542,16863)
=((39600,32670),(25542,16863))
=(990,33)
=33 Ans.
91：まほろ：2004/05/26(水) 22:58: 問題２．
(鄯)a_1*x_1＋a_2*x_2＋…＋a_n*x_n=m が整数解を持つならば
(a_1,a_2,…,a_n)=d であるから定理３より
d|(a_1*x_1＋a_2*x_2＋…＋a_n*x_n)
即ち d|m
(鄱)d|m ならば
適当な整数kを用いて m=kd と表すことができて、
また、適当な整数 u_1,u_2,…,u_n を用いて
d=a_1*u_1＋a_2*u_2＋…＋a_n*u_n と表すことができるので
a_1*x_1＋a_2*x_2＋…＋a_n*x_n=m=kd=k(a_1*u_1＋a_2*u_2＋…＋a_n*u_n)
⇔a_1*(x_1-k*u_1)＋a_2*(x_2-k*u_2)＋…＋a_n*(x_n-k*u_n)=0
ここで各々の i(1≦i≦n,i∈Z) について x_i=k*u_i としてやると等式は常に成立する。
つまり a_1*x_1＋a_2*x_2＋…＋a_n*x_n=m は整数解を持つ。
以上(鄯)(鄱)より
a_1*x_1＋a_2*x_2＋…＋a_n*x_n=m が整数解を持つための必要十分条件は d|m　Q.E.D.
92：まほろ：2004/05/26(水) 22:58: 問題３．
(a,bc)=d_1 , (a,c)=d_2 とすると
d_1|a , d_1|bc , (a,b)=1 より d_1|d_2 (d_1≦d_2)
また bc≧c であるから d_2≦d_1
よって d_1=d_2
即ち (a,bc)=(a,c)　Q.E.D.

問題４．
(a_1,b_1)=1 , (a_1,b_2)=1 であるから定理４の系より
(a_1,b_1*b_2)=1
(a_1,b_i)=1 (1≦i≦n,i∈Z) であるから系を順次用いて
(a_1,b_1*b_2*…*b_n)=1
(a_i,b_1*b_2*…*b_n)=1 であるから同様にして
(a_1*a_2*…*a_n,b_1*b_2*…*b_n)=1
つまり積 a_1*a_2*…*a_n と b_1*b_2*…*b_n は互いに素 Q.E.D.
93：まほろ：2004/05/26(水) 23:01: 見にくくて申し訳ないです。

>>65のとこなんですがテキストの方はわかるのですが
「{b_1,…,b_n}には正の最小元がある.それをdとおく.」
としてしまうと、たとえば{-2,3,5}という集合を考えたとき
d=2となってしまうのでダメなのでは・・・？

というのが>>80-89の議論ですか？ｗ
94：LAR-men （lBLdA0dk）：2004/05/27(木) 00:34: >>93
ですね
95：quindecim(☆6) （DTxrDxh6）：2004/05/27(木) 02:13: >>90
おｋ
細かいこといえば、たとえば(1)の3行目は7935=5796×1 2139と書くべきかも知れませんが.
(1)の4行目と5行目の間に2139=1518×1 621と書いてくれたら,
目だけで解答追うのが楽になったんですけどね.

>>91
(鄱)の5行目と6行目は正確には同値じゃないですね.
5行目は
a_1*x_1＋a_2*x_2＋…＋a_n*x_n=m
だけのほうがよいでしょう.
あとはok.

>>92
問題３．
3行目は
d_1|a , d_1|bc , (a,b)=1 より (d_1,b)=1.定理４よりd_1|c.よってd_1|d_2となるのでd_1≦d_2.
ということですか？

問題４．
「帰納的に」って言葉を一言添えておいたほうがよいかと.

大体オッケーですね。整数問題に対してちょっと、外側から
見る目が養われてくるような気がしませんか.
96：まほろ：2004/05/27(木) 22:12: >>95
１．申し訳ない。紙からテキストデータにエンコードするときに
一行抜け落ちてしまったようです。
２．了解
３．実はどうしてよいかわからず誤魔化してしまいましたｗ
なるほど、そういうことですかｗｗｗ
４．了解

素数の定理７の辺りまで読みました～
97：quindecim(☆6) （DTxrDxh6）：2004/05/29(土) 17:04: 先、いっていいかな。９ちゃん読んでくれてる？
§４　最小公倍数
a_1…a_n≠0を満たす整数a_1,…,a_nのすべての倍数である整数を,
a_1,…,a_nの公倍数といいます.a_1,…,a_nの正の公倍数全体の集合は
空でないので(a_1…a_nか-a_1…a_nのどちらかはa_1,…,a_nの正の公倍数)
整列性によりその最小元lが存在しますが,lをa_1,…,a_nの最小公倍数といいます.

mをa_1,…,a_nの任意の公倍数だとするとl|mが成り立ちます.
実際mをlでわると除法の定理によりm=lq＋r,0≦r<lを満たす整数の組(q,r)が
存在しますが,mもlもa_1,…,a_nの公倍数なのでr=m-lqだってa_1,…,a_nの公倍数
になります.rは0≦r<lでlの最小性からr=0とならざるを得ません.

上の性質からa_1,…,a_nの公倍数全体の集合は最小公倍数の倍数全体の集合と一致することがわかります.

最大公約数の節の補題Ａ(>>71)のような命題が成立しますが後の演習にします.

定理５　2つの正の整数a,bの最小公倍数lは,abを(a,b)=dで割った商に等しい.

証明　a=a_1d,b=b_1dとおけば定理３系３より(a_1,b_1)=1.
lはaの倍数だからl=ak=(a_1d)k=(a_1k)d.
lはb=b_1dの倍数でもあるから(a_1k)d=(b_1d)m即ちa_1k=b_1mと書け,b_1|a_1k.
(a_1,b_1)=1,b_1|a_1kなので定理４よりb_1|k.
よってk=b_1tと書けるので,l=ak=ab_1tとなる.
ab_1=a*(b/d)=(a/d)*b=a_1bはa,bの公倍数であるのでlの最小性よりt=1.よってl=ab_1=ab/d.■
98：quindecim(☆6) （DTxrDxh6）：2004/05/29(土) 17:04: 問題１　ab≠0となる整数a,bの最小公倍数を[a,b]で表すことにする.
abc≠0となる整数a,b,cに対して[[a,b],c]=[a,b,c].

問題２　対毎に素な正の整数a_1,…,a_nの最小公倍数はa_1…a_n.

問題３　(a,b)=1,a|m,b|m⇒ab|m.
99：LAR-men （lBLdA0dk）：2004/05/30(日) 00:17: 整列性が意外に活躍することに感動
100：quindecim(☆6) （DTxrDxh6）：2004/05/30(日) 01:51: >>99
解析学の初歩(解析概論みたいなの)での
デデキント･カットみたいなものですから。
101：まほろ：2004/06/01(火) 14:12: 解答がうまいこと書けない＿|￣|○
102：まほろ：2004/06/29(火) 21:29: ・・・ヨビコの先生に「深入りしたら落ちるよ」って言われました・・・orz
103：(☆7) （DTxrDxh6）：2004/07/30(金) 22:30: では残った問題は誰かがいつかといてくれるのを期待して…

§５　素数・素因数分解
　2以上の整数で自身と1以外に約数を持たないものを素数, 素数でない2以上の整数を合成数といいます.
pを素数, aを整数とするとpは1とpしか約数を持ちませんので(a, p)=1か(a, p)=pです.
前者のときはaとpは互いに素, 後者のときはp|aですね.
aを整数, p_1, p_2を素数としa|p_1p_2であるとすると定理4(>>74)からa|p_1またはa|p_2がいえます.
したがって帰納的に

補題Ｃ
aを整数とし, p_1, …, p_nがみな素数でありa|p_1…p_nであるならばa|p_iとなる1以上n以下の番号iが必ず存在する.

がいえます.

この補題Ｃを使って所謂「整数論の基本定理｣が示せます.

定理６
任意の2以上の整数はいくつかの素数の積に分解できる.その分解は順序を問わなければ一意である.

注意
pが素数であればpは素数の積には分解できないが, 1つの素数で表されることも「素数の積への分解｣
のうちに入れる慣習が数学にはあります.正確な言葉遣いにこだわって議論が煩雑になるのを防ぐためだと思って下さい.
104：(☆7) （DTxrDxh6）：2004/07/30(金) 22:30: 定理６の証明
2以上の整数のうち素数の積でかけないものがあると仮定すると, 自然数の整列性によりそのようなもののうちの
最小の数が存在する.それをmとおく.mは素数でないので合成数である.よって
　　　　m=de
を満たす自然数d, eが存在する.d, eは1≦d<m, 1≦e<mを満たし, mの最小性によりd, eは素数の積に分解できる.
したがってm(=de)も素数の積に分解できる.
いまmが
　　　　m=p_1…p_k=q_1…q_l
と2通りの素数の積に分解できたとしよう.必要なら番号の付け替えによって補題Ｃによりp_1|q_1と出来るが,
p_1もq_1も素数なのでp_1=q_1.これより
　　　　　p_2…p_k=q_2…q_l.
再び必要なら番号の付け替えによって補題Ｃによりp_2|q_2と出来, p_2=q_2.これより
　　　　　p_3…p_k=q_3…q_l.
この操作を繰り返すと
　　　　　p_k=q_k…q_l　　　　　　(*).
もう一度繰り返すことが出来るとすれば
　　　　　1=q_(k+1)…q_l
となり矛盾.よってこの操作は(*)の段階で
　　　　　p_k=q_k
となっているはずである　■
105：(☆7) （DTxrDxh6）：2004/07/30(金) 22:31: 上の証明中に出てきた素因数p_1, …, p_nの中には同じものがあるかもしれないのでこれらを指数を使って
　　　　　a=(p_1)^(α_1)…(p_n)^(α_n)
とまとめて書き表すことが出来ます.この表し方(つまりi≠jならp_i≠p_jとなる表し方)をaの標準分解と
呼ぶことにします.標準分解では出てくる指数は全部1以上の整数ですが, 0でない整数aに対してa^0=1と
定めれば, 例えば
　　　　　200=2^3・3^0・5^2
などという分解の表現も許されます.

定理６の応用例１
58800=2・294・100=2^2・147・100=2^2・3・7^2・100だから
58800の標準分解は
　　　　　58800=2^4・3^1・5^2・7^2.

定理６の応用例２
整数aの標準分解を
　　　　　a=(p_1)^(α_1)…(p_n)^(α_n)
とするとaの約数全体は
　　　　　(p_1)^(β_1)…(p_n)^(β_n), 各β_iは0≦β_i≦α_i
の形の数全体である.
106：(☆7) （DTxrDxh6）：2004/07/30(金) 22:31: 定理６の応用例２の証明
a={(p_1)^(β_1)…(p_n)^(β_n)}{(p_1)^(α_1-β_1)…(p_n)^(α_n-β_n)}
だから
(p_1)^(β_1)…(p_n)^(β_n), 各β_iは0≦β_i≦α_i
の形の数は皆aの約数.
整数b, cを使ってa=bcと書けるとするとbの素因数は(cの素因数も)aの素因数だから
　　　　　b=(p_1)^(γ_1)…(p_n)^(γ_n),
　　　　　c=(p_1)^(δ_1)…(p_n)^(δ_n).
と書けるが, このとき分解の一意性から各iについてγ_i+δ_i=α_iとなることが分かり,
これより各iについて0≦γ_i≦α_iが分かる■

この応用例２によって指数の組(β_1, …, β_n)の個数が即ちaの約数の総数であることが分かるので

定理６の応用例３
整数aの標準分解を
　　　　　a=(p_1)^(α_1)…(p_n)^(α_n)
とし, aの約数の総数をτ(a)とすると
　　　　　τ(a)=(α_1+1)…(α_n+1).

がいえます.さらに
107：(☆7) （DTxrDxh6）：2004/07/30(金) 22:32: 定理６の応用例４
整数aの標準分解を
　　　　　a=(p_1)^(α_1)…(p_n)^(α_n)
とし, aの約数の総和をσ(a)とすると
　　　　　σ(a)=Π[{1-(p_i)^(α_1+i)}/(1-p_i)].

がσ(α)=Σ[β_1=0, α_1]…Σ[β_n=0, α_n](p_1)^(β_1)…(p_n)^(β_n)
　　　　=Σ[β_1=0, α_1](p_1)^(β_1)…Σ[β_n=0, α_n](p_n)^(β_n)
となることより分かります.

正の整数aの正の約数のうちaでないものをaの真の約数といいます.
正の整数aのすべての真の約数の和がaに等しいときaを完全数といいます.
応用例４の記号を使えばσ(a)=2aであるときaは完全数です.

(m, n)=1ならmの標準分解とnの標準分解の積はmnの標準分解となりますので応用例４によって
　　　　　　　　　σ(mn)=σ(m)σ(n)
が成り立ちますがこのことを使って次の命題が示せます.
108：(☆7) （DTxrDxh6）：2004/07/30(金) 22:32: 命題
eを2以上の整数としa=2^(e-1)(2^e-1)とする.
aが完全数であるための必要十分条件は2^e-1が素数であることである.

命題の証明
十分性:　2^e-1が素数ならσ(a)=(2^e-1){1+(2^e-1)}=2a.
必要性:　(2^(e-1), 2^e-1)=1であるのでσ(a)=σ(2^(e-1))σ(2^e-1)=(2^e-1)σ(2^e-1).
2a=2^e(2^e-1)であるのでaが完全数であるならσ(2^e-1)=(2^e-1)+1となるので2^e-1は素数.

必要性の巧妙な証明はオイラーによるものだそうです.

上の命題において2^e-1なる数が出てきましたが, この形の素数をメルセンヌ数といいます.
1でない整数a, bを使ってe=abと書けるなら2^e-1は2^a-1の倍数となりますので
メルセンヌ数2^e-1が素数であるための必要条件はeが素数であることです.
2^11-1=2047=23・89ですから十分条件ではありません.

メルセンヌ数に似たものにフェルマー数っていう数があります.2^e+1の形の素数です.
eが2以外の素因数を持つならeは奇数因子を持つことになりますから2^e+1は合成数となります.
つまりフェルマー数2^e+1が素数であるための必要条件はeが2の冪となることです.
2^(2^5)+1=2^32+1は合成数だそうです.(手計算をする気力がでません.信じましょう)
したがって十分ではありません.
109：(☆7) （DTxrDxh6）：2004/07/30(金) 22:33: 以下証明は難しくって今の私には手におえない事実ってのを紹介しておきます.
○4で割って3余る完全数はない.
あと
○4で割って1余る完全数が存在するかどうか
は未解決問題だそうです.

有理数の定義
整数mと0でない整数nをつかってm/nで表される数を有理数といい, 有理数全体の集合をボールド体の
Qで表します.0でない有理数m/nはm/n={m/(m, n)}/{n/(m, n)}といつでも"既約分数"で書けます.

この節の最後に…

定理７
素数は無数に存在する.

定理７の証明
もし素数が有限個しかないとすると最大の素数pが存在するがp以下の素数をすべて乗じた数に1を加えた数は
p以下のすべての素数で割り切れないのでこれもまた素数.不合理■
110：(☆7) （DTxrDxh6）：2004/07/30(金) 22:35: あ、書き忘れ。
F_ν=2^(2^ν)+1とおいたとき、
現在までに知られているフェルマー数は
F_0, F_1, F_2, F_3, F_4の5つだけだそうです。
111：(☆7) （DTxrDxh6）：2004/07/30(金) 22:44: 間違い指摘よろしく。
皆さん、問題どうしますか？
112：LAR-men （lBLdA0dk）：2004/07/31(土) 00:16: ぅぁぁぁ
113：(☆7) （DTxrDxh6）：2004/08/07(土) 05:54: とりあえず,問題を置いておきます.有志の皆さん解いてください.
１.　次のことを証明せよ.
　　(a)　合成数aは√aを超えない1でない約数を持つ.
　　(b)　Nを2より大きい整数とし,√Nを超えない素数の全体が知られているとする.
　　　　そのとき,√N<a≦Nである整数aのうちからそれらの素数の倍数を全部除去すれば,
　　　　除去されずに残っている数はすべて素数である.

これは少々入試的ですね.本スレに貼ってもいいかも.

２.　正の整数a,bの素因数分解を
　　a=p_1^α_1…p_k^α_k,b=p_1^β_1…p_k^β_k
　　(p_1,…,p_kは相異なる素数,α_i,β_i∈N)とし,max{α_i,β_i}=γ_i,min{α_i,β_i}=δ_i
　　とする.このときaとbの最小公倍数,最大公約数はそれぞれ
　　p_1^γ_1…p_k^γ_k,p_1^δ_1…p_k^δ_k
　　となることを証明せよ.

３.　pを素数,rを1≦r≦p-1である整数とすれば,pCrはpで割り切れることを示せ.

これもやや入試的ですね.
114：(☆7) （DTxrDxh6）：2004/08/07(土) 05:55: ４.　a_1,…a_nを整数とする.方程式
　　　　x^n+a_1x^(n-1)+…+a_n=0
　　　が有理数の解を持つなら,それは整数であることを証明せよ.

京都府立医科大学かどこかの入試に実際あったのでは.

５.　a,nを正の整数とする.x^n=aとなるような整数xが存在しないならば,
　　この方程式を満たす有理数xも存在しないことを示せ.
　　(2の平方根,5の立方根などが無理数であることがこれで分かりますね)

４.が入試に出たのなら５.だって出る可能性はあるんじゃないかな.

以後整数aに対してτ(a)はaの正の約数の個数,σ(a)はaの正の約数の総和とします.

６.　τ(58800),σ(58800)

高校入試ですな.

７.　(a,b)=1ならばτ(ab)=τ(a)τ(b),σ(ab)=σ(a)σ(b)であることを証明せよ.

前半は済んでますね.
115：(☆7) （DTxrDxh6）：2004/08/07(土) 05:55: ８.９.は本文中でやってしまってました.
８.がメルセンヌ数2^e-1が素数であるための必要条件がeが素数であること,
９.がフェルマー数2^e+1が素数であるための必要条件がeが2の冪であることでした.

１０.　641=5^4+2^4=5･2^7+1に注意して,2^32+1は641を約数に持つことを示せ.
　　　　ただし必要なら5^4･2^28+2^32,5^4･2^28-1はともに641で割り切れることを使ってよい.

工夫次第で入試に出せるかな.

１１.　a_1,…,a_nを対ごとに素な0でない整数とする.そのとき
　　　　1/(a_1…a_n)=(x_1/a_1)+…+(x_n/a_n)
　　　となるような整数x_1,…,x_nが存在することを示せ.

１２.　aを0でない有理数とし,それを既約分数で表したときの分母の標準分解を
　　　　p_1^α_1…p_k^α_kとする.そのとき,適当な整数x_1,…,x_kによって
　　　　　a=(x_1/p_1^α_1)+…+(x_k/p_q^α_k)
　　　と表されることを証明せよ.

１３.　nを2以上の整数としa_1,…,a_nを0でない整数とする.ある素数pと正の整数hとが存在して,
　　　a_1,…,a_nのうち1つのa_iだけがp^hで割り切れ,他のa_jはどれもp^hで割り切れないとき
　　　　S=(1/a_1)+…+(1/a_n)
　　　は整数でないことを証明せよ.
116：(☆7) （DTxrDxh6）：2004/08/07(土) 05:56: １４.　次のことを証明せよ.
　　　(a)　1+(1/2)+(1/3)+…+(1/n)　(n>1)は整数でない.
　　　(b)　1+(1/3)+(1/5)+…+(1/2n-1)　(n>1)は整数でない.

１５.　aを1より大なる整数とする.そのとき,任意の正の整数nは
　　　　　　n=c_0+c_1a+…+c_ka^k,　0≦c_0<a,0≦c_1<a,…,0<c_k<a
　　　の形に一意的に書けることを示せ.

a進展開の一意性ですな.

１６.　aを2以上の整数とする.aがそのいくつかの真の約数の和に等しいとき,aを準完全数という.
　　　すべての2以上の真の約数が準完全数でない準完全数を規約な準完全数という.
　　　a=2^npでpが2^n<p<2^(n+1)を満たす素数ならaは規約な準完全数である.

１７.　n個ずつの整数からなるm個の組
　　　　　　x_1(1),…,x_n(1);
　　　　　　x_1(2),…,x_n(2);
　　　　　　　　　 …
　　　　　　x_1(m),…,x_n(m)
　　　を作り,各組から1つずつ適当に数を選んで和をとると0からn^m-1までのすべての整数が
　　　得られるようにせよ.
117：(☆7) （DTxrDxh6）：2004/08/07(土) 05:58: １８.　nを正の整数,pを素数とする.n!の標準分解に現れるpの冪指数は
　　　　　　[n/p]+[n/p^2]+[n/p^3]+…
　　　に等しいことを示せ.

１９.　1234!に含まれる5の冪指数を求めよ.

１９みたいなんを某国立大学教育学部附属中学の入試で見た記憶が…

２０.　αを無理数,Nを正の整数とするとき
　　　　　　　　|mα-n|<1/N
　　　を満たすような整数m,n,0<m≦Nが存在することを証明せよ.

本スレの去年の住人さんなんかにはおなじみかな.

えー、入試ででてもおかしくない問題ばかりな気がします.受験生諸君の挑戦も期待.
118：（DTxrDxh6）：2005/01/03(月) 05:21: ここも随分留守にしてしもたなあ.問題誰か解いてえな.

§６　同値関係, 合同式
Sを空でない集合とし, 順序のついた対(a, b)がS×Sのある部分集合の元であることを,
a～bと書くことにします.～を(その部分集合から導かれた)関係といいます.
(http://jbbs.livedoor.jp/bbs/read.cgi/study/4125/1078049875/645-647 参照)
関係～が反射律(すべてのSの元aに対してa～a), 対称律(すべてのS×Sの元(a, b)に対して
a～bならb～a)推移律(すべてのS×S×Sの元(a, b, c)に対して, a～bかつb～cならa～c)の
すべてを満たすとき～をS上の同値関係といいます.

空でない集合S上に同値関係～が入ってるとしましょう.Sの元aに対してC_a={x∈S|a～x}とおきます.
これを関係～に関するaの同値類, あるいは略して類と呼びます.
a～bであるときC_a=C_bです.
実際, x∈C_aであるとすると, C_aの定義からa～x, 対称律よりx～a, これと前提a～bより
推移律を使えばx～b, 再び対称律よりb～xですのでx∈C_bですし, 前提a～bは対称律によれば
b～aですのでx∈C_bならばx∈C_aもまったく同様に示せます.
a～bでないときC_a∩C_b=Φです.
実際, 集合C_a∩C_bが元xを持つとすればC_a, C_bの定義からa～x, b～xですが対称律と推移律より
a～bが導かれてしまいます.
上の二つの事実は同値関係～がSをいくつかの同値類に分割を生じさせることを意味しますが,
この分割をSの～による類別といったりします.各同値類の任意の元をその同値類の代表元といいます.
代表元という呼び名がふさわしい理由は, C_aの任意の元xに対してC_a=C_xだからです.C_aのどの元を
代表扱いしてもかまわないってこってすね.
119：（DTxrDxh6）：2005/01/06(木) 08:12: Zにおける合同関係を紹介しましょう.
mを与えられた正の整数とします.(a, b)∈Z×Zに対して
m|(a-b)のときaとbはmを法として合同といい,
a≡b (mod m)
と書きます.
合同関係は同値関係です.
実際, a-a=0mですので反射律を満たしますし,
a-b=dmなる整数dが存在すればb-a=(-d)mですから対称律も満たします.
a-b=sm, b-c=tmなる整数s, tが存在すればa-c=(a-b)+(b-c)=(s+t)mですから推移律も満たします.
さらに
a≡a'(mod m)かつb≡b'(mod m)なら
a-a'=d_1m, b-b'=d_2mをみたす整数d_1, d_2があり
(a+b)-(a'+b')=(a-a')+(b-b')=(d_1+d_2)m,
(a-b)-(a'-b')=(a-a')-(b-b')=(d_1-d_2)m
となるので
a+b≡a'+b'(mod m),a-b≡a'-b'(mod m)
ab-a'b'=ab-ab'+ab'-a'b'=a(b-b')+(a-a')b'
=ad_2m+d_1mb'=(ad_2+b'd_1)m
となるので
aa'≡bb'(mod m)が成り立ちます.
120：名無し研究員さん：2005/01/08(土) 07:09: おもしろそーだな。暇なときに解いてみるわ。
121：（DTxrDxh6）：2005/01/09(日) 06:44: >>120
是非！！よろしく。

例.　整数aを通常のように十進法で
a=a_0+a_1･10+a_2･10^2+…+a_n10^n
と表すと10≡1 (mod 9)なので
a≡a_0+a_1+a_2+…+a_n,
10≡-1 (mod 11)なので
a≡a_0-a_1+a_2+…+(-1)^na_n (mod 11).
とくに
aが9で割り切れるための必要十分条件はaの各桁の和が9で割り切れることであり,
aが11で割り切れるための必要十分条件はa_0-a_1+a_2+…+(-1)^na_nが11で割り切れることです.
たとえば
1923482962≡1+9+2+3+4+8+2+9+6+2≡2+6+2≡1 (mod 9),
1923482962≡1-9+2-3+4-8+2-9+6-2≡-9+2+2=-5≡6 (mod 11)
なので1923482962を9で割った余りは1,11で割ったあまりは6です.
122：（DTxrDxh6）：2005/01/10(月) 04:13: mを法とする合同関係によるZの類別の同値類を,法mに関する剰余類といいます.
aをある剰余類の代表元とすると,その剰余類はaとmを法として合同な数全体の集合
即ち{x∈Z|a≡x (mod m)}={a+mk|k∈Z}です.
定理２(>>24)によればaとmに対して
a=mq+r, 0≦r<m
をみたす整数q,rの組がただ一組だけ存在します.
したがって任意の整数aは集合{0,1,…,m-1}の中に1つだけmを法として合同な整数を持ちます.
これは,0,1,…,m-1をそれぞれ代表元とするm個の剰余類があるということを示しています.
法2に関する剰余類は0を代表元とする偶数全体の集合と,1を代表元とする奇数全体の集合です.
法3に関する剰余類は3の倍数全体の集合と3で割って1余る数全体の集合と,3で割って2余る
数全体の集合です.
123：（DTxrDxh6）：2005/01/10(月) 04:14: 法mに関するm個の剰余類から,代表元を1つずつとって作ったm個の整数の組を
法mに関する完全剰余系といいます.
例えば
2,5,8,-1,11
は法5に関する完全剰余系です.
m個の整数
x_1,x_2,…x_m
が,どの2つをとってもmを法として合同でないとします.
すると,各x_iをmで割ったあまりをr_iとしたとき
r_1,…,r_mは全部違う数だということになります.
各r_iは0以上m-1以下の整数ですから
{r_1,…,r_m}={0,1,…,m-1}
ということになります.
逆に
x_1,…,x_m
が法mに関する完全剰余系であるとすると
各x_iをmで割ったあまりをr_iとしたとき
{r_1,…,r_m}={0,1,…,m-1}
であるので
{r_i}はどの2つをとってもmを法として合同ではありません.
よって{x_i}もどの2つをとってもmを法として合同ではありません.
124：（DTxrDxh6）：2005/01/10(月) 04:15: 即ち

m個の整数
x_1,…,x_m
が法mに関する完全剰余系であるための必要十分条件は
どの2つをとっても法mに関して合同でないことである

ということがいえるわけです.

補題Ｄ　mを正の整数として(a,m)=1とする.x_1,…,x_mが法mに関する完全剰余系
であるとすると,ax_1,…,ax_mも法mに関する完全剰余系である.

証明　ax_i≡ax_j (mod m)であるような相異なる1以上m以下の番号i,jがあったとする.
このときm|a(x_i-x_j)であるが(a,m)=1であるから定理４(>>74)よりm|(x_i-x_j)となってしまう.
矛盾■
125：（DTxrDxh6）：2005/01/10(月) 04:15: 一章六節の問題.
１.　a≡b(mod m)ならば任意の整数kに対してa≡b+mk(mod m).
２.　ac≡bc(mod m),(c,m)=1ならばa≡b(mod m).
３.　a≡b(mod m)ならば,任意の正の整数kに対してak≡bk(mod mk).
４.　a≡b(mod m)とし,d|a,d|b,d|mとする.そのときa=a_1d,b=b_1d,m=m_1dとすればa_1≡b_1(mod m_1).
５.　a≡b(mod m)ならば,mの任意の正の約数dに対してa≡b(mod d).
６.　a≡b(mod m_1),a≡b(mod m_2),…,a≡b(mod m_k)ならば,m_1,m_2,…,m_kの最小公倍数mに対してa≡b(mod m).
７.　pを素数とすると,任意の整数x,yに対して(x+y)^p≡x^p+y^p(mod p).
８.　pを素数とすると,任意の整数x_1,…,x_nに対して(x_1+…+x_n)^p≡x_1^p+…+x_n^p(mod p).
９.　pを素数,aを0≦a≦p-1なる整数とすればp-1Ca≡(-1)^a(mod p).
１０.(2^100-1)^99を100で割ったあまりを求めよ.
１１.3^30≡1+17･31(mod 31^2).
126：こけこっこ （M3IWa4lY）：2005/01/11(火) 20:26: >>125
(10)
2^100 - 1
=(1000+24)^10 - 1 (∵2^10=1024)
≡24^10 - 1 (mod 100)
=(500+76)^10 - 1 (∵24^2=576)
≡76^10 - 1 (mod 100)
=5776^5 - 1 (∵76^2=5776)
=(100k+76)^5 - 1 (k=57)
≡76^5 - 1 (mod 100)
=76*(100k+76)^2 - 1
≡76^3 - 1 (mod 100)
=76(100k+76) - 1
≡76^2 - 1 (mod 100)
=(100k+76) - 1
≡75 (mod 100)

(2^100 - 1)^99
≡75^99 (mod 100)
=(421800+75)^33 (∵75^3=421875)
=(100m+75)^33 (m=4218)
≡75^33 (mod 100)
=(100m+75)^11
≡75^11 (mod 100)
=75^2*(100m+75)^3
≡75^5 (mod 100)
=75^2*(100m+75)
≡75^3 (mod 100)
=100m+75
≡75 (mod 100)

∴75・・・答
127：こけこっこ （M3IWa4lY）：2005/01/11(火) 20:28: (11)
3^7=2187 より，
3^7=2k+265　(k=961)

3^30
=3^2*(2k+265)^4
≡3^2*265^4 (mod k)
=(210675)^2 (∵3*265^2=210675)
=(219k+216)^2
≡216^2 (mod k)
=46656 (∵ 216^2=46656)
=48k+528
≡528 (mod k)
∴
3^30
≡528 (mod 31^2)
=1+17*31
本質的な意味は分からず。
128：Мечислав （DTxrDxh6）：2005/01/20(木) 06:26: >>126
五行目から六行目
24^10-1
=(500+76)^5-1.
ですね。
つぎのようにすればどうでしょう。

2^n≡a_n(mod 100),0≦a_n≦99
なる数列{a_n}を順に並べると
2, 4, 8,16,32,64,28,56,12,24,
48,96,92,84,68,36,72,44,88,76,
52,

よって
(2^100-1)≡(a_100-1)≡(a_20-1)≡75 (mod 100).

75^n≡b_n(mod 100),0≦b_m≦99
なる数列{b_n}を順に並べると
75,25,75,

よって
(2^100-1)^99≡75^99≡b_99≡b_1≡75(mod 100).

2^200≡2^100(mod 100)だから>>126の結果と一致しちゃうわけですね。。
129：Мечислав （DTxrDxh6）：2005/01/20(木) 06:27: >>127
おｋ.

3^30≡(3^7)^4･9≡(81･27)^4･9≡((31+50)(31-4))^4･9
≡(31･46-200)^4･9≡(31･15-200)^4･9≡(31･15-31･6-14)^4･9
≡(31･9-14)^4･9≡(-4･31･9･14^3+14^4)･9
≡(-31･5･14^3+56･49･14)･9≡(-31･8･14^2+(31+25)(31+18)･14)･9
≡(-31･49+(31･43+450)･14)･9≡(-31･18+(31･12+31･14+16)･14)･9
≡(-31･18+(31･26+16)･14)･9≡(-31･18+31･26･14+16･14)･9
≡(-31･18+31･21･7+224)･9≡(-31･18+31･23+31･7+7)･9
≡(31･12+7)･9≡31･12･9+63≡31･15+31･2+1≡31･17+1(mod 31^2)

でもよいですね。
130：Мечислав （DTxrDxh6）：2005/01/23(日) 06:21: §７　1次の合同式
mを正の整数とし,f(x)=a_nx^n+a_(n-1)x^(n-1)+…+a_1x+a_0を整係数多項式とする.
合同方程式f(x)≡0(mod m)を解くとは,このしきを満たす整数xをすべて見つけること
をいいます.合同方程式のことを,単に合同式ということもあるようです.
m|a_nでないときこの合同式はn次であるといいます.
さて,合同式は辺々足したり,掛けたりってのが自由ですので(cf >>119)
x_1という整数がf(x)≡0(mod m)を満たしているならx≡x_1(mod m)なる整数xは皆
f(x)≡0(mod m)を満たします.実際x≡x_1(mod m)ならf(x)≡f(x_1)(mod m)ですから.
したがってx_1を含む剰余類{x|x≡x_1(mod m)}を合同式f(x)≡0(mod m)の1つの解である
という言い方をしたりします.
f(x)≡0(mod m)の解の個数は,法mに関する完全剰余系のうちでこの式を満たすものの個数
である,と解釈するわけです.

以下,1次の合同式のみを扱うことにしましょう.
先ず,次の定理が成り立ちます.
131：Мечислав(☆9) （DTxrDxh6）：2005/01/23(日) 06:23: 定理８　(a,m)=1なら合同式ax≡b(mod m)はただ1つの解を持つ.

証明　§６補題Ｄ(>>124)によって,x_1,…,x_mが法mに関する完全剰余系なら
ax_1,…,ax_mもそうである.与えられた整数bに対してこの{ax_1,…,ax_m}のうち,
1つだけが法mに関してbと合同である.ax_i≡b(mod m)とすると,合同式ax≡b(mod m)は
唯一の解x≡x_i(mod m)をもつ■

実際に合同式を解いて見ましょう.

例１　25x≡1 (mod 56)を解け.

解答　25x≡1(mod 56)の両辺を2倍して50x≡2(mod 56),50≡-6(mod 56)より
-6x≡2(mod 56).両辺4倍して-24x≡8(mod 56).もとの合同式と辺々足してx≡9(mod 56).

目の子でみつけたようなもんだけど,こういう方法も法の値が比較的
小さければ有効な手立てでありましょう.
132：Мечислав(☆9) （DTxrDxh6）：2005/02/09(水) 01:03:11: 例２　80x≡339(mod 583)
例２を体系的に解くために>>125の問題１と問題２を解いておきます。

問題１.　a≡b(mod m)ならば任意の整数kに対してa≡b+mk(mod m).

解答.　a≡b(mod m)⇔m|a-b⇔∃d∈Z(a-b=md).このとき
∀k∈Z(a-b-mk=m(d-k)).よって∀k∈Z(m|a-(b+mk))⇔a≡b+mk(mod m).

問題２.　ac≡bc(mod m),(c,m)=1ならばa≡b(mod m).

解答　ac≡bc(mod m)⇔m|(a-b)c.このとき(c, m)=1だから定理４(>>74)より
m|(a-b)⇔a≡b(mod m).
133：Мечислав(☆9) （DTxrDxh6）：2005/02/09(水) 01:03:38: さて例２を解くためには80=2^4･5で(2,583)=(5,583)=1なので問題１より
右辺の339に583の何倍かを足したものを339の代わりとして,問題２より
その値が2だの5で割り切れたら両辺で割ることができ,少し簡単な合同式に代わります.
ところでpが奇数であるならp≡±1(mod 4)なので2つの奇数の和か差は4で割り切れます.
これらのことを利用すれば
80x≡339(mod 583)⇔80x≡339-583(mod 583)⇔80x≡-244(mod 583)⇔20x≡-61(mod 583)
20x≡-61-583(mod 583)⇔20x≡-644(mod 583)⇔5x≡-161(mod 583).
-161+583t≡0(mod 5)なるtを見つければ5x≡-161(mod 583)は両辺を5で「割る」ことが
できますが,-161+583t≡0(mod 5)⇔-1+3t≡0(mod 5)⇔t≡2(mod 5)なので
80x≡339(mod 583)⇔5x≡-161(mod 583)⇔5x≡-161+2･583(mod 583)⇔5x≡-161+1166(mod 583)
⇔5x≡1005(mod 583)⇔x≡201(mod 583)となります.
実際,80･201-339=16080-339=15741=3･5247=3^2･1749=3^3･583.となりたしかに
80･201≡339(mod 583)です.
134：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 01:57:42: いくつかの異なった法をもつ連立1次合同式についての基本的な定理を紹介します.
定理９　m_1,…,m_k(k≧2)を対毎に素な正の整数とする.b_1,…,b_kを任意の整数とすると
連立合同式x≡b_1(mod m_1)∧…∧x≡b_k(mod m_k)は積m=m_1･…･m_kを法として
ただ1つの解を持つ.

この定理を証明するために>>125の問題５と６を示しておきましょう.

５.　a≡b(mod m)ならば,mの任意の正の約数dに対してa≡b(mod d).

５.の証明
a≡b(mod m)でd|m,d>0ならば,m|(a-b)とd|mなのでd|(a-b)即ちa≡b(mod d).■

６.　a≡b(mod m_1),a≡b(mod m_2),…,a≡b(mod m_k)ならば,m_1,m_2,…,m_kの最小公倍数mに対して
a≡b(mod m).
135：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 01:58:18: ６.の証明
各i∈{1,…,k}に対してa≡b(mod m_i)であるとするとm_i|(a-b).よってa-bはm_1,…,m_kの公倍数.
>>97で示したようにm|(a-b).即ちa≡b(mod m).■

定理９の証明
各i∈{1,…,k}に対してM_i=m/m_iとおく.すべてのj∈{1,…,i-1,i+1,…,k}に対して
(m_i,m_j)=1だから定理４の系(>>76)を繰り返し使えば(m_i,M_i)=1.
よって定理８(>>131)より各i∈{1,…,k}に対してM_it_i≡b_i(mod m_i)を満たす整数t_iが存在する.
x_0=M_1t_1+…+M_kt_kとおくと問題１(>>132)よりx_0は連立合同式の解である.
このときすべてのi∈{1,…,k}に対してx≡x_0(mod m_i)だから,与えられた連立合同式は
x≡x_0(mod m_1)∧…∧x≡x_0(mod m_k)…☆
と同値である.
m_1,…,m_kは対毎に素だからmはこれらの最小公倍数である.よって問題６より
☆を満たすxについてx≡x_0(mod m).逆にx≡x_0(mod m)を満たすxは問題５より
☆を満たす.以上より与えられた連立合同式は,mを法としてただ1つの解{x|x_0≡x(mod m)}を持つ.■
136：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 05:39:19: >>135
訂正.
定理９の証明の三行目.
× M_it_i≡b_i(mod m_i)を
○ m_it_i≡1(mod m_i)を
137：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 06:10:05: 例３　b_1,b_2,b_3を任意の整数として合同式x≡b_1(mod 4)∧x≡b_2(mod 5)∧x≡b_3(mod 7)を解く.

5･7t_1≡1(mod 4)を満たすt_1=-1,4･7t_2≡1(mod 5)を満たすt_2=2,4･5t_3≡1(mod 7)を満たすt_3=-1.
よって与えられた合同式の解は4･5･7を法として
5･7･(-1)b_1+4･7･2b_2+4･5･(-1)b_3=-35b_1+56b_2-20b_3と合同な数.
例えば,連立合同式x≡2(mod 4)∧x≡1(mod 5)∧x≡3(mod 7)の解は
x≡-5･7･2+2^3･7･1-2^2･5･3(mod 3･5･7)⇔x≡-74(mod 140)⇔x≡66(mod 140).

別の解き方としては,連立合同式を前から順に解く方法もあります.
第1の合同式x≡2(mod 4)をみたすxはtを任意の整数としてx=2+4t.
2+4t-1=1+4tだから,
2+4tが第2の合同式x≡1(mod 5)も満たすためのtの必要十分条件は,t≡1(mod 5).
t≡1(mod 5)をみたすtはsを任意の整数としてt=1+5sであるから
第1の合同式と第2の合同式を同時に満たすxはsを任意の整数としてx=2+4(1+5s)=6+20s
6+20s-3=3+20sだから
6+20sが第3の合同式x≡3(mod 7)も満たすためのsの必要十分条件は,s≡3(mod 7).
s≡3(mod 7)をみたすsはuを任意の整数としてs=3+7uであるから
連立合同式を同時にみたすxはuを任意の整数としてx=6+20(3+7u)=66+140u.
即ちx≡66(mod 140).
138：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 06:43:24: 一章七節の問題
１.　(a,m)=d>1とする.合同式ax≡b(mod m)が解を持つための必要十分条件はd|b.またこのとき解はd個.
２.　m_1,…,m_kの最小公倍数を[m_1,…,m_k]と書く.
　　　(a)　d=(m_1,n_2)とすれば,
　　　連立合同式x≡b_1(mod m_1)∧x≡b_2(mod m_2)が解を持つ⇔b_1≡b_2(mod d).
　　　またこのとき解は[m_1,m_2]を法として一意.
　　　(b)　連立合同式x≡b_1(mod m_1)∧…∧x≡b_k(mod m_k)が解を持つなら
　　　[m_1,…,m_k]を法として一意.
３.　(a)　19x≡27(mod 35)　(b)　47x≡89(mod 111)　(c)　256x≡147(mod 333)
　　 (d)　81x≡127(mod 250)(e)　111x≡75(mod 321) (f)　80x≡55(mod 185)
４.　80x-583y=339をみたす整数x,yの組.
５.　連立合同式x≡b_1(mod 3)∧x≡b_2(mod 7)∧x≡b_3(mod 16)を解き,3,7,16で割った余りが
　　それぞれ1,4,11であるようなすべての整数を求めよ.
６.　x≡3(mod 8)∧x≡11(mod 20)∧x≡1(mod 15).
７.　xに5を法とするある完全剰余系の値を代入することによって,合同式
　　 x^5+2x^2+3x+4≡0(mod 5)
　　の解を求めよ.
８.　x^5+x+1≡0(mod 7).
９.　x^5+x+1≡0(mod 35)
１０.　pを素数とし,0<a<pとする.合同式ax≡1(mod p)の解はx≡(-1)^(a-1)･C(p,a)/p(mod p).
139：Мечислав(☆9) （DTxrDxh6）：2005/02/13(日) 06:43:23: 一章七節の問題
１.　(a,m)=d>1とする.合同式ax≡b(mod m)が解を持つための必要十分条件はd|b.またこのとき解はd個.
２.　m_1,…,m_kの最小公倍数を[m_1,…,m_k]と書く.
　　　(a)　d=(m_1,n_2)とすれば,
　　　連立合同式x≡b_1(mod m_1)∧x≡b_2(mod m_2)が解を持つ⇔b_1≡b_2(mod d).
　　　またこのとき解は[m_1,m_2]を法として一意.
　　　(b)　連立合同式x≡b_1(mod m_1)∧…∧x≡b_k(mod m_k)が解を持つなら
　　　[m_1,…,m_k]を法として一意.
３.　(a)　19x≡27(mod 35)　(b)　47x≡89(mod 111)　(c)　256x≡147(mod 333)
　　 (d)　81x≡127(mod 250)(e)　111x≡75(mod 321) (f)　80x≡55(mod 185)
４.　80x-583y=339をみたす整数x,yの組.
５.　連立合同式x≡b_1(mod 3)∧x≡b_2(mod 7)∧x≡b_3(mod 16)を解き,3,7,16で割った余りが
　　それぞれ1,4,11であるようなすべての整数を求めよ.
６.　x≡3(mod 8)∧x≡11(mod 20)∧x≡1(mod 15).
７.　xに5を法とするある完全剰余系の値を代入することによって,合同式
　　 x^5+2x^2+3x+4≡0(mod 5)
　　の解を求めよ.
８.　x^5+x+1≡0(mod 7).
９.　x^5+x+1≡0(mod 35)
１０.　pを素数とし,0<a<pとする.合同式ax≡1(mod p)の解はx≡(-1)^(a-1)･C(p,a)/p(mod p).
140：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:11:07: §８　2つの整数論的関数
すべての正の整数で定義され,実数値または複素数値を取る関数を整数論的関数といいます.
この節では2つの整数論的関数を紹介しましょう.
一つ目はオイラー関数φです.φ(n)はnと互いに素である正の整数の個数であると定義します.
たとえば,φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2,φ(5)=4,φ(6)=2,φ(7)=6,φ(8)=4です.

この定義は次のように言い換えることも可能です.
§３補題B(>>72)によるとa≡b(mod n)なら(n,a)=(n,b)ですので,
nを法とするある剰余類のある元がnと互いに素であるとすると,
その剰余類のほかのすべての元もnと互いに素です.
このような剰余類を,nを法とする既約剰余類といいます.
φ(n)はnを法とする既約剰余類の個数と一致します.

各既約剰余類から代表元を1つずつとって得られるφ(n)個の整数の組を
nを法とする既約剰余系といいます.
nを法とする完全剰余系からnと互いに素なφ(n)個の整数を選べば,
それが即ち既約剰余系です.
また与えられたφ(n)個の整数が既約剰余系であるための必要十分条件は,
それらのうちのどの2つもnを法として合同でなく,どれもがnと互いに素であることです.
141：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:11:52: 定理１０　n=p_1^(α_1)…p_n^(α_n)をnの標準分解とすると
φ(n)=(p_1^(α_1)-p_1^(α_1-1))…(p_n^(α_n)-p_n^(α_n-1))=n(1-1/p_1)…(1-1/p_n).
とくに
φ(p^α)=p^α-p^(α-1),φ(p)=p-1.

定理１０の証明
まず,αが2以上の整数のとき(p^α,k)>1となる1以上p^α以下の整数kはp^α以下のpの倍数であり,
p^α=p･p^(α-1)よりその個数はp^(α-1)個.よってφ(p^α)=p^α-p^(α-1).
(p,k)>1となる1以上p以下の整数kはpのみであるのでφ(p)=p-1.
142：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:12:13: 一般のケースを証明するために次の補題Ｅを示す.

補題Ｅ　(m,n)=1ならばφ(mn)=φ(m)φ(n).

補題Ｅの証明　S,T,Uをそれぞれ法m,n,mnに関する完全剰余系,S*,T*,U*を法m,n,mnに関する
既約剰余系とする.S,Tが完全剰余系であることから,
任意のUの元zに対してz≡x(mod m)となるSの元xが一意に存在し,
z≡y(mod n)となるTの元yが一意に存在する.
また(m,n)=1を仮定するなら定理９(>>134)が成り立つので,
任意のS×Tの元(x,y)に対してz≡x(mod m)∧z≡y(mod n)を満たすUの元zが一意に存在する.
即ちzにz≡x(mod m),z≡y(mod n)をみたす(x,y)を対応させる写像をUからS×Tへの写像fと
定めると,このfは全単射である.
このfをU*に制限したものf|U*を考える.(z,m)=d>1とすると(z,mn)≧dとなるので
とz∈U*なら(z,mn)=1だが,このとき(z,m)=1かつ(z,n)=1でなければならない.
また(z,mn)=d>1で(z,m)=1だとすると(z,n)≧dでなければならないので
(z,m)=1かつ(z,n)=1ならば(z,mn)=1.
即ち(z,m)=1かつ(z,n)=1であることは(z,mn)=1であるための必要十分条件である.
よってz∈U*ならf(z)=(x,y)とすると(x,m)=1かつ(y,n)=1即ちf(z)∈S*×T*.
逆に(x,y)∈S*×T*であるなら(x,m)=1かつ(y,n)=1であるがf(z)=(x,y)となるUの元
zに対して(z,m)=1かつ(z,n)=1となるので(z,mn)=1即ちz∈U*となる.
以上よりf|U*も全単射となる.(補題Ｅの証明了)
143：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:12:35: 定理１０の証明(つづき)
n=p_1^(α_1)…p_n^(α_n)がnの標準分解ならp_1^(α_1),…,p_n^(α_n)は対毎に素だから
補題Ｅを繰り返し用いて
φ(n)=φ(p_1^(α_1))…φ(p_n^(α_n)).
さらに,先に証明したn=p^αのときの定理１０を用いれば
φ(n)=(p_1^(α_1)-p_1^(α_1-1))…(p_n^(α_n)-p_n^(α_n-1)).
p^α-p^(α-1)=p^α(1-1/p)なので
φ(n)=p_1^(α_1)…p_n^(α_n)(1-1/p_1)…(1-1/p_n)=n(1-1/p_1)…(1-1/p_n).■

えと,例えば,φ(720)=φ(2^4･3^2･5)=2^4･3^2･5(1-1/2)(1-1/3)(1-1/5)
=(2^4･3^2･5･1･2･2^2)/(2･3･5)=2^6･3=192.です.
144：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:12:58: 次はメビウス関数μです.まず,μ(1)=1とします.nが素数の平方で割り切れる場合は
μ(n)=0,n=p_1…p_kと標準分解できるときはμ(n)=(-1)^kと定義します.
たとえば,μ(1)=1,μ(2)=-1,μ(3)=-1,μ(4)=0,μ(5)=-1,μ(6)=1,μ(7)=-1,μ(8)=0です.

定理１１　n>1ならばΣ[d|n]μ(d)=0,ただしdはnのすべての正の約数を渡る.

証明　nの標準分解に出てくる指数が1の素因数がp_1,…,p_kであるとする.
nの正の約数dのうち,平方因子を含むものについてはμ(d)=0であるから
指数が1の素因数のみからなる約数dについてだけ考えればよい.
指数が1の素因数のみからなる約数はp_1,…,p_kからいくつかを選んで積を作ったもの
であるので,μ(1)=1も考慮に入れて
μ(n)=1+C(k,1)(-1)^1+…+C(k,k)(-1)^k.
二項定理によるとμ(n)=(1-1)^k=0.■
145：Мечислав(☆9) （DTxrDxh6）：2005/02/21(月) 06:13:18: 一章八節の問題
１.　1から100までの整数nについてのφ(n)とμ(n)の数表をつくってみよ.
２.　任意の正の整数nに対してΣ[d|n]φ(d)=n
３.　(整数論的関数の反転公式).　F(n)を整数論的関数とし,G(n)=Σ[d|n]F(d)とおく.
　　　このときF(n)=Σ[d|n]μ(d)G(n/d).
４.　任意の正の整数nに対してφ(n)=Σ[d|n]μ(d)n/d.
５.　nを1より大きい整数とする.1,…,nのうちnと互いに素な数の和はn･φ(n)/2.
６.　整数論的関数θが乗法的であるとは,θ(1)=1で,(a,b)=1ならθ(ab)=θ(a)θ(b)
　　　が成り立つことをいう.
　　(a)　μは乗法的.
　　(b)　θ_1,θ_2が乗法的ならばθ_1(n)･θ_2(n)=θ(n)と定義されるθも乗法的.
　　(c)　θを乗法的,n=p_1^(α_1)…p_k^(α_k)を標準分解だとすると
　　　Σ[d|n]θ(d)=(Σ[β_1=0,α_1]θ(p_1^(β_1))…(Σ[β_k=0,α_k]θ(p_k^(β_k)).
７.　F(n)を整数論的関数とし,G(n)=Σ[d|n]F(d)とおく.このとき
　　　Fが乗法的であるための必定十分条件はGが乗法的である.
８.　m_1,…,m_kを対毎に素な正の整数,それらすべての積をm,1以上k以下の各整数iに対して,
　　　M_i=m/m_iとおく.
　　　整数x_1,…,x_kがそれぞれm_1,…,m_kを法とするある完全剰余系を動けば
　　　M_1x_1+…+M_kx_kという形の数全体は法mに関する完全剰余系であることを示せ.
　　　この形の数がmと互いに素であるためには,x_1,…,x_kがそれぞれm_1,…,m_kと互いに素
　　　であることが必要十分であるを示せ.
　　　上の事実からφの乗法性を導け.
146：Мечислав(☆9) （DTxrDxh6）：2005/02/24(木) 22:00:14: §９　オイラーの定理とフェルマの定理
前管理人にとっての二年越しの宿題がいまここに完結します.
「東大」「才能」「数学」
http://school2.2ch.net/test/read.cgi/kouri/1061202039/82
で僕が提出した問題を,長助くんが回答した
「東大」「才能」「全教科」ver2.0
http://school2.2ch.net/test/read.cgi/kouri/1061993330/362-367
のなかに出てきた定理
「東大」「才能」「全教科」ver2.0
http://school2.2ch.net/test/read.cgi/kouri/1061993330/956
を,９くんが
「東大」「努力」「全教科」ver3.0
http://school2.2ch.net/test/read.cgi/kouri/1063602221/22
でスレ上の投下問題にしてしまって,スレ上では未解決のままの定理です.
147：Мечислав(☆9) （DTxrDxh6）：2005/02/24(木) 22:00:37: 補題Ｆ　m>0で(a,m)=1とする.x_1,…,x_φ(m)が法mに関する既約剰余系
であるなら,ax_1,…,ax_φ(m)もそうである.

補題Ｆの証明　i≠jのときax_i≡ax_j(mod m)とするとm|a(x_i-x_j).
(a,m)=1なので定理４(>>74)よりm|(x_i-x_j)即ちx_i≡x_j(mod m)となり
x_1,…,x_φ(m)が既約剰余系であることに反する.よって
ax_1,…,ax_φ(m)はどの2つをとっても法mに関して合同でない.
さらに(a,m)=1,(x_1,m)=1,…,(x_φ(m),m)=1なので定理４系(>>76)より
ax_1,…,ax_φ(m)はどれもmと互いに素である.■
148：Мечислав(☆9) （DTxrDxh6）：2005/02/24(木) 22:01:00: 定理１２(オイラー)　mが正の整数で(a,m)=1ならばa^φ(m)≡1(mod m).

定理１２の証明　x_1,…,x_φ(m)が法mに関する既約剰余系とする.
補題Ｆによってax_1,…,ax_φ(m)もそうである.
したがって,ax_1≡x_σ(1)(mod m),…,ax_φ(m)=x_σ(φ(m))(mod m)となる
{1,…,φ(m)}から自身への全単射σが存在する.
>>119よりa^φ(m)x_1…x_φ(m)≡x_σ(1)…x_σ(φ(m))(mod m)
右辺はx_1…x_φ(m)と一致するので
a^φ(m)x_1…x_φ(m)≡x_1…x_φ(m)(mod m).
再び定理４系(>>76)によって(x_1…x_φ(m),m)=1.
一章六節問題２(>>125)よりa^φ(m)≡1(mod m).■
149：Мечислав(☆9) （DTxrDxh6）：2005/02/24(木) 22:01:27: 定理１０(>>141)より次の,フェルマの小定理とよばれる系が成り立ちます.

系(フェルマ)　pが素数で(a,p)=1であるならa^(p-1)≡1(mod p).

オイラーの定理,フェルマーの小定理が成り立つことを,実例で確かめましょう.

(13,30)=(13,2･3･5)=1,φ(30)=φ(2)φ(3)φ(5)=1･2･4=8.
13^φ(30)=13^8=169^4=(5･30+19)^4≡19^4=361^2=(12･30+1)^2≡1(mod 30).

(8,11)=(2^3,11)=1,
8^10=64^5=(5･11+9)^5≡9^5≡(-2)^5≡-32≡1(mod 11).

フェルマの小定理のステートメントは「pが素数ならばa^p≡a(mod p)」でも
いいですね.p|aであったらもちろんa^p≡a(mod p)だから,仮定の(a,p)=1を消すことが
可能ってわけです.
150：Мечислав(☆9) （DTxrDxh6）：2005/02/24(木) 22:01:49: 一章九節の問題
１.　一章六節の問題８(>>125)を用いてフェルマの小定理を証明せよ.
２.　フェルマの小定理からオイラーの定理を導け.
３.　m>1,(a,m)=1とする.合同式ax≡b(mod m)の解はx≡ba^(φ(m)-1)(mod m)で与えられる.
151：AM：2005/03/02(水) 11:18:29: 代数系入門再開します。
もういちど初めからノートとって演習問題をこなしていこうと思います。
152：AM：2005/03/03(木) 21:38:43: 第一章§１読了

疑問
>>6の問題１における「どんな集合Xに対してもΦ⊂Xが成り立つ」ことに関して
「S⊂T」を「Sの元が皆Tの元であること(>>2)」と定めた場合、
「元を一つも持たない特殊な集合Φ(>>3)」に関して
「Φ⊂X」とはどういう意味なのか？

回答待ちで§２へ移行。
153：Мечислав(☆9) （DTxrDxh6）：2005/03/03(木) 21:57:02: >>152
えと
一般的に,
命題「p⇒q」はpが偽であれば,真です.

詳しくは集合位相スレにあるはずです。
リンク先は後でかきます。今移動車中なので。
154：AM：2005/03/03(木) 23:04:39: >>153
　　「Ｓが要素を持っていてかつそれらが全て集合Ｔの元(=p)」⇒「Ｓ⊂Ｔ」
なので
　　「Ｓが要素を持っていない(pが偽である)」⇒「Ｓ⊂Ｔ」は真
ということですか？
155：Мечислав(☆9) （DTxrDxh6）：2005/03/03(木) 23:45:46: >>154
Φ⊂X
と
x∈Φ⇒x∈X
は,論理的に同等で(包含関係の定義だから)
x∈Φは偽だから
x∈Φ⇒x∈X
は真,したがってΦ⊂Xは真です.

まだ移動中。
156：Мечислав(☆9) （DTxrDxh6）：2005/03/04(金) 00:20:34: >>AM
「集合・位相入門」輪読会
http://jbbs.livedoor.jp/bbs/read.cgi/study/4125/1078049875/18
参照です。
157：AM：2005/03/04(金) 21:20:56: >>155-156
ありがとうございます、理解できました。
＞命題「p⇒q」はpが偽であれば,真です
を知りませんでした。
159：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:56:08: 第二章　群
§１　写像
S,S'を集合とする.
Sの各元にS'の1つの元を対応させる対応のことをSからS'への写像という.
fがSからS'への写像であることをf:S→S'と書く.
このときSをfの定義域,S'をfの終集合という.
始集合という用語もある.S~を集合,SをS~の部分集合とし,
SからS'への写像を考えるとき,S~を始集合,Sを定義域とするのである.
定義域,S'をfの終集合という.
fをSからS'への写像とする.
fによってSの元xが対応するS'の元をxにおけるfの値またはfによるxの像と呼びf(x)と書く.
写像fによるxの像がf(x)であることはx|→f(x)と書く.
160：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:56:48: 例１　Nの各元nにそれぞれ2n∈Nを対応させれば,
この対応はNからNへのひとつの写像となる.

例２　正の整数nに対してnの約数の個数τ(n)を対応させる整数論的関数τ(c.f.>>106),
約数の総和σ(n)を対応させる整数論的関数σ(c.f.>>107),
nと互いに素なn以下の正の整数の個数φ(n)を対応させるEuler関数φ(これも整数論的関数c.f.>>140)
は皆Z^+からZ^+への写像である.
素数の平包因子を持つ場合μ(n)=0,n=p_1p_2…p_kと標準分解できる場合,
μ(n)=(-1)^kを対応させるM"obius関数はZ^+からZへの写像である.

例３　Rを実数全体の集合とする.
Rのある部分集合からRへの写像は実変数の実数値関数である.
Sを集合とする.SからRへの写像をS上で定義された実数値関数という.
Cを複素数全体の集合とする.
Cのある部分集合からCへの写像は複素変数の複素数値関数である.
Sを集合とする.SからCへの写像をS上で定義された複素数値関数という.
161：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:57:14: 例４　S,S'を集合,bをS'の元とする.
Sの任意の元にbを対応させる写像,
即ちSの任意の元xに対してx|→bで定めたSからS'への写像をSからS'への値bの定値写像という.

例５　加法
　　　　　　　　　　R×R∋(a,b)|→a+b∈R
はR×RからRへの写像である.
乗法
　　　　　　　　　　R×R∋(a,b)|→ab∈Rも
R×RからRへの写像である.
Sを集合とする.S×SからSへの写像をSにおける二項演算,S上の二項算法などという.

S,S'を集合,fをSからS'への写像とする.
Sの元x,yに対し,x≠yならばf(x)≠f(y)であるときfをSからS'への一対一対応の写像,
SからS'への単射などという.
162：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:57:39: UをSの部分集合とする.
　　　　　　　　　　f(U):={x'|f(x)=x'となるUの元xが存在する}={f(x)|x∈ U}
をUのfによる像という.
f(S)を単にfの像という.

f(S)=S'のときfをSからS'の上への写像,SからS'への全射などという.
fがSからS'への全射かつ単射であるとき,fをSからS'への全単射という.

fがSからS'への全単射であるならS'の各元x'に対してf(x)=x'となるSの元xがただ1つ存在する.
実際,fは全射であるならS'の元x'に対してf(x)=x'となるSの元xは存在するし,
もしx'=f(x)=f(y),y∈ Sであるならfが単射であることからx=yが言えるからである.

例６　Sを集合とする.
Sの各元xにx自身を対応させる写像
　　　　　　　　　　I:S∋x|→x∈S
は,すべてのSの元xに対してI(x)=xなるSの元xがあるから全射であり,
I(x)=I(y)ならばx=yであるから単射である.
即ちIはSからS自身への全単射である.
IをSの恒等写像といい,I_SとかId_Sと書いたりする.
163：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:58:01: 例７　Sを集合,S'をSの部分集合とする.S'の各元xをx自身に対応させる写像
　　　　　　　　　　f:S'∋x|→x∈S
は,f(x)=f(y)ならばx=yなので単射である.
これをS'からSへの自然な単射という.
164：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:58:26: 例８　RからRへの写像f_i,(i=1,2,3,4)と
R':={x|x∈R,x≧0}からRへの写像f_5を次のように定める.
　　　　　　　　　　f_1:R∋x|→x+1∈R
　　　　　　　　　　f_2:R∋x|→x^3-x∈R
　　　　　　　　　　f_3:R∋x|→2^x∈R
　　　　　　　　　　f_4:R∋x|→x^2∈R
　　　　　　　　　　f_5:R∋x|→x^2∈R'
165：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 05:58:46: x∈Rに対してf_1(x-1)=x,x-1∈Rであるからf_1は全射,
f_1(x)=f_1(y)ならばx+1=y+1となるのでx=yとなりf_1は単射.よってf_1は全単射.

f_2'(x)=3x^2-1=3(x-(1/√3))(x+(1/√3)),f_2(0)=0,
f_2((1/√3))=(1/3√3)-(1/√3)=-2/3√3,lim[x→∞]f_2(x)=∞,f_2(x)は連続.f_2(-x)=-f_2(x).
以上よりf_2は全射.
f_2(0)=f_2(1)よりf_2は単射ではない.

f_3(x)=-1を満たすxはないのでf_3は全射ではない.
f_3(x)=f_3(y)ならば2^x=2^y即ちx=yとなるのでf_3は単射.

f_4(x)=-1を満たすxはないのでf_3は全射ではない.
f_4(-1)=f_4(1)よりf_4は単射ではない.

R'の各元xに対してf_5(√{x})=x,√{x}∈Rであるのでf_5は全射.
166：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:00:28: Sを有限集合とする.
fがSからSへの単射であるならfは全射でもある.
実際,S={x_1,…,x_n}であるとするとi≠jならf(x_i)≠f(x_j)であるので
集合{f(x_1),…,f(x_n)}の元の個数はSの元の個数と一致する.
即ちf(S)はn個の元からなるSの部分集合であるからSそのものと一致する.
167：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:00:44: S,S'を集合,fをSからS'への全単射とする.
このとき,
S'の各元x'にはf(x)=x'となるSの元xがただ1つあるが,
このx'にxを対応させる対応
　　　　　　　　　　S'∋x'|→x∈S
はS'からSへの写像となる.
この写像をfの逆写像といいf^(-1)と書く.
f^(-1)も全単射である.
実際,Sの各元xに対してf(x)はS'の元であるのでSの元f^(-1)(f(x))があるが,
f^(-1)の決め方によりf^(-1)(f(x))=xである.したがってf^(-1)は全射.
また,f^(-1)(x')=f^(-1)(y')であるとすると,
f(x)=x',f(y)=y'を満たすSの元x,yがあって,
x=f^(-1)(x'),y=f^(-1)(y)であるので,
x=yである.よってx'=f(x)=f(y)=y'となりf^(-1)は単射となる.
168：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:02:00: 例９　R^+を正の実数全体の集合とする.
RからR^+への写像fを
f(x)=2^xと定めると,fはRからR^+への全単射となり,
f^(-1):R^+→Rは対数関数x|→log_2xである.
実際,R^+の各元xに対してRの元log_2xがあって,
f(log_2x)=2^(log_2x)=xとなるのでfは全射,
またf(x)=f(y)なら2^x=2^yとなりx=yとなるのでfは単射となる.
fは単射であるので先のlog_2xについて,f^(-1)(x)=log_2xとなる.
詳しくは解析学の成果を用いねばならない.
169：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:03:41: S,S'を集合,fをSからS'への写像とする.
S'の各元x'に対して
f^(-1)(x'):={x|x∈S,f(x)=x'}をx'のfによる逆像という.
￢(x'∈f(S))ならf^(-1)(x')=Φである.
U'がS'の部分集合であるとき,f^(-1)(U'):={x|x∈S,f(x)∈U'}をfによるU'の逆像という.
この意味でのf^(-1)は2^{S'}:={B|B⊂S'}から2^S:={A|A⊂S}への写像と見ることができる.

f:S→S'を写像とし,U⊂Sとする.
このとき対応U∋x|→f(x)∈S'は写像であるが,
この写像をfのUへの制限といい,f|Uと書く.
f:S→S',f_1:S_1→S_1'を写像,Ssubset S_1,S'subset S_1'とする.
Sの任意の元xに対してf(x)=f_1(x)であるときf_1はfのS_1への拡大であるという.
170：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:06:28: f:R→S,g:S→Tを写像とする.
対応R∋x|→g(f(x))∈Tは写像であるが,
これをfとgの合成写像といいg○fと書く.

例１０　f:R→R,g:R→Rをそれぞれ,
f(x)=x^2,g(x)=x+1とすると,(g○f)(x)=x^2+1,(f○g)(x)=(x+1)^2.

補題１
(1) f:R→S,g:S→Tがともに単射であればg○f:R→Tも単射である.
(2) f:R→S,g:S→Tがともに全射であればg○f:R→Tも全射である.

証明.
(1)　(g○f)(x)=(g○f)(y)であるとするとg(f(x))=g(f(y)).
gが単射であるからf(x)=f(y).fが単射であるからx=y.
(2)　zをTの任意の元とするとgが全射であることによりg(y)=zなるSの元yが存在する.
このときfが全射であることによりf(x)=yとなるRの元が存在する.このとき
(g○f)(x)=g(f(x))=g(y)=z.■
171：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:08:09: 補題２　f:R→S,g:S→T,h:T→Uを写像とすると,
h○(g○f)=(h○g)○f.

証明.　h○(g○f)も(h○g)○fもRからUへの写像であり,
Rの任意の元xに対して
(h○(g○f))(x)=h((g○f)(x))=h(g(f(x))),
((h○g)○f)(x)=(h○g)(f(x))=h(g(f(x))).■

f:S→S'を写像とするとf○I_S=f,I_{S'}○f=fである.
実際,f○I_SもI_{S'}○fもSからS'への写像であり,
任意のSの元xに対して,
　　　　　　　　　　(f○I_S)(x)=f(I_S(x))=f(x),(I_{S'}○f)(x)=I_{S'}(f(x))=f(x).
またfが全単射のときはf○f^(-1)=I_{S'},f^(-1)○f=I_Sである.
実際,f○f^(-1)はS'からS'への写像であり,
任意のS'の元x'に対して
　　　　　　　　　　(f○f^(-1))(x')=f(f^(-1)(x'))=x',
f^(-1)○fはSからSへの写像であり,
任意のSの元xに対して
　　　　　　　　　　(f^(-1)○f)(x)=f^(-1)(f(x))=x.
172：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:09:11: 補題３　f:S→S'を写像とする.
g○f=I_Sかつf○g=I_S'をみたすS'からSへの写像gが存在するなら
fは全単射でありg=f^(-1)である.

証明.　f(x)=f(y)であるとするとg○f=I_Sよりx=yとなるのでfは単射.
f○g=I_S'よりS'の各元x'に対してf(g(x'))=x'でありg(x')はSの元であるのでfは全射である.
補題２よりf^(-1)=I_S○f^(-1)=(g○f)○f^(-1)=g○(f○f^(-1))=g○I_{S'}=g.■
173：Мечислав(☆12) ◆QRDTxrDxh6：2007/05/31(木) 06:12:56: 二章一節の問題
１．f:S→S'を写像とする.次のことを示せ.
(a) U⊂S,W⊂Sならば
　　　　　　　　　　f(U∪W)=f(U)∪f(W),
　　　　　　　　　　f(U∩W)⊂f(U)∩f(W),
fが単射ならば等号が成立する.

(b) U'⊂S',W'⊂S'ならば
　　　　　　　　　　f^(-1)(U'∪W')=f^(-1)(U')∪f^(-1)(W'),
　　　　　　　　　　f^(-1)(U'∩W')=f^(-1)(U')∩f^(-1)(W').

(c) U⊂Sならば
　　　　　　　　　　f^(-1)(f(U))⊃U.
fが単射ならば等号が成立する.
(d) U'⊂S'ならば
　　　　　　　　　　f(f^(-1)(U'))⊂U'.
fが全射ならば等号が成立する.
174：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 03:53:41: §２　群とその例
Gを空でない集合とする.Gに1つの2項算法が与えられたとする.
この2項算法による(a,b)の像をa*bと書くことにする.
この算法が次の3つの条件を満たすとき,Gと*のペアを群という.

G1　すべてのGの元a,b,cに対して,
　　　　　　　　　　(a*b)*c=a*(b*c).
が成り立つ.
G2　すべてのGの元aに対して,aに無関係なGの元eで次の条件を満たすものが存在する.
　　　　　　　　　　e*a=a*e=a.
G3　すべてのGの元aに対して,
　　　　　　　　　　a*b=b*a=e
をみたすGの元bが存在する.
175：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 03:54:33: Gと*の組(G,*)を群というのだが,特に必要がなければ群Gと言ったりもする.
群の算法を表す記号は加法の記号a+bや乗法の記号a*bあるいはabを用いる.
乗法記号を用いるとき乗法群,加法記号を用いるとき加法群といったりする.
以下一般論では,記号を簡単にするため乗法群を用いる.
G2におけるeをGの単位元と言う.eの代わりに1と書いたりもする.
G3におけるbをaの逆元という.
単位元は1つしかない.実際eもe'も単位元であるとすると,e=ee'=e.
aの逆元は各aに対して1つしかない.実際bもcもaの逆元であるとすると,
b=be=b(ac)=(ba)c=ec=c.
aの逆元をa^{-1}と書く.
aa^{-1}=a^{-1}a=eであるから(a^{-1})^{-1}=aである.
加法群においては,単位元を0,aの逆元を-aと書く.
習慣として加法群においては,その算法が交換律を満たすものとする.
即ちa,bをの加法群Gの任意の元であるとするとa+b=b+aが成り立つものとする.
一般に乗法群において,ab=baが満たされるときaとbは可換であるという.
Gの任意の2元が可換であるときGを可換群またはAbel群という.
176：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 03:57:23: 例１１　Z,Q,R,Cはそれぞれ普通の加法に関して可換群である.
証明　a∈Z,b∈Zならばa+b∈Z,
a∈Q,b∈Zならばa+b∈Q,
a∈R,b∈Zならばa+b∈R,
a∈C,b∈Zならばa+b∈C.
Cは加法についてG1を満たす.
Cの元0は加法の単位元である.0∈Z⊂Q⊂R⊂C.
a∈Cに対して-aは逆元である.
a∈Zならば-a∈Zであり,
a∈Qならば-a∈Qであり,
a∈Rならば-a∈Rであり,
a∈Cならば-a∈Cである.
Cの任意の2元はCの加法について可換である.■
177：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 03:59:20: 例１２　Q^*:=Q-{0},R^*:=R-{0},C^*:=C-{0}
はそれぞれ普通の乗法に関して可換群をなす.
Q,R,Cは乗法に関して群をなさない.
証明　a∈Q,b∈Zならばab∈Q,
a∈R,b∈Zならばab∈R,
a∈C,b∈Zならばab∈C.
Cは乗法についてG1を満たす.
Cの元1は乗法の単位元である.
1∈Q⊂R⊂C.
a∈C^*に対して1/aは逆元である.
Cの任意の2元はCの乗法について可換である.
a∈Qならば(1/a)∈Qであり,
a∈Rならば(1/a)∈Rであり,
a∈Cならば(1/a)∈Cである.
0∈Q⊂R⊂Cの逆元があるとし,
bとすると0b=b0=1.このようなCの元bは存在しない.■
178：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 04:01:56: 例１３　a∈R,b∈Rとする.
複素数α:=a+ibに対し,その絶対値を
　　　　　　　　　　|α|:=√(a^2+b^2)
で定義する.
T:={α∈C;|α|=1}は乗法に関して可換群をなす.
証明　a_1∈R,a_2∈R,b_1∈R,b_2∈R,α_1=a_1+ib_1∈ T,α_2=a_2+ib_2∈ Tとすると,
　　　　　　　　　　|α_1α_2|
　　　　　　　　　　=|(a_1a_2-b_1b_2)+i(a_1b_2+b_1a_2)|
　　　　　　　　　　=√((a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2)
　　　　　　　　　　=√(a_1^2a_2^2+b_1^2b_2^2+a_1^2b_2^2+b_1^2a_2^2)
　　　　　　　　　　=√(a_1^2(a_2^2+b_2^2)+b_1^2(a_2^2+b_2^2))
　　　　　　　　　　=√((a_1^2+b_1^2)(a_2^2+b_2^2))
　　　　　　　　　　=1
となるので乗法はTにおける算法である.
Tの乗法はCの乗法であるので結合律を満たす.即ちTはG1を満たす.
|1|=|1+i0|=√(1^2+0^2)=1より1∈Tであるので,1はTの単位元である.即ちTはG2を満たす.
α_1=a_1+ib_1∈ Tに対して,
1/α_1=a_1-ib_1∈T.TはG3を満たす.
また,Tの乗法はCの乗法であるのでTの任意の2元は可換である.■
179：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 04:02:43: 例１４　{1,-1}は乗法について可換群をなす.
証明　1*1=(-1)*(-1)=1,1*(-1)=(-1)*1=-1となるので乗法は{1,-1}における算法である.
{1,-1}の乗法はCの乗法であるので結合律を満たす.即ち{1,-1}はG1を満たす.
1∈{1,-1}であるので,1は{1,-1}の単位元である.即ち{1,-1}はG2を満たす.
1^{-1}=1,(-1)^{-1}=-1であるので{1,-1}はG3を満たす.
また,{1,-1}の乗法はCの乗法であるので{1,-1}の任意の2元は可換である.■
180：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 04:03:34: 例１５　集合{e}はee=eと算法を定めれば可換群をなす.
証明　(ee)e=ee=e,e(ee)=ee=eより{e}はG1を満たす.
ee=ee=eよりeは{e}の単位元である.よって{e}はG2を満たす.
e^{-1}=e.{e}はG3を満たす.
ee=eeより{e}の任意の2元は可換である.■
例１５の{e}を単位群という.
181：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 04:06:10: 有限個の元からなる群を有限群という.有限群の元の個数をその群の位数という.
例１６　Xを空でない集合とする.
GをXからXへの全単射全体の集合とすると,
Gは写像の合成に関して群をなす.また,
Xが3元以上からなるならGは非可換.
証明　補題１(>>170)より写像の合成はGの算法である.
補題２(>>171)よりGはG1を満たす.
I_XはGの単位元である.よってGはG2を満たす.
f∈Gの逆元はf^(-1)∈Gである.よってGはG3を満たす.
{a,b,c}⊂ Xとする.
f∈Gを
　　　　　　　　　　f(a)=b,f(b)=c,f(c)=a,￢(x∈{a,b,c})ならばf(x)=x,
g∈Gを
　　　　　　　　　　g(a)=c,g(c)=a,￢(x∈{a,c})ならばf(x)=x
とすると,
(g○f)(a)=b,(f○g)(a)=aとなるのでこの群は非可換である.■
182：Мечислав(☆12) ◆QRDTxrDxh6：2007/06/15(金) 04:08:02: 例１５のGを集合X上の対称群といいS(X)と書く.
S(X)の元を置換という.
Xがn元からなる集合のときS(X)をS_nと書き,
n次対称群という.
S_nは有限群で,その位数はn!である.実際,X={1,2,…,n}とすると,
X上の置換は例えば
　　　　　　　　　　(1,2,…,n),(4,7,2,1,…)
などと表される.左の置換はI_Xを,右の置換はσ(1)=4,σ(2)=7,σ(3)=2,σ(4)=1,…となるS_nの元σを,それぞれ表すものとする.
即ちS_nの位数は,異なるn個のものを1列に並べる順列n!に等しい.
183：はじめまして：2010/07/15(木) 09:55:21: １１４の（3）の答えってどうなるか教えてくださいー（＞_＜。）