[過去ﾛｸﾞ] (･ω･)俺が日々の数学的発見を書くスレ (139ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
102(1): ◆uxQt4Y4ywU 2019/08/26(月)14:41 ID:EGcR6R12(1/10) AAS
[補題]
素数p、整数a,bに対して
(a+b)^p≡a^p+b^p mod p が成り立つ。
103: ◆uxQt4Y4ywU 2019/08/26(月)14:41 ID:EGcR6R12(2/10) AAS
[証明]
補題>>96に注意して、
(a+b)^p
=(a^p+b^p)+Σ[k=1→p-1]pCk*a^k*b^(p-k)
≡a^p+b^p mod p//
104(1): ◆uxQt4Y4ywU 2019/08/26(月)14:41 ID:EGcR6R12(3/10) AAS
[系]
a[k]∈Z(k∈N)に対して、
(Σa[k])^p≡Σ(a[k]^p) mod p が成り立つ。
105: ◆uxQt4Y4ywU 2019/08/26(月)14:42 ID:EGcR6R12(4/10) AAS
[証明]
補題>>102より、
(a[1]+a[2])^p≡a[1]^p+a[2]^p mod p
である。ここで、
(Σ[k=1→n]a[k])^p≡Σ[k=1→n](a[k]^p) mod p
が成り立つと仮定する(n∈N)。このとき、
(Σ[k=1→n+1]a[k])^p
≡(Σ[k=1→n]a[k])^p+a[n+1]^p
≡Σ[k=1→n](a[k]^p)+a[n+1]^p
=Σ[k=1→n+1](a[k]^p) mod p
省1
106: ◆uxQt4Y4ywU 2019/08/26(月)14:43 ID:EGcR6R12(5/10) AAS
[定理](フェルマーの小定理)
素数pとa⊥pなるa∈Zに対して、
a^(p-1)≡1 mod p が成り立つ。
107: ◆uxQt4Y4ywU 2019/08/26(月)14:44 ID:EGcR6R12(6/10) AAS
[証明1]
オイラーの定理から、a^φ(p)≡1 mod p であり、
φ(p)=p-1なので示された。//
108: ◆uxQt4Y4ywU 2019/08/26(月)14:44 ID:EGcR6R12(7/10) AAS
[証明2]
a≡1 mod pのとき主張の成立は明らか。
a≡k mod pで主張が成り立つと仮定する。
(ただし k∈Z,1≦k≦p-2 である)
このとき、仮定と補題>>96より
(k+1)^p=Σ[i=0→p]pCi*k^i≡k^p+1≡k+1 mod p
であり、p⊥(k+1)なので (k+1)^(p-1)≡1 mod p
よってa≡k+1 mod pでも主張は成り立つ。
以上から示された。//
109: ◆uxQt4Y4ywU 2019/08/26(月)14:44 ID:EGcR6R12(8/10) AAS
[証明3]
p=2のとき、a≡1 mod pなので主張は成り立つ。
pが奇素数のとき、a^(p-1)>0よりa∈Nとしてよい。
よって、系>>104より
a^p=(Σ[k=1→a]1)^p≡Σ[k=1→a](1^p)=a mod p
したがって、a⊥pよりa^(p-1)≡1 mod pとなる。//
110(1): ◆uxQt4Y4ywU 2019/08/26(月)14:45 ID:EGcR6R12(9/10) AAS
[定理](位数)
a,m∈Z(a⊥m)に対して、
a^n≡1 mod mとなる最小の正の整数nをdとすると、
a^x≡1 mod mとなるx∈Zはdの倍数となる。
(ちなみにdは法mにおけるaの位数と呼ばれる)
111: ◆uxQt4Y4ywU 2019/08/26(月)14:45 ID:EGcR6R12(10/10) AAS
[証明]
以下法をmとする。
dの倍数でないxの値x'が存在したとすると、
x'=dq+r(q,r∈Z,0<r<d)とおける。
このとき、a^x'≡1 より、
a^(dq+r)≡1 ∴ (a^d)^q*a^r≡1 ∴ a^r≡1
となるが、これはdの最小性に矛盾している。
したがって示された。//
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.105s*