整数の基本問題

質問

整数の基本問題です。

2つの整数ap,bpを考えます。（a,b,pは全て整数で、aとbは互いに素）
ap,bpは両方とも整数dで割り切れます。
この時pはdで割り切れることを証明したいのですが、
どうすればよいでしょうか。
記号では以下のように表すとします。

d|ap・・・(1)　d|bp・・・(2) (a,b)=1・・・(3)→ d|p

それではよろしくお願いします。

回答No.8

ka1234 · ベストアンサー

こんにちは。

dを素因数分解します。d=J^j×K^k×L^l×・・・
(J, K, L, ・・・は素数、j, k, l, ・・・は正の整数)

(1)より、J^j を ap に振り分けると、
[1] a が素因数 J を1つでも持つ場合
[2] a が素因数 J を1つも持たない場合
に分けられる。

[1]aとbは互いに素であるから、aがJを1つでも素因数に持てばbはJを素因数に持たない。
すると、bpはdで割り切れるので、pが素因数Jをjコ持つ事になるが、aはJをjコ未満しか持たないので（少なくとも1つはaが持つから）、これは成り立たない。
従ってJ^jは全てpに含まれる。他の素因数についても同様であるから、pはdで割り切れる。（証明終わり）

イメージとしては、dの素因数Jが3コあったとして、
そのうち1つでもaにあげると、bは「要らないよ」っていう感じです。
・aが1コ取ったので、相手のpはJが2コとなり、
・bは1コも取っていないので、相手のpはJが3コということになります。
・すると同じ数であるはずのpに含まれる素因数Jの個数が違ってしまうので矛盾ということです。

お礼

なるほど、dを素数冪分解して
その素数一つ一つに対してpの因数になるか確かめればできますね。

どうもありがとうございます。
また何か他に別解なども思い付きましたらよろしくお願いします。

回答No.12

noname#47975

以下の補題を知っていれば簡単ですが…。
補題そのものを証明しないといけないかと思いますので、結局はシンドイですね．．。
だが、別解として参考程度になればと思います。

補題：(a,b)=1のとき、 ka + hb = 1となるような(k,h)は存在する。
（証明は下記のＵＲＬ参照の事）
http://oshiete1.goo.ne.jp/qa2635749.html

証明：

(a,b) = 1 & d|ap & d|bp ⇒ d|(ka+hb)p（k,hは任意の整数)--(1)

補題より、ka + hd = 1となるような(k',h')が存在する事から、(1)より、

(a,b) = 1 & d|ap & d|bp　⇒ d|((k')a+(h')b)p

となる。また、((k')a+(h')b)=1より、d|((k')a+(h')b)p ⇔ d|p
である事から、

∴(a,b) = 1 & d|ap & d|bp ⇒ d|p

お礼

ご回答どうもありがとうございます。

いろいろな証明方法がありますね。
勉強になります。

確かにこの証明法をすぐに使いこなすのは難しそうです。
まだ整数論の勉強を始めたばかりでして・・・。

どうもありがとうございました。

補足

皆様ご協力どうもありがとうございました。
いろいろ勉強になりました。

実は自分なりに考えている解き方がありまして。
何とかその方法で解ければと思っているのですが・・・。

少し聞きたいこととずれてきてしまったので、
この質問は一旦締め切りまして、
新しい質問を立てることにしました。

良かったらそちらの方もご協力お願いします。

この度はどうもありがとうございました。

回答No.11

ka1234

ANo.8です。

・（３）より、ａとｂは互いに素であるから、ａｐとｂｐの最大公約数はｐである。

・（１）（２）より、ｄは、ａｐとｂｐの公約数である。

公約数は最大公約数の約数であるから、ｄはｐの約数である。（証明終わり）

お礼

ご回答どうもありがとうございます。

>公約数は最大公約数の約数であるから、ｄはｐの約数である。

実はこれが元ネタでして・・・。
質問はこれを証明する過程で出てきた途中式です。

回答No.10

aquarius_hiro

