１）4で割って3余る素数が無限にあることを示せ．

１）4で割って3余る素数が無限にあることを示せ．
２）オイラー関数φ(n)について，以下を証明せよ．
(1) pが素数のときφ(p^r )=p^r-p^(r-1).
(2) ｍとｎが互いに素ならばφ(ｍｎ)=φ(ｍ)φ(ｎ)．
(3) 自然数ｎに対し，φ(ｎ)=ｎ?_(p|n) (1-1/p) (積はｎを割る素数をわたる)．

No.1 ベストアンサー 回答者： yoikagari 回答日時： 2010/06/08 02:58

1)

以下回答では合同式を用いる。
意味がわからなければ下記サイトを参考にしてほしい
http://www2.ocn.ne.jp/~atel.a/emath/mod.html

4n+3の形の素数がp_1，p_2，…，p_mのm個のみと仮定する。…○

N=4(p_1)(p_2)…(p_m)-1とおく。

N=4(p_1)(p_2)…(p_m)-1=(p_1){4(p_2)…(p_m)-1}+p_1 -1となるから、
Nはp_1で割り切れない。
N=4(p_1)(p_2)…(p_m)-1=(p_2){4(p_1)(p_3)…(p_m)-1}+p_2 -1となるから、
Nはp_2で割り切れない。
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
N=4(p_1)(p_2)…(p_m)-1=(p_m){4(p_1)…{p_(m-1)} -1 }+p_m -1となるから、
Nはp_mで割り切れない。
よってNはp_1，p_2，…，p_mのいずれでも割り切れない。…※

Nを素因数分解してみる。N=(q_1)…(q_k)
※よりq_1，q_2…，q_kはp_1，p_2，…，p_mのいずれとも異なる。…●

Nは2では割り切れないから、q_1,…,q_kのいずれも2ではない。

q_1,…,q_kのいずれも4で割ると1余る素数と仮定する。
N=(q_1)…(q_k)≡1*1…*1≡1 (mod 4)となるが、
N=4(p_1)(p_2)…(p_m)-1≡-1≡3 (mod 4)だから不合理
よって、q_1,…,q_kのいずれかは4で割ると3余る素数となる。
それをq_wとする。
●よりq_wはp_1，p_2，…，p_mのいずれとも異なっているが
4で割ると3余る素数すなわち4n+3の型の素数となるが
これは○の仮定に反する。

以上より○の仮定が誤りで、4n+3の形の素数の個数が無限にあること
がいえた。

2)
(1)
φ(p^r)=p^r-(1からp^rまでの整数のうちpの倍数の個数)=p^r-p^(r-1)

(2)
kをmより小さくmと互いに素な正の整数、hをnより小さくnと互いに素な正の整数とする。
「mh+nkはmnと互いに素になることがいえる。」・・・※

※の証明

もしmh+nkとmnをともに割り切る素数pが存在すると仮定する。
mh+nk=ps

mnが素数pで割り切れる。
pは素数だからm,nのいずれかがpで割り切れる。

nがpで割り切れるとき
n=pu
mh=ps-puk=p(s-tk)だからmhが素数pで割り切れる。
pは素数だからmまたはhがpで割り切れる。

mがpで割り切れるとき
m,nがともにpで割り切れるのでm,nが互いに素であることに
反し不合理

hがpで割り切れるとき
n,hがともにpで割り切れるのでn,hが互いに素であることに
反し不合理

※の証明ここまで

「mh+nk≡mh'+nk' (mod mn)ならばk≡k'(mod m)，h≡h'(mod n)」…○

○の証明
mh+nk=mh'+nk'+mnv
m(h-h')=n(mv-k+k')だからm(h-h')はnで割り切れる
m,nは互いに素だからh-h'はnで割り切れる
すなわち、h≡h'(mod n)がいえる。
n(k-k')=m(nv-h+h')だからn(k-k')はmで割り切れる。
m,nは互いに素だからk-k'はmで割り切れる。
すなわち、k≡k'(mod m)がいえる。
よって、k≡k'(mod m)，h≡h'(mod n)がいえる。

○の証明ここまで

※と○より
Z(m)をmod mの既約剰余類、Z(n)をmod nの既約剰余類、Z(mn)をmod mnの既約剰余類とする。

k∈Z(m)，h∈Z(n)をとる
f：Z(m)×Z(n)∋(k,h)→mh+nk∈Z(mn)
※よりmh+nkは確かにZ(mn)の元であることがいえる。
また○よりfは単射である。
よってφ(ｍ)φ(ｎ)≦φ(ｍn)がいえる。

またZ(mn)の元wをとる
wはmnと互いに素だから、wとm,wとnも互いに素である
g：Z(mn)∋w→(w,w)∈Z(m)×Z(n)
gは明らかに単射だからφ(ｍn)≦φ(ｍ)φ(ｎ)

以上よりφ(ｍn)=φ(ｍ)φ(ｎ)がいえた。

(3)
nを素因数分解すると、n=π_[p|n]p^kだから(1),(2)より
φ(n)=π_[p|n]φ(p^k)=π_[p|n]{p^k-p^(k-1)}=π_[p|n]p^k{1-(1/p)}
=π_[p|n]p^k*π_[p|n]{1-(1/p)}=nπ_[p|n]{1-(1/p)}となり
φ(n)=nπ_[p|n]{1-(1/p)}がいえた。

この回答へのお礼

どうもありがとう御座いました！

お礼日時：2010/06/09 00:33

No.2 回答者： B-juggler 回答日時： 2010/06/08 04:01

このレベルで丸投げは良くないけど・・・。

代数学かな？　講義ででてくることだと思うけどね・・・。

ちゃんと調べたりして理解できればね♪

丸呑みしちゃあダメですよ。

ちゃんと説明してくださっていますので、よく読んで

理解をしてくださいね。

「４で割って３余る素数は無限にある」

これは、シンプルに、自明でも構いません。

素数は必ず「４ｎ＋１」か「４ｎ－１」で表されることが分かっていれば。
　＃ｎは自然数ね。

後は２だけだけど、２は４で割って３余りはでないからね。

オイラー関数は、重要だけど、この辺は講義でやるはずだよ～。

私の講義ではほとんどあつかわないけれども（代数学の非常勤講師です）。

整数論が絡んでくるのかな？　どっちにしても大事なことだからね。

書かれてあることを理解するように、がんばってください。

ポイントは、私につけてはダメよ。Ｎｏ．１さんにあげてくださいね。

ちゃんと締め切るようにしてね　ｍ（＿　＿）ｍ

がんばってください。