合同式の問題

質問

aを
1<= a <= 10 の任意の整数として、

a^30 = 1 (mod 11)

をどのように示すのかよく分かりません。
よろしくお願いします。

回答No.2

ka1234 · ベストアンサー

こんにちは。

必要な事項を証明しておきます。

[フェルマーの小定理]
a と p が互いに素の時、a^(p-1)≡1 (mod p) が成り立つ。

[証明] 　集合A {1, 2, 3, ・・・, p-1} は、
mod p で、集合B {a×1, a×2, a×3,・・・, a×(p-1)}と一致する。→[補題]
∴(a×1)(a×2)(a×3)・・・{a×(p-1)}≡1×2×3・・・(p-1) (mod p)
⇔a^(p-1)×(p-1)！≡(p-1)！ (mod p)

(p-1)！は p と互いに素であるから、
⇔a^(p-1)≡1 (mod p)　（証明終わり）

[補題] 集合B の任意の異なる２つの元 a×i, a×j (1≦i＜j≦p-1)
に対して、1≦j-i≦p-2 であるから、a(j-i) は p で割り切れない。
（∵a と p は互いに素）
よって、a(j-i)≠0 (mod p) （≠は「合同ではない」のつもり）
　　　　∴aj≠ai (mod p)
よって、集合Bは mod p で同じものを含まないので、集合Aと一致する。
（証明終わり）

さて、フェルマーの小定理より、11と互いに素なaに対して
a^(11-1)≡1 (mod 11) が成り立ちます。両辺を３乗して、
a^30≡1 (mod 11)
a=1～10 は 11 と互いに素であるから、
a^30≡1 (mod 11)　となる。（証明終わり）

お礼

詳しい解説ありがとうございます。
なんとか理解できました。
＃読んでいる本のかなり後ろにこの定理が載っていましたが
＃多少読んでみましたが、証明がよくわからないです
＃（読み進めてないので当然なのですが）

とても助かりました。ありがとうございました。

回答No.3

koko_u_

Fermat の小定理だけならもっと単純で、

a^p = (1 + 1 + … + 1)^p (1 を a 回足す)を多項展開すると 1^{s_1}・1^{s_2}… 1^{s_a} の係数は p！/(s_1！・s_2！…s_a！)　( s_1 + s_2 + … + s_a = p )

p は素数だから、s_1 < p, s_2 < p, ... s_a < p の場合は係数は p で割り切れる。

すなわち、s_1 = p, s_2 = 1, ... s_a = 1 のような a 個の係数だけが生き残って

a^p ≡ a mod p

特に (a, p) = 1 であれば a^(p-1) ≡ 1 mod p

ただし、これはオイラーの定理には適用が困難。

お礼

あぁ、こんな風にも解けるんですね。
目から鱗です。
物理のために群論をやりたいのですが、
その手前で苦闘している状態です(^^;
どうもありがとうございました。

回答No.1

koko_u_

Fermat の小定理を使っていいなら一瞬ですが。

お礼

ありがとうございます。
Fermatの小定理は読んでいる本のかなり後ろに出ていました。orz