ANo.2です。

すみません。間違ってしまいましたm(_ _)m

a=a1×a2×…×an
b=b1×b2×…×bm
d=d1×d2×…×dr

と素因数分解したとき、0≦s≦rとして、

p=d1×d2×…×ds×p1×…×pk …(4)

と書けたとし（d0=1とおく）、d{s+1},d{s+2},…,dr が素因数p1,…,pkに含まれないとします。（ここまでは一般性を失っていない。）

いま、s＜rとすると、drが{a1,…,an}と{b1,…,bm}の両方に含まれなければ、dがapとbpの両方の約数になれません。従って、aとbは共通の約数drをもつことになるので、互いに素であるという条件に矛盾します。

従って、s=rであり、(4)より、pはdで割り切れます。

こんどこそ大丈夫だと思いますが、ミスがあったらすみません。

お礼

度々のご回答どうもありがとうございます。

素数の冪に素因数分解する方法ですね。
やはりこのやり方が一般的でしょうか。

どうもありがとうございました。

回答No.9

Tacosan

多分以下で OK のはず.
「d | m, d | n なら d | (m, n)」を使っていいなら ((a, b) = 1 なら (ap, bp) = p なので) 一瞬.
使っちゃダメといわれると面倒なんだけど対偶 ((d | ap & d | bp & not (d | p)) → (a, b) > 1) を証明しにいく:
１．d = 1 のとき: 自明.
２．d > 1 かつ d と p が互いに素のとき:
d | ap より d | a. 同様に d | bp より d | b だから a と b は d を共通因数として持ち, これは 1 より大なので (a, b) > 1.
３．d > 1 かつ d と p が互いに素でないとき:
q = (d, p), d = d' q, p = p' q とおく. (d', p') = 1 かつ (not(d | p) より) d' > 1 である.
ここで d | ap ⇔ d' | a p', d | bp ⇔ d' | b p' より (２ を使うと) a, b は d' を共通因数として持つ. d' > 1 だから (a, b) > 1.

お礼

度々どうもありがとうございます。

対偶でも解けるのですね。
勉強になります。

>「d | m, d | n なら d | (m, n)」を使っていいなら ((a, b) = 1 なら (ap, bp) = p なので) 一瞬.

これは実は証明したい式そのものですので、これを使われるときついです。

どうもありがとうございました。

回答No.7

Tacosan

#5 です.
どちらも間違ってはいません.
#5 の証明は, 対偶証明の一種になります.
つまり, もともと証明したい命題は
(d | ap & d | bp & (a, b) = 1) → d | p
ですが, これは
not((d | ap & d | bp & (a, b) = 1)) or (d | p)
と等価です. さらにいじると
not(d | ap) or not(d | bp) or (a, b) > 1 or (d | p)
となり, もっといじると
not(d | ap) or not(d | bp) or not(not(d | p)) or (a, b) > 1
です. で, 最終的に
not(d | ap & d | bp & not(d | p)) or (a, b) > 1
だから
(d | ap & d | bp & not(d | p)) → (a, b) > 1
を証明しにいっています.
この not(d | p) の部分を処理するために「d と p が互いに素のとき」と「互いに素ではないとき」に分けています. また, 最後の (a, b) > 1 は「a と b が (1 より大きい) 共通因数を持つ」ことを示せば OK です.
....
今思ったんだけど, (a, b) = 1 なら (ap, bp) = p だよなぁ....

お礼

再びの回答どうもありがとうございます。

この回答はちょっと複雑で難しいですね。

>(d | ap & d | bp & not(d | p)) → (a, b) > 1

の証明自体が元の証明と同等に私には難しい気がします。

まだ締め切りませんので、シンプルな別解などが思いつきましたら
また教えてください。

回答No.6

dmg7

