24/07/22 00:44:46.61 F+OPO1w3.net
一般に次が成り立つ。
(p, q)=1の時、
Z/pqZ≅(Z/pZ)×(Z/qZ)
φ: Z/pqZ→(Z/pZ)×(Z/qZ)を上に定めた記号を用いて
φ: αpq→(αp, αq)、α∈Z、
とする。
φが全単射であることは後で証明する。
φ(ab)=φ(a)φ(b)が成り立つことを証明する。
∀α, β∈Z2対して
φ(αpq+βpq)=φ((α+β)pq)
=((α+p, (α+β)q))
φ(αpq)+φ(βpq)=(αp, αq)+(βp, βq)
=(αp+βp, αq+αq)=((α+β)p, (α+β)q)
よってφ(ab)=φ(a)φ(b)が成り立つ。演算と写像の順序交換。
1075:１３２人目の素数さん
24/07/22 01:11:48.52 F+OPO1w3.net
定理1・6 中国剰余定理の証明
0～pq-1までのpq個の集合Sの中で考える
A, B∈S、A≠BであるA, Bが題意を満たすとして矛盾を導く
p|(A-B)、q|(A-B)、(p, q)=1より
pq|(A-B)
ここで0≤|A-B|≤pq-1よりA-B=0、A=B。よって2個以上は存在しない。0個または1個である。
これにより
φ: Z/pqZ→(Z/pZ)×(Z/qZ)が単射であることが証明された。つまりダブり無し
|Z/pqZ|=pq個である。
同様に|Z/pZ|=p個、|Z/qZ|=q個であるから全射である。対応なしがない。
これでφが全単射であることが証明された。証明終
φ: A→Bが
全射⇒|A|≥|B|
単射⇒|A|≤|B
全単射⇒|A|=|B||
1076:１３２人目の素数さん
24/07/22 01:49:02.01 F+OPO1w3.net
問1・8
3、1
5、2
7、3
百五減算というそうです
マジックナンバー15、70、21
70+15×3+21×2=157≡52
Z/105Z≅(Z/3Z)×(Z/5Z)×(Z/7Z)
この同型がポイントですね
マジックナンバーは
(1, 0, 0)→70、
(0, 1, 0)→21、
(0, 0, 1)→15となる
(1, 2, 3)→70+42+45=157≡52
1077:１３２人目の素数さん
24/07/22 02:10:43.90 F+OPO1w3.net
定理1・7 中国剰余定理の証明
x≡a mod p、x≡b mod q、x≡c mod r、p, q, rは対毎に互いに素とする
マジックナンバーを作る
qrs≡1 mod p、prt≡1 mod q、
pqu≡1 mod r
pv+(qr)s=1、ここで(p, qr)=1より
解(s0, v0)∈Z×Zを持つ。
同様にt0, u0という解も持つ。
これらがマジックナンバーであり
答えは(apqs+bprt+cpqu)105
が存在する
一意性の証明
x, y、x≠yとすると3通りの余りが全て等しいから
x-yはp、q、rの全てで割り切れる。それぞれが他と互いに素であるから積pqr
1078:で割り切れる。 0≤|x-y|≤pqr-1よりx-y=0、x=y 従って2個以上は存在しない 一意性が証明された。
1079:１３２人目の素数さん
24/07/22 02:32:30.05 F+OPO1w3.net
p, q, rが対毎に互いに素ならば
Z/pqrZ≅(Z/pZ)×(Z/qZ)×(Z/rZ)
であることの証明
α, β∈Zとする。
φ: Z/pqrZ→(Z/pZ)×(Z/qZ)×(Z/rZ)をαpqr→(αp, αq, αr)で定義すると
p, q, rが全て一致しない限り同じ点にはうつらないので単射である
また|Z/pqrZ|=pqr個であり
|Z/pZ|×|Z/qZ|×|Z/rZ|=pqrであるから|A|<|B|とは成り得ず、全射でもある。よってφは全単射である。
Aはpqr個、Bは最大でもpqr個、φは単射なので等号が成立するしかない。
単射の条件は|B|≥pqr、
分解による条件は|B|≤pqr
よって|B|=pqrとなる。
φ(αpqr+βpqr)=φ((α+β)pqr)
=((α+β)p, (α+β)q、(α+β)r)
φ(αpqr)+φ(βpqr)=
(αp, αq, αr)+(βp, βq, βr)
=(αp+βp, …)
=((α+β)p, …)
よって演算と写像の交換が成り立つ。φが同型写像であることが証明された。よって同型である(証明終)
1080:１３２人目の素数さん
24/07/22 02:36:48.02 F+OPO1w3.net
1-6節は直積です
中国剰余定理、同型、同型写像、など。繰り返しが多く分かりやすいですね。
1081:１３２人目の素数さん
24/07/22 02:40:52.71 F+OPO1w3.net
百五減算は面白いですね
x≡1 mod3
x≡2 mod5
x≡3 mod7
マジックナンバーは
70、21、15
x≡70+42+45=157≡52 mod 105
1082:１３２人目の素数さん
24/07/22 02:47:20.98 F+OPO1w3.net
p, q, rが素数でなくても対毎に互いに素ならば分けられるので
Z/(2^3×3^4×5^2)Z≅
(Z/8Z)×(Z/81Z)×(Z/25Z)です。
1083:1001
Over 1000 Thread Thread.net
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 23日 16時間 24分 21秒
1084:過去ログ ★
[過去ログ]
■ このスレッドは過去ログ倉庫に格納されています