N = pq(p, q は互いに素)の時、gcd ( N , n ) ≠ 1 となるものの条件は、pの倍数あるいはqの倍数である。

とあるのですが、なぜそうなるのでしょうか?
pの倍数あるいはqの倍数がgcd ( N , n ) ≠ 1となる、のは分かるのですが、これらに限られる、ということがピンと来ません。

参考
http://izu-mix.com/math/exam/yokoichi/2006_1.html

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2011/07/19 14:49:25
  • 終了:2011/07/26 14:50:04

回答(4件)

id:a-kuma3 No.1

a-kuma3回答回数4488ベストアンサー獲得回数18572011/07/19 14:59:17

ポイント25pt

p と q が、それぞれ素数だ、という条件を忘れてるから、ピンと来ないんじゃありませんか?

id:Happisee714 No.2

はぴすぃ714回答回数43ベストアンサー獲得回数72011/07/19 16:23:20

ポイント25pt

p,qが互いに素なので、

Nの約数は 1,p,(pの約数),q,(qの約数),(pの約数×qの約数),N です。


もし、「nがpの倍数でもqの倍数でもない」ならば、

nは p,(pの約数),q,(qの約数),(pの約数×qの約数),N を約数に持たないので、gcd(N,n) = 1 となってしまいます。


なので、gcd(N,n) ≠ 1 となるためには、

「nがpの倍数あるいはqの倍数」であることが必要です。

id:i_kumagoro No.3

i_kumagoro回答回数170ベストアンサー獲得回数582011/07/20 10:20:25

ポイント25pt

N=pq (p, qは互いに素)

であれば、nがpの倍数あるいはqの倍数であることはgcd(N, n)≠1であるための十分条件ではありますが、必要条件ではありません。

例えば、p=4, q=9, n=6の場合を考えてください。Nは36になり、gcd(36, 6)=6ですが、nはpの倍数でもqの倍数でもありません。

ちなみに、参考先に書かれた前提は「互いに異なる素数」であって、「互いに素」ではありません。本来質問したかった内容が、参考先と同一の、「互いに異なる素数」を前提としたものであるのであれば回答は以下のようになります。

Nの約数は1, p, q, N (=pq)しか存在しないので、gcd(N, n)はnの値によらず前述のいずれかの値になります。gcd(N, n)が1以外になるということは、nが1以外のNの約数を約数に持つということです。1以外のNの約数はすべてpの倍数またはqの倍数であるため、nもpの倍数またはqの倍数になります。


また、2番目の回答者が書かれた

nは p,(pの約数),q,(qの約数),(pの約数×qの約数),N を約数に持たない

のうち、「(pの約数), (qの約数), (pの約数×qの約数)を約数に持たない」は誤りです。

id:katekin1982 No.4

katekin回答回数12ベストアンサー獲得回数12011/07/25 01:34:11

ポイント25pt

a-kuma3さんやi_kumagoroさんが指摘しているとおり、pとqが素数であることがポイントです。


gcd(pq,n)≠1となるとき、pとqは素数であるので

 gcd(pq,n)=q または gcd(pq,n)=p

 (pq > n より gcd(pq,n)=pqとはならないことに注意しよう)

となる。

よって、nはpの倍数あるいはqの倍数である。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません