素数の基本性質

質問

今、「数を考える（岩波ジュニア）」という本を読んでいます。

ｐ１００、

「ｐを素数とするとき、整数a、bについて、
abがｐで割り切れれば、ａまたはｂがｐで割り切れる」

この証明なのですが、

ａｂが素数ｐで割り切れる　(1)と仮定する

このときａまたはｂがｐでわりきれることをしめしたいのであるから、さらに

ｂがｐで割り切れない　　(2)と仮定して、次を示せばよい

なおａは正としてよい

ａがｐで割り切れる　　(3)

という具合に証明が続いていくのですが、つまり、これを証明すれば最初の命題を証明したことになるようですが、なぜこれでよいのかがわかりません。

わかりやすく説明できる方はいませんか。

宜しくお願いします。

回答No.2

notnot · ベストアンサー

なにが分からないのか分からないのですが、途中の仮定ですかね。

＞ｂがｐで割り切れない
ケース１：bがpで割り切れる場合
ケース２：bがpで割り切れない場合
この2ケースのどちらか一方は正しいです。ケース1なら証明終わり。
続いてケース2の証明に移るということで、bがpで割り切れない場合を考えるわけです。

＞なおａは正としてよい
正の数aがpで割り切れれば、
a=p * N ⇒ -a=p*(-N)
なので、それに-1を掛けた数負の数-aもpで割り切れます。

お礼

ありがとうございます。途中の仮定です。

単に対偶を証明すればよいとも思ったのですが、実際それでもできますし、

内容も同じ様になると思うのですが、わざわざ背理法をつかってありましたので、戸惑ったのです。

よく考えてみればわかることなのですが。

回答No.7

178-tall

>d1f1、d1, f1 はｄ×１、ｆ×１という意味でしょうか。

ANo.6 で訂正したように、d1, f1 は
　p = d1*f1
　1 ＜ d1, f1 ＜p
を満たす 2 数。

p が素数ならそのような {d1, f1} は存在し得ない…という筋書きです。

回答No.6

178-tall

< No.5
錯誤の訂正。

0≦ d, f ＜p ゆえ、そのような d, f があれば、
　p = d1f1
　1 ＜ d1, f1 ＜p
なる d1, f1 が存在することになる。

回答No.5

178-tall

< ANo.4
への蛇足。

>(B) → 1≦ df ＜ p^2 かつ 積が p で整除可な d, f はあり得ない。

0≦ d, f ＜p ゆえ、そのような d, f があれば、
　p = d1f1
　1≦ d1, f1 ＜p
なる d1, f1 が存在することになる。(つまり、p は「半素数」)
これは、p が素数であるということに矛盾。(つまり、あり得ない)

補足

ありがとうございます。

d1f1、d1, f1 はｄ×１、ｆ×１という意味でしょうか。

ちょっと気になります。

宜しくお願いします。

回答No.4

178-tall

>ａｂが素数ｐで割り切れる　(1)と仮定する
　　↓
a か b の「少なくとも一方」が p で割り切れる

… はずだからです。

a (b) を p で割ったとき、商が c (e)、余りが d (f) だとすれば、
　ab = (cp+d)(ep+f) = (cep+cf+de)*p + df
　(ただし 0≦ d, f ＜p)
と書けそうな気配。

その左辺が素数 p で整除可なら、右辺の df は (A) 零か、(B) (非零) 正値かつ p で整除可、のはず。
(A) → a,b の「少なくとも一方」が p で整除可、ということ。
(B) → 1≦ df ＜ p^2 かつ 積が p で整除可な d, f はあり得ない。
　　↓
a か b の「少なくとも一方」が p で割り切れる。

お礼

＞（Ｂ） 1≦ df ＜ p^2 かつ 積が p で整除可な d, f はあり得ない。＜

ここのところを、ずっうと考えておりました。

たしかに、1≦ df ≦ p^2－１において、

dfはpで割り切れません。

1≦ df ≦ ｐ－１

df＝ｐのとき、

pは素数だからdf＝１×ｐ＝p×１となり、

いずれか一方はｐとなり、ｄ＜ｐ、ｆ＜ｐに反する。

したがってdfはｐでない。

p＋1≦ df ≦ ｐ＋（ｐ－１）

２p＋1≦ df ≦ ２ｐ＋（ｐ－１）

途中略

（ｐ－３）p＋１≦df≦（ｐ－３）p＋（ｐ－１）

df＝（ｐ－１）^２＝ｐ＾２－２ｐ＋１

やっぱりｐで割り切れない。

df＝ｎ×ｐ（※ｎは２以上の整数）について。

ｎが素数のとき、
ｎが合成数のとき、つまり、2つ以上の素数の積のとき、

df＝ｎ×ｐはいずれか一方はｐ以上になるので
ｄ＜ｐ、ｆ＜ｐに反する。

よって、ｄｆ＝ｎ×ｐ（※ｎは２以上の整数）とはならない。

ｄｆはｐの倍数にはならない。

以上からｄｆはｐで割り切れない。

※質問はどうやって証明するかではなかったのですが。

回答No.3

noname#212313

