人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: koime_ryokutya
●カテゴリ:コンピュータ 学習・教育
✍キーワード:PQ とある
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● a-kuma3
●25ポイント

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


2 ● はぴすぃ714
●25ポイント

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の倍数」であることが必要です。


3 ● i_kumagoro
●25ポイント

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の約数)を約数に持たない」は誤りです。


4 ● katekin
●25ポイント

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の倍数である。



●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