素数？？

質問

すみません、すごい単純な問題かもしれないんですけど…

[問]
P が素数とする。
ab が P で割り切れるならば、a は P で割り切れる。または、b は P で割り切れる。

この証明を考えているんですが、なんか当たり前というか…
素数 ←ってのが証明で必要だと思うのですが、
なかなかしっくりこなくて困っています。
どのように解けばいいのでしょうか？？

くだらない問題ですみませんが、よろしくお願いします。

回答No.11

zk43 · ベストアンサー

これは、くだらないどころではなく、すごく基本的かつ重要なことです。
（数学の最も根本にあるものと思える。）
Zを整数全体の集合とし、Zの部分集合Sで、
x,y∈Sならばx-y∈S
という性質を持つものを考えます。
すると、x-x=0なので、0はSの元です。
また、0-x=-xなので、xに対して-xもSの元です。
さらに、x+y=x-(-y)と書けるので、和x+yもSの元となります。
さらに、x+x+…+x=nx、-x-x-…-x=-nxにより、帰納的にxの整数倍も
Sの元となります。
つまり、「x,y∈Sならばx-y∈S」という性質を持つ整数全体の集合の
部分集合は、和に関しても閉じており、任意の整数倍についても閉じて
いることになります。（代数学では、このようなSをイデアルといいま
す。）
Sが0以外の元を含むとき、xと-xを含むので、必ず自然数を含みます。
そこで、Sに含まれる最小の自然数をmとします。
nをSの任意の元とするとき、nをmで割ったときの商をq、余りをrとすると、
n=qm+r（0≦r＜m）と表わせて、r=n-qmとなり、nもqmもSの元なので、
従って、その差n-qmもSの元、すなわち、rはSの元となります。
mがSに含まれる最小の自然数としたので、0<r<mではありえず、r=0と
なります。したがって、n=qmとなり、Sの任意の元はmの倍数です。
逆にmの倍数はSの元であるので、Sはmの倍数全体の集合となります。
以上まとめると、Sは{0}または、Sに含まれる最小の自然数の倍数全体
の集合となります。

つぎに、pがaを割り切らない、つまり、pとaが互いに素であるとして、
px+ay（x,yは整数）という形の数全体の集合を考えます。
(px+ay)-(px'+ay')=p(x-x')+a(y-y')となるので、これは上の集合Sの
性質を満たしています。
従って、S={px+ay|x,y∈Z}とおくと、SはSに含まれる最小の自然数mの
倍数全体の集合になっています。
pもaもSに属しているので、pもaもmの倍数、すなわち、mはpとaの公約
数となり、pとaの最大公約数である1以下になります。
よって、m=1。
よって、px+ay=1となる整数x,yがあります。
両辺にbを掛けると、
pbx+aby=b
pはpbxを割り切り、abyを割り切るので、pは左辺を割り切り、したがっ
て、右辺のbを割り切ります。
pがbを割り切らないとした場合でも、対称的な議論により、pはaを割り
切ることが分かります。

長々書きましたが、pとaが互いに素なとき、px+ay=1を満たす整数x,yが
存在するというところがポイントです。

この素数の性質により、初等整数論の基本定理（素因数分解の一意性）
も証明されます。

回答No.12

ringohatimitu

これはただ自然数の除法、乗法を定義しただけの段階ではそんなに明らかなことではないんですよね。
素因数分解を自明とした上では当然のように思えますがその素因数分解の一意性が案外曲者です。とはいえかなり簡単に証明されますので以下参考にしてみてください。たとえば次のように背理法で素因数分解の一意性を示すことができます。

素因数分解の一意性が成り立たない最小の自然数nがとれたとします（～～を満たす最小の自然数をとるという自然数の命題でよくとられる論法です）。n＝p_1 p_2 p_3 ...＝q_1 q_2 q_3 ...と異なる２通りの分解で表します（小さい順に並べておきます）。このとき左辺の素因数と右辺の素因数の中に一致する素数は一つもありません。というのも仮にp＝p_1＝q_2などとすればn/pはnより小さくしたがって仮定より一意に分解されるはずですが上の二つの分解が異なることに矛盾です。要するに素数としての集合{p_1 p_2 ...}と{q_1 q_2 ...}は共通部分を持たないということです。さて小さい順に並べてあるのでp_1＜p_2なので(p_1)^2＜nです。同じく(q_1)^2＜nも成り立ちます。したがって(p_1)(q_1)＜nです。別の自然数m＝n-(p_1)(q_1)＜nをとります。mに関してはnに対する仮定より素因数分解の一意性が成り立ちます。またnがp_1,q_1両方で割り切れるのでmも両者で割り切れます。m＝p_1 ...＝q_1 ...と分解すれば一意性によりq_1が左辺の分解のどこかにあるはずで結局mは(p_1)(q_1)で割り切れることが分かります。するとn＝m+(p_1)(q_1)は(p_1)(q_1)で割り切れますから(n/q_1)はp_1で割り切れます。(n/q_1)＜nですから再び仮定より(n/q_1)は一意に素因数分解されるはずです。すなわちq_2 q_3 ....が唯一の分解になってるわけですが
一方でp_1 ...という分解もあるのでp_1がq_2,q_3,...のどれかでなくてはなりません。しかし最初に示したことからこれはあり得なく結局矛盾です。