vigo24さんは
p=6,a=4,d=8の時p=8,a=2,d=4の時など例えられてますが、
その時bはどうなるか考えてください
>2つの整数ap,bpを考えます。（a,b,pは全て整数で、aとbは互いに素）>ap,bpは両方とも整数dで割り切れます。
が条件ですので、p=6,a=4,d=8のときはbはどうなりますか？
aとbは互いに素なのですからbは2以外の素数を持ちますよね？
そのようなもので上の条件を満たすものはありますか？

補足

ご回答どうもありがとうございます。

>p=6,a=4,d=8の時p=8,a=2,d=4の時など例えられてますが、
その時bはどうなるか考えてください

おっしゃることは分かります。
要するにこの問題は(1)、(2)、(3)全ての条件を同時進行的に使わないといけないということです。

だとすると
まず条件(1)のみを考え、
次に『同様にして(2)の場合も』などとする解法は

条件(1)のみを考えた場合には、
>p=6,a=4,d=8の時p=8,a=2,d=4の時
のような不適解が入ってしまうので、
『同様にして(2)の場合も～』の議論には進めないということです。

この不適解を取り除くには条件(1)、(2)、(3)を同時進行的に扱わないとまずいと思います。

また何か分かりましたらよろしくお願いします。

回答No.5

Tacosan

#1～#4 を組合せるとこんな感じかな:
１．まず d と p が互いに素である場合を考える. これは, まあ簡単.
２．で d と p が互いに素ではない場合だけど, q = (d, p), d = d' q, p = p' q とおくと (d', p') = 1 かつ d | ap iff d' | ap' なので１に帰着される, と.
とりあえず解答そのものになるのは回避したつもり.

補足

ご回答どうもありがとうございます。

>１．まず d と p が互いに素である場合を考える. これは, まあ簡単.

dとaが互いに素の書き間違いだと思っていいのでしょうか？

>d' | ap' なので１に帰着される

d’|aだからといってd|aはいえないような気がするのですが・・。

何か私の勘違いでしたらご訂正ください。

回答No.4

Segenswind

ｐがｄで割り切れない　＝　ｄはｐと共通しない素因数を少なくとも１つ持つ

と考えれば、帰謬法で証明できます。

補足

もう少し詳しく説明していただけるとありがたいです。

回答No.3

zk43

(1)dがpを素因数に持たない場合
　d|apより、d|a
d|bpより、d|b
(a,b)=1より、d=1
よって、d|p
(2)dがpを素因数に持つ場合
　d=pkと書ける。
　pk|apより、k|a
　pk|bpより、k|b
(a,b)=1より、k=1
　よって、d=pとなり、d|p

補足

ご回答どうもありがとうございます。

>(1)dがpを素因数に持たない場合
>　d|apより、d|a
>d|bpより、d|b

p=8,a=2,d=4の時には成り立たないような気がします。

回答No.2

aquarius_hiro

vigo24さん、こんにちは。

まず、pがdで割り切れないとします。（背理法を使う。）
そうすると、apがdで割り切れるためには、aがdで割り切れる必要があります。bdについても同様で、bがdで割り切れることがわかります。ところが、これはaとbが互いに素という条件と矛盾します。
したがって、pはdで割り切れます。

別の書き方もしてみます。pがdで割り切れないとしたら、pはdを約数として含みません。一方、apとbdはdで割り切れるので、dという約数を含みます。pがdを約数として含まないのでaとbにdという約数が含まれなければなりません。これはaとbが互いに素という条件と矛盾します。
従って、pはdで割り切れます。

> 記号では以下のように表すとします。
> d|ap・・・(1)　d|bp・・・(2) (a,b)=1・・・(3)→ d|p

d|pが成立たないとしたら、(1)d|apよりd|a。(2)d|bpよりd|b。これは(3)(a,b)=1に矛盾。従って、d|pは成立つ。

補足

aquarius_hiroさん、御回答どうもありがとうございます。

FEX2053さんの補足にも書いたのですが、

>まず、pがdで割り切れないとします。（背理法を使う。）
>そうすると、apがdで割り切れるためには、aがdで割り切れる必要があります。

これが単純にはいえないような気がします。
例えばp=6,a=4,d=8などの場合です。