自然数nに対し,nと互いに素であってnを超えない自然数の個数をφ(n)で表す.
a,bを自然数,p,qを異なる自然数として,以下の問いに答えよ.
(1)φ(9)を求めよ.
(2)φ(p^a)を求めよ.
(3)φ{p^aq^(b-1)}=4p^aq^(b-1)を満たすp,qをすべて求めよ.
この問題の解答を教えてほしいです
|
No.28833 - 2014/09/12(Fri) 01:43:28
| ☆ Re: / angel | | | 多分
(1) φ(9)=6
(2) φ(p^a)=p^(a-1)・(p-1)
(3) (p,q)=(3,7) ※1組のみ
なのでしょうけど、色々問題の条件がおかしかったり、条件が不足しているように見えます。
※だからこのままでは、本当は解けない
過不足・誤り等ないか確認してください。
|
No.28835 - 2014/09/12(Fri) 12:45:15 |
| ☆ Re: / くまたろう | | | No.28839 - 2014/09/12(Fri) 17:30:29 |
| ☆ Re: / angel | | | (3)の問題もあっていますか?
さて、(1),(2)についてはφ(n)の定義をしっかり把握するのが大事です。
「nと互いに素であって、nを超えない自然数の個数」
ですから、
・φ(9) = ( 1〜9の中で9と互いに素な自然数の個数 )
となります。
どんな数が9と互いに素かと言うと、それは3の倍数でないもの全て。なので6個です。
・φ(p^a) = ( 1〜p^a の中でp^aと互いに素な自然数の個数 )
p^a というのは、素因数をpしか持ちません。
なので、それと互いに素な数と言うのは、pの倍数でないもの全て。(1)と似たような状況です。
1〜p^aから、pの倍数 p^a/p個を除くと、
p^a-p^a/p=p^a・(1-1/p)=p^a・(p-1)/p=p^(a-1)・(p-1)
と個数が計算できます。
|
No.28842 - 2014/09/12(Fri) 18:26:36 |
| ☆ Re: / くまたろう | | | 何度も訂正すみません
(3)の左辺はφ(p^aq^b)
でした。
|
No.28859 - 2014/09/13(Sat) 00:21:09 |
| ☆ Re: / angel | | | (3) φ(p^a・q^b)=4p^a・q^(b-1)を満たすp,qをすべて求めよ
今度のφは、「1〜p^a・q^b の中で、p^a・q^b と互いに素な自然数の個数」です。
(2)と違う点は、素因数が「pのみ」→「pとq」になっている所です。なので、
「pの倍数でもqの倍数でもない数」の個数を数えることになります。
ここで、集合の時に出てきたベン図を描く/思い描くなりしてほしいのですが、
(pの倍数でもqの倍数でもない数)
= (全体)-(pの倍数の数)-(qの倍数の数)+(p,q両方の倍数の数)
です。なお、最後の項「p,q両方の倍数」は結局の所「pqの倍数」に他なりません。
※素数p,qの最小公倍数はpqだから
と言うわけで、条件を整理すると、
φ(p^a・q^b)
= p^a・q^b-p^a・q^b/p-p^a・q^b/q+p^a・q^b/(pq)
= p^a・q^b・( 1-1/p-1/q+1/pq )
= p^a・q^b・(p-1)(q-1)/(pq)
= p^(a-1)・q^(b-1)・(p-1)(q-1)
φ(p^q・q^b)=4p^a・q^(b-1) ( = p^(a-1)・q^(b-1)・4p )
に適用すると、p^(a-1), q^(b-1) が綺麗に消えて
(p-1)(q-1)=4p
展開してから再度積の形にまとめなおすと、
(p-1)(q-5)=4
これを満たす(p,q)を全て列挙し、p,q共に素数になるものだけに絞り込むと、残るのは(3,7)のみ、となります。
|
No.28864 - 2014/09/13(Sat) 15:33:44 |
|
