整数の約数・倍数の問題

Question

二つの正の整数の和は54で、その最小公倍数は231である。各数を求めよ。
という問題です。

231=3*7*11、二つの整数の和が54より最大公約数は3.∴求める２数は3*7、3*11つまり21,33.
と解説があるのですが、よくわかりません。

最小公倍数とは、２数に共通する因数の２数に共通しない因数の積ということは覚えていたので、その２数をA,BとするとA（B）=3^l*7^m*11^n、となるから、3,7,11を掛け合わせて和が54になるような2数を探せばよいんだなという方針で、答えはでたのですが、あまり能率的ではないような気がします。

解説の解説をお願いします。
宜しくお願いしますm（__）m

maris_stella · Accepted Answer

231=3*7*11

以上のように素因数分解されているということは、二つの数で、この三つの素数を使わなければならないということです。「最低一回」使うのです。

しかし、二つの数の和は、５４だと言います。すると、一方の数で、７＊１１を使うと、これで、７７になり、もう５４を越えてしまいます。

残りの可能性は、７と１１を二つの数に分けることです。３＊７，１１という可能性と、３＊１１，７という可能性が思いつきますが、これでは、５４に足らないのです。（前の場合、２１＋１１＝３４で、後の場合、３３＋７＝４０です）。

３を二度使って、３＊７，３＊１１にしてみると、２１と３３で丁度５４です。
これで終わりです。

------------------------------

二つの数の和が、５４ですから、二回使える数は、１１は見ただけで無理、７も、１１がすでにあるので、二回使うと、７＊７＝４９となって、大きくなりすぎるので、結局、二回使う数は、３しかないということになるのです。

素因数を二回使わねばならないと分かった時点で、５４を、２と３で素因数分解するまでもなく、７と１１は、５４に比べ、あまりに大きな数なので、残るのは３となるのです。

------------------------------

和が５４でなく、もっと大きな数の場合、７か１１で割って見ることは重要です。７か１１で割れれば、二つの数は、どちらかの数を二回使っているということが分かるからです。

例えば、和が７１４などになると、これは、７か１１でまず割って見ることです。７で悪と割り切れて、７＊１０２となります。しかし、１１では割り切れません。これは、二つの数で、７をそれぞれ使っているということを意味します。

そこで１０２を考え、また７と１１で割れるかどうか確認します。今度はどちらも割れません。しかし、３だと割り切れ、３４になります。つまり、３を二つの数で使っているのです。

二つの数は、３＊７，３＊７＊１１という形をしている可能性があるのです。しかし、前は２１，後は２３１で、合計しても、２５２でたりません。

２５２は、７１４の大体、１／３です。ということは、どちらか二つの数の一方に３をかけると、うまく、目的の数になる可能性があるのです。それは、多分、３＊７，３＊３＊７＊１１ではないかと考えます。前は２１，後は、９＊７７＝６９３で、合計は６９３＋２１＝７１４で合います。

二つの数は、３＊７＝２１と、３＊３＊７＊１１＝６９３となります。こういう計算の時は、共通素因数を見つけるため、素因数で割ってみるというのは良い方法です。

しかし、今回の問題では、和が５４なので、素因数３，７，１１を考えただけで、７や１１が二回使われて、共通素因数になっているのは無理だと分かるのです。

kony0 · Answer

求める数をA,Bとおき、その最大公約数をGとおくと、
A=Ga,B=Gb（a,bは互いに素な（１以外に公約数を持たない）整数）とかけます．

G(a+b)=54, Gab=231

ここで、１つ定理。
「a,bが互いに素であるとき、a+bとabも互いに素である。」ことがわかっています。

ということは、Gは54,231の最大公約数であるから、G=3
ということで、a+b=18, ab=77
あとは因数分解をする要領で、aとbは7と11であることがわかります。

よって、求める数は、3*7=21と3*11=33（答）

さて、定理の証明ですが、これは背理法を使う必要があります。

a+bとabが1以外の公約数を持つと仮定すると、
ある素数pを用いてa+b=pm, ab=pn と書けます。
abの積が素数pの倍数なので、a,bの少なくとも１つはpの倍数でなくてはなりません。
ここでたとえばaがpの倍数であると仮定すると、a=pa'
これをa+b=pmに代入すると、b=p(m-a')

ということは、a,bがともにpの倍数であり、これはa,bが互いに素であるという条件に矛盾する。

したがって、a+b,abは互いに素である。（証明終）

eatern27 · Answer

2つの正の整数をA,B(A<B)、最大公約数をｎとおくと、
AもBもｎの倍数ですからA＋B＝５４もｎの倍数です。
ＡＢ＝231はｎの倍数だから、
ｎは231と54の公約数となります。
231と54の公約数は１と３だから、ｎ=1 or 3ですが、
明らかにｎ≠1です。
ｎ=3の時は
Ａ＝3*7＝21、Ｂ＝3*11＝33と、Ａ＝3、Ｂ＝3*7*11が考えられますが、
後者は明らかに不適で、前者はＡ＋Ｂ＝54となるので、
21と33が答えになります。

liar_adan · Answer

解き方としては考えていらっしゃる通りです。
ただ、解説の中にはちょっとした機転みたいな部分が
含まれています。

まず、3,7,11だけでは、足して54になる組み合わせはないのは簡単にわかります。
(組み合わせとしては3通りしかないから)
「だから、どれか重複して使われる因数があるはずだけど…。
そういえば、同じ因数を持つ数どうしを足し合わせると、
和も同じ因数を持つはずだな。
54を見てみると、因数は2と3しかないぞ。
2は使われてないから、重複して使われる因数は3にちがいない。
3とほかの因数を掛け合わせて、21,33。ちょうど条件に合う。
答えはこれだ」
という過程をとって、ちょっとだけ探すのが早くなります。

整数の約数・倍数の問題

求める数をA,Bとおき、その最大公約数をGとおくと、

2つの正の整数をA,B(A<B)、最大公約数をｎとおくと、

解き方としては考えていらっしゃる通りです。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング