• ベストアンサー
  • すぐに回答を!

素因数分解の証明問題

素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、 φ(n)=n{1-(1/p_1)}{1-(1/p_2)}・・・{1-(1/p_r)}となることを示せ。 ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。 よろしくお願いします。

共感・応援の気持ちを伝えよう!

  • 回答数2
  • 閲覧数137
  • ありがとう数4

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.1
  • R_Earl
  • ベストアンサー率55% (473/849)

数学的帰納法で解けそうです。 [1] n = (p_1)^e_1の時にφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}を証明 [2] r = kの時にφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成り立つと仮定した時、 r = k + 1の時でもφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成り立つ事を証明 [1], [2]より全ての整数n = (p_1)^e_1(p_2)^e_2・・・(p_r)^e_rに対して φ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成立 とすれば良さそうです。 [2]を証明する際に 「自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)」 という事を利用できそうです。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

参考にさせていただき、解くことができました。 ありがとうございました。

関連するQ&A

  • 素因数分解

    全ての自然数は、素因数分解出来るのでしょうか? また、出来る場合は、それが証明されているのでしょうか?

  • 素因数分解はなぜ困難?

     今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。

  • 素因数分解

    1、 216を出来るだけ小さい自然数でわって、ある整数の2乗になるようにしたい。どんな自然数でわればよいですか? 2、 504に出来るだけ小さい自然数をかけて、ある整数の2乗になるようにしたい。どんな自然数をかければよいですか? この問題を素因数分解を使って解くようなのですが、、、、、 わかる方いましたら教えてください。 よろしくお願いします。

その他の回答 (1)

  • 回答No.2
  • Tacosan
  • ベストアンサー率23% (3656/15482)

文章に不明確なところがあります: ・「φ(n)」の定義を書いてください. ・「p_1, p_2, ..., p_r がすべて異なる」という条件はありますか? ありませんか?

共感・感謝の気持ちを伝えよう!

質問者からの補足

φ(n)はEuler関数のことです。 p∈Nに対して、φ(p)=|{n|1≦n≦p,gcd(n,p)=1}| つまり、φ(p)は集合の要素の個数を表しています。 p_1, p_2, ..., p_r はすべて素数で異なります。

関連するQ&A

  • 素因数分解をこの問題でどう使うのか??

    問題 「a、b、cは自然数とする。 2^3a×3^2b×5^cで表せる6桁の数があり、その中央の4桁は0736であることがわかっているとき、a,b,cの値を求めよ。」 これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。 ~私の解法(素因数分解の利用なし)~ 3^2b=9の倍数なので、9の倍数の性質と2×5=10を利用して6桁の数が「207360」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも9の倍数の性質を知らないと解けない問題自体見たことがありません。 素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。

  • 素因数分解!?

    xは自然数でx^2=736164のときxを求めよ。という問題なのですが、素因数分解してくと2、2、3、3の順で分解できるのはすぐ気づきます。しかし20449でとまってしまいます・・。なんとか143で分解できると気づいてx=858と答え出せたのですが、もっと上手い解き方ありますか?あるいは、2~3桁の素数の積を一瞬で見分ける方法はありますか?わかる方いましたらお願いします。

  • 素因数分解の一意性?????

    m,n,p,qをすべて互いに素な自然数とした時に、 2^n・p^m=q^mにおいて、 素因数分解の一意性より、qは2の倍数である。 素因数分解の一意性ってどういうことなのでしょうか?

  • 正規数と素因数分解に関する証明問題

    正規数と素因数分解に関する証明問題です。 xが正規数(1/xが60進有限小数) ⇔x=2^a3^b5^cと素因数分解できる xが正規数(1/xが12進有限小数) ⇔x=2^a3^bと素因数分解できる 以上2題の証明がどうしてもわかりません。 わかる方、教えてください。

  • 素因数分解の問題で…

    素因数分解の問題で… 中学3年の姪っ子に数学を教えています。 市販の問題集で、解説と回答を見てもどうしても分からない問題があるんです。 〈素因数分解の問題〉 Aは100より小さい自然数で、Aに54をかけると自然数の2乗になるという。このような自然数Aは全部で何個あるか。 〈解答・解説〉 54=2×3の3乗=6×3の2乗だから、A=6×Nの2乗の形になればよい。 A〈100だから、 N=1のとき、A=6 N=2のとき、A=24 N=3のとき、A=54 N=4のとき、A=96 したがって、Aは4個 と参考書には記載されています。 解説の「A=6×Nの2乗の形になればよい。」という理屈が分かりません。 姪っ子に教えられなくて困っています…。 どなたか分かりやすく解説して頂けないでしょうか? よろしくお願い致します!

  • 素因数分解

    X4乗+4を素因数分解してください。また文字のついているものを素因数分解する方法を教えてください。

  • 素因数分解の問題です

    素因数分解の問題です nは2ケタの自然数で n/20 を既約分数にしたとき 分母が5になるという このようなnは全部で何個あるか?? 答えは18となっています やり方を教えてください

  • 素因数分解でわからない問題があります。教えていただ

    けますでしょうか。 勉強していて、下記の問題がどうしてもわかりません。 解答はついているのですが、考え方がわかりません。 教えていただけないでしょうか? 問い 56にできるだけ小さい自然数をかけて、ある整数の二乗にしたい。どんな数をかければよいか? 素因数分解はできるのですが(2の3乗X7)、その後の考え方がわかりません。 ちなみに答えは2X7=14 です。 解説に、56=2の3乗x7=2の2乗x(2x7) よって、2x7=14とありますが、 この解説がまったく理解できません。 2x7=14が何を意味するのかがわかりません。 どう考えればよいのでしょうか? 同じく 360を自然数でわって、ある整数の2乗にしたい。どんな数でわればよいか? という問いも、素因数分解から先の考え方がわからず、解けません。 (答え10,40,90,360)。 どなたか 解き方(考え方)を教えていただけますでしょうか。

  • 素因数分解について

    X=√4,840,000 を素因数分解?? で解く場合、100*2*11=2,200 となると思いますが、素数の100を1000にしては駄目ですか? そもそも、素因数分解のルールが理解出来ていません。 素因数分解の簡単なやり方を分かり易く教えて下さる方、宜しくお願いいたします。 因数分解は方程式なので、取っ付きにくいイメージがあります。

  • 素因数分解ができない?

    123、205の最大公約数はいくつでしょう? 素因数分解をして求めたいのですが、 123は3で割って41 3* 205は5で割って41 5* となるのでしょうか? その後の素因数分解が続きません。 すいませんが、教えてください。 よろしくお願いします。