言ってることは極単純なことなので随所で使われる「仮定」に注意して読んでください。
これの後で#8さんのように進めればよいです。

回答No.10

koko_u_

うーむ。ユークリッドの互除法はアルゴリズムも明快なので、初学者にはお勧めなんですが。

ANo.8 氏はわかってて書いているのか不明ですが、「素因数分解は一通りしか無い」証明に質問文にある命題が必要なので、循環論法になってダメです。

回答No.9

yoikagari

koko_uさんのおっしゃている「a, b が互いに素ならば ax + by = 1 を満たす整数 x, y が存在すること」の証明はたとえば、
http://aozoragakuen.sakura.ne.jp/suuronN/node15.html
を参照してみてください(初心者には難しいと思います)

回答No.8

hugen

[高校レベルの証明]
それぞれの素因数分解を
a＝a1・・an
b＝b1・・・bm
ab＝c1・・・・P　　　とすると
(a1・・an)(b1・・・bm)＝c1・・・・P　　　
「素因数分解は一通りしか無い」から、右辺は左辺の並べ替えであり
P は、a1,・・,an , b1,・・・,bm のいずれかと一致する。

回答No.7

yoikagari

整数に関する基本的な定理の証明は中学、高校、大学でも敬遠されているようです。
たぶん当たり前に見えるのに、きちんとやると難しいからでしょう。
歴史的にも、Gaussより前の数学者は「素因数分解の一意性の定理」は「証明すべきこと」という認識はなく、「当たり前のこと」として認識されていたようです。
しかし、「素因数分解の一意性の定理」も「定理」とあるようにきちんと厳密な証明が与えられているのです。
(ちなみに、素因数分解の一意性の定理を最初に証明したのはGaussです)

xyz0122さんの考えた命題
「pを素数とする。
abがpで割り切れるならば、aはpで割り切れる。または、bはpで割り切れる。」
は決してくだらない問題ではなく、きちんと考えると難しいのです。
私の解答を見ても、はじめは何のことやらわからないかもしれません。
(私も最初はわからなかったです)
頑張って理解してみてください。

回答No.6

koko_u_

この問題は素因数分解の一意性の証明の基礎を成すものなので見た目ほど簡単ではありません。

よくやるのは a, b が互いに素ならば ax + by = 1 を満たす整数 x, y が存在することをユークリッドの互除法などで証明してから

a が p で割り切れなければ、互いに素なので ax + py = 1 なる整数 x, y が存在する。よって

b = 1*b = abx + pby 。右辺は仮定により p で割り切れるので b も p で割り切れる。

回答No.5

yoikagari

私が書いた方法以外にも
「abがcで割り切れ、aがpと互いに素ならばbがpで割り切れる」・・・＊
という定理を用いると証明することが出来ます(やってみてください)。

＊の証明は以下のサイトを参照してください。
http://aozoragakuen.sakura.ne.jp/suuronN/node10.html

回答No.4

yoikagari

以下a*bはaかけるbつまりabを意味します。

「a*b が 素数pで割り切れるならば、aはpで割り切れる。または、bはpで割り切れる。」
をヴェイユの方法で証明します。
意外と難しいので、じっくり読んでください。

aがpで割り切れるとき
a=p*kとかけるからa*b=p*(kb)となって、abはpで割り切れます。

aがpで割り切れないとき
以下のような集合Sを考えます
S={nは正の整数でn*bがpで割り切れる}
Sの要素の中で最小のものをeとおきますと・・・※
以下のようなことが言えます。
「Sの任意の要素kはeで割り切れる。」・・・○
○の証明
ある要素kがeで割り切れなかったと仮定します。
kをeで割り、商をq、余りをrとしますと
k=e*q+r,0＜r＜e
k,eはSの要素だから以下のようにかけます。
k*b=p*u,e*b=p*v(ただし、u,vは整数)と書けます。
r*b=(k-eq)*b=k*b-(e*b)*q=p*(u-vq)だから
r*bはpで割り切れます。よってr∈Sがいえます。
ところが、0＜r＜eよりrはeより小さなeの要素になり
※のeの仮定に反します。
よって、Sの任意の要素kがeで割り切れることがいえました。
○の証明ここまで

a*bはpで割り切れるし、pもpで割り切れる
よってa,p∈Sがいえます。
よって○よりb,pはeで割り切れます。
a=e*c,p=e*f(ただし、c,fは整数)・・・●
したがってeはpの約数です
pは素数ですからe=1,p以外起こりません
e=pと仮定しますと
●よりa=p*cとなりaがpで割り切れることになって
aがpで割り切れないという仮定に反します。
したがって、e=1となります
このとき、b=e*b=p*vとなって、bがpで割り切れることがわかります。

回答No.3

yoikagari

kumipapaさんとAronseさんの方法は、循環論法のような気がします。
証明で暗に「ab が 素数pで割り切れるならば、aはpで割り切れる。または、bはpで割り切れる。」を使っているような気がします。

回答No.2

Aronse

1さんと基本的に同じなんですが、（1さんは2通りの書き方をしてくれていますね）

abがpで割り切れることより、ab=pk(kは整数)とおける。
これより、a=pk/b
aが整数であることより右辺も整数
ここで、bがpで割り切れないとすると、
a=pn(n=k/bとおいた。nは整数)。これよりaはpの倍数である。
したがって、aはpで割り切れる。または、bはpで割り切れる。