No.7ベストアンサー
- 回答日時:
>これは順序が逆です。
>
>φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・を証明するために
>φ(ab)=φ(a)φ(b)が出て来て、φ(ab)=φ(a)φ(b)の証明が
>わからないのです。
まったく「学習の方法」が分かってないのですね.
証明が分からないというから
逆手にとって
証明対象が正しいと認めて
まずは具体例で考えてみなさいと
アドバイスされてるのが分からないのですか?
そもそも・・・既約剰余類を導入して
abの既約剰余類と,aの既約剰余類とbの既約剰余類の組が
1対1に対応するということを証明するだけなんだから
まずは具体的に
a=5,b=3とかで手を動かせばいいのです.
(1) 15の既約剰余類は 1,2,4,7,8,11,13,14
(2) 5の既約剰余類は 1,2,3,4
(3) 3の既約剰余類は 1,2
(2)と(3)のペア(m,n)と(1)の値 3m+5n を対応させる
(1,1) -> 8
(1,2) -> 13
(2,1) -> 11
(2,2) -> 16 -> 1
(3,1) -> 14
(3,2) -> 19 -> 4
(4,1) -> 17 -> 2
(4,2) -> 22 -> 7
逆に,(1)の値に対しては 3*2+5*(-1)=1(ユークリッドの互除法)を使って
1 -> (2,-1) -> (2,2)
2 -> (4,-2) -> (4,1)
4 -> (8,-4) -> (3,2)
7 -> (14,-7) -> (4,2)
8 -> (16,-8)-> (1,1)
11 -> (22,-11) -> (2,1)
13 -> (26,-13) -> (1,2)
14 -> (28,-14) -> (3,1)
この二つの対応は明らかに互いに逆写像になっているので
abの既約剰余類と,
aの既約剰余類とbの既約剰余類の組が
1対1に対応する
のが見えるのです.
これを一般的に書けば証明です.
はっきりいって
具体的に数字で書き下せば納得できるでしょう.
この手の初等整数論に限らず
数学で泥臭い手計算を避けるのは愚策以外の何物でもありません.
丁寧な回答ありがとうございます。
だいぶわかってきました。
> まずは具体例で考えてみなさいと
> アドバイスされてるのが分からないのですか?
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・,φ(ab)=φ(a)φ(b)に
数値を代入して成立するのはわかります。
わからなかったのは
・既約類、既約剰余系、既約代表の一組の概念の違い
・φ(a)、φ(b)の既約剰余系の「組」をφ(ab)の既約剰余系に対応させる
・φ(ab)→φ(a)、φ(b)に対応させるところ
でした。
No.6
- 回答日時:
n=ab で、a,b は互いに素とする。
互いに素なので、a,bを素因数分解するとき、共通の素因数は無い。
a の素因数分解を、ΠPi
b の素因数分解を、ΠQj
とすれば、
n=ab の素因数分解は n=ΠPi*ΠQj
となり、
オイラーの関数は
φ(n)=nΠ(1-1/pi)*Π(1-1/Qj)
=abΠ(1-1/pi)*Π(1-1/Qj)
=aΠ(1-1/pi)*bΠ(1-1/Qj)
=φ(a)φ(b)
となり、等式は成立する。
ポイントは、互いに素なので共通因数が無いので
素数をaからのものと、bからのものに分けることが出来る
ところです。
No.5
- 回答日時:
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・
の式で、
a=14=2*7
b=15=3*5
n=14*15=210
として、
φ(210)=210(1-1/2)(1-1/7)(1-1/3)(1-1/5)
と、
φ(14)=14(1-1/2)(1-1/7)
φ(15)=15(1-1/3)(1-1/5)
を比べてください。
これは順序が逆です。
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・を証明するために
φ(ab)=φ(a)φ(b)が出て来て、φ(ab)=φ(a)φ(b)の証明が
わからないのです。
No.4
- 回答日時:
>φ(ab)=φ(a)φ(b)の証明がわからなかったとしか
>いいようがないです
それではアドバイスのしようがありませんね。
どんな証明が書いてあって、最初に分からなかった箇所はどこですか?
合同の観念を応用して、φ(n)の意味を練れば、
簡単にφ(ab)=φ(a)φ(b)が解決するとあり、
既約類、既約剰余系を導入するんですが
これがよくわからないです。
次にay+bxを考察しφ(ab)とφ(a)などの既約代表を考えるのですが
これもよくわかりませんでした。
連立合同式を使う他の証明もあったのですが
お手上げです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
素数の性質
-
数学の「証明」のときなどの接...
-
婿養子です、妻と離婚して妻の...
-
(4^n)-1が3の倍数であることの...
-
婿養子に入ったのに出て行けと...
-
成人した後両親が離婚し別の人...
-
3,4,7,8を使って10を作る
-
中学校の2年生に仮定と結論を...
-
数学的帰納法の質問
-
証明終了の記号。
-
正解が一つとは限らない数学の...
-
σ集合体の証明
-
なぜ独身だと養子が持てないの...
-
親の再婚相手との問題です。私...
-
47歳、母親の再婚を子供の立場...
-
夫が亡くなった後の義理家族と...
-
素数の平方根は無理数である。
-
明治期の戸籍、養子につきまして
-
数学の証明問題で、「証明終了」...
-
大学の二次試験で・・・
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
数学の証明問題で、「証明終了」...
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
婿養子です、妻と離婚して妻の...
-
√2が無理数であることの証明で...
-
証明終了の記号。
-
素数の性質
-
婿養子に入ったのに出て行けと...
-
3,4,7,8を使って10を作る
-
無理数って二乗しても有理数に...
-
(4^n)-1が3の倍数であることの...
-
素数の積に1を加算すると素数で...
-
素数の平方根は無理数である。
-
親の再婚相手との問題です。私...
-
「証明証」と「証明書」はどう...
-
下の問題では漸化式の形から≠0...
-
47歳、母親の再婚を子供の立場...
-
ぶすですか?
-
直角三角形の性質
おすすめ情報