abが素数pで割り切れる場合に、

「aか、bか、少なくともどちらかがpで割り切れる」―(1)

ことを示したいわけですが、よく使われるのは、

「aもbも、pで割り切れないと仮定する」―(2)

というアプローチです。(1)以外が成立すると仮定して矛盾を示し、(1)が成立することを示す手法ですね。この(2)は、

「aがpで割り切れないと仮定する」―(3)
　　かつ
「bがpで割り切れないと仮定する」―(4)

という、「かつ」で結ばれる二つの条件（仮定）を、一つの文で表したものになっています。「かつ」ですから、(3)と(4)は共に成立しなければ、(2)を満たしません。ですから、どちらか一方の不成立を言えばいいわけです。

　そこで、まず(4)が成り立っているという前提（この前提に関しては、矛盾が起こるかどうか考えない）で、(3)が成り立つときの矛盾を証明してみる必要があります。それができたとして、今度は(3)が成り立っているという前提で、(4)が成り立つときの矛盾も証明する必要があるかどうか。

　ここで、abが何かと考えると、掛け算ですから順序を入れ替えて、baでも同じことです。ということは、二つの数について言うために、aとbという二つの文字変数を使ってはいるものの、aとbは特に区別する必要はないということです。

　つまり、「bがpで割り切れないときのa（の条件）」は「aがpで割り切れないときのb（の条件）」と、何ら区別する必要がありません。

　ですので、(4)は成り立っているという前提で、(3)が成立するときの矛盾だけを考えればいいことになります。

P.S.

　ついでですので、やっておくことにします。bはpで割り切れないとします。

　aがpで割り切れないということは、a＝pm+n（m, nはある整数、nはあまりで0ではない）と書けます。すると、

　ab＝(pm+n)b＝pmb+nb　―(5)

ということになります。問題の条件より、abは素数pで割り切れるのですから、(5)の右辺をpで割っても、割り切れるはずです。

　(pmb+nb)/p＝pmb/p+nb/p＝mb+nb/p　―(6)

　最右辺第1項のmbはpで割った結果であり、整数であることは明らかです。pで割りきれています。

　問題は第2項のnb/pです。これも割り切れていないと、mb+nb/p、ひいては、abがpで割り切れないことになります。しかし、bはpで割り切れないのですから、nがpで割り切れる必要があります。ところが、nはbをpで割ったあまりなのでした。ということは、n（の絶対値）はpよりも小さいということです。nがpで割り切れるわけがないですね。

　ということは、(6)はあまりが出ます。ならば(5)、つまりabはpで割るとあまりが出ることになります。これは、abがpで割り切れるという問題文の条件に反します。矛盾ですね。

　この矛盾は、（bがpで割り切れないという前提において）aがpで割り切れないと仮定したことにより、起こっています。ですので、仮定は誤りであり、aはpで割り切れるわけです。

　(4)の成立を認めても、(3)が成立してしまうと矛盾になるわけで、(3)は成立するとせねばならないわけです。少し考えると、前述したように、(3)の成立を認めると、(4)が不成立になることは、全く同じようにして示せます（上記証明で、aとbの文字を入れ替えるだけ）。

　これを、上記のようにab＝baを利用して端折ってしまわずにやろうとすると、最も少ない前提条件で証明するという緻密なものにはなりますが、、手間としては多少大変です。

　例えば、上記でa＝pm+nとしたのをbについても同様に、b＝pi+jと置いて、

　ab＝(pm+n)(pi+j)＝p^2+(ni+mj)p+nj

として、これがpで割り切れるとしたらどうなるかを調べることになります。最右辺で、pが掛けてある第1項、第2項はpで割り切れることは明らかです。

　ですので、njがpで割り切れるとしたら矛盾が起こることを示せばいいのですが、素数pより（絶対値が）小さい整数二つの積が、pで割り切れないことを示す必要があります。

　これも証明できはしますが、ab＝baという対称性を使って手間を省いた場合より、ちょっと大変になります。

お礼

しばらく考えておりました。時間が迫ってきましたので感想だけですが、ちょっと書いてみます。

＞abが何かと考えると、掛け算ですから順序を入れ替えて、baでも同じことです。ということは、二つの数について言うために、aとbという二つの文字変数を使ってはいるものの、aとbは特に区別する必要はないということです。＜

一般性は損なわれない。そうすると「ab＝baを利用して端折って」やったほうが、計算が楽になります。

しかし、ｎｊがｐで割り切れないことを示すほうを考えていました。

ここでは省きますが、たしかに割り切れません。

質問はこの問題の解法ではなかったのですが、いろいろ解いてありましたので、勉強になりました。

回答No.1

f272

(A)bがpで割り切れる
(B)bがpで割り切れない
(C)aがpで割り切れる
として(A)か(B)のどちらかです。
もし(A)であれば「ａまたはｂがｐで割り切れる」と言えます(bがpで割り切れるから)。
もし(B)であれば(C)が導けるのですからやはり「ａまたはｂがｐで割り切れる」と言えます(aがpで割り切れるから)。

お礼

ありがとうございます。いつも明快な回答に感謝です。