最大公約数や最小公倍数をだす時になぜ、素数で割るのか？

最大公約数や最小公倍数をだすときに、素数で割っていきますが
なぜ、素数でなければならないのですか？

No.5 回答者： miku0004 回答日時： 2001/08/25 02:25

質問者の方がどのくらいのレベルなのかが把握できない為、一応基礎から全て答えますので、わかるところは適当に読み飛ばしてください。

「素因数分解」がわかれば、ここはすっ飛ばしてください。

まず、素数というものは「その数か1でしか割れない数(自然数)」です。
例：2,3,5,7,11,13,17,19,23,29,31,…

全ての自然数は素数の掛け算で表す事ができます。
なぜなら、ある自然数が素数でなければ、その数は「その数か1以外でも割れる数」であり、割れる＝積の形で表せることであり、さらにその積となった数字のひとつひとつが素数でなければまた同じく積の形に表せて…
最終全て素数の積になるでしょう。
例：ある自然数30について
30は2で割れる→30＝2×15
15は3で割れる→30＝2×(3×5)
2,3,5は素数だな→30＝2×3×5はこれ以上分解できないな⇒終了

次に最大公約数について

「共通に割ることができる数で最大のもの」
例：18,24の場合⇒最大公約数は6(18÷6＝3,24÷6＝4)
ちなみに
18＝6×3
24＝6×4
と書くと、両方の式に共通の"6"が掛け算されていることがわかります。
このことから共通の積があればその数で両方とも割り切れ、共通の積で最大のものが最大公約数になる、ということは分かっていただけると思います。

で、本題の、なぜ素数で割るのか、ということに関してお答えすると、答えは「間違いがないから」です。

先の説明から素因数分解をすると、これ以上割れない数(素数)ばかりの積の形で表せます。
ここで大事なのは「誰がやっても、積でこれ以上分解できない同じ形」になることです。
例：180,600
180＝2×2 ×3×3×5
600＝2×2×2×3 ×5×5
誰がやってもこうなります。

で、最大公約数を求める時は、この中から共通の積で最大になる数を求めればいいわけです。
ちなみに素数で分けずに適当な積で分けると、
180＝4×3×15
600＝2×5×6×10
などとなり、さっぱり分かりません。

上の素因数分解の形でみると、
2は180では2つ、600では3つある、それじゃあ、共通にとれる2は2つだけだね。
3は180では2つ、600では1つある、それじゃあ、共通にとれる3は1つだけだね。
5は180では1つ、600では2つある、それじゃあ、共通にとれる5は1つだけだね。

180＝(2×2×3×5)×3
600＝(2×2×3×5)×2×5

最大公約数は2×2×3×5＝60だ！
てな具合に間違いが少なく計算していくことができます。

長すぎてごめんなさい。
こんな書くつもりもなかったし、書く必要もないかと思ったけど、途中で引っ込みがつかなくなってしまいました。

この回答へのお礼

ありがとうございました。
僕は小学５年生です。
とっても良くわかりました。僕たちは今、約数や公倍数を習っているのですが
素数という言葉も習ってないし、割り算の反対のような式で、2つの数の
最大公約数や最小公倍数の出し方も習っていません。
それで　その出し方は親に聞いたのですが、なぜ素数でなければならないかが
よくわからなかったのです。
でも、よくわかりました。

お礼日時：2001/08/25 09:13

No.4 回答者： wildcat888 回答日時： 2001/08/24 23:25

　（（　素人ですが　））

　素数でなくてもかまわないのではないでしょうかね。
例えば、１８，１２については，

　「どちらも掛け算の６の段にあるので」

　　・・・・・・・
と、ひらめいたら、

　　　　１８＝６ｘ３
　　　　１２＝６ｘ２

ですから、３と２にはもう（２以上の）共通の約数はありませんので，

　　　　最大公約数　　６
　　　　最小公倍数　　６ｘ３ｘ２＝３６

と、求められます。

　共通の約数がうまく見つかればいいのであって，
「必ず素数で割っていく」ということをしなくても，
このように最大公約数，最小公倍数は，正しく，求められます。

　普通，素数で割っていって最大公約数，最小公倍数を求めるのは，

　　　　　　　　　・・・・・・・・・・・・・
　　　　『うまく，ひらめかなくても，だれでも必ずできる』

からだと思います。２で割っていって，もう２で割れなくなったら，
次に３で割っていって・・・と，じゅんじょよくやっていけば，
見落とし（割りのがし？）がありません。

　素人は素数で割ることについて，そんなふうに思うのですが。
　
　

No.3 回答者： taro1122 回答日時： 2001/08/24 22:35

例えば

36=2の2乗×3の2乗　となります。
素数の積にする事により　約数の個数が解ります。
この場合
　(指数+1)×(指数+1)が　約数の個数になります。
ある程度大きな数字の約数の個数を求めるときには
便利ですよ。

この回答へのお礼

ありがとうございました。
僕は小学５年生です。
とっても良くわかりました。僕たちは今、約数や公倍数を習っているのですが
素数という言葉も習ってないし、割り算の反対のような式で、2つの数の
最大公約数や最小公倍数の出し方も習っていません。
それで　その出し方は親に聞いたのですが、なぜ素数でなければならないかが
よくわからなかったのです。
でも、よくわかりました。

お礼日時：2001/08/25 09:21

No.2 回答者： Zincer 回答日時： 2001/08/24 21:57

はじめましてZincerです。

数学的な証明は専門家に任すとしまして、
こんなやつのことですよね、

a ) A0 B0
　----------
b ) A1 B1
　----------
c ) A2 B2
　----------
　　A3 B3

最大公約数　a×b×c
最小公倍数　a×b×c×A3×B3

別に素数でなくても構いません。例えば上の場合A0とB0を見てa×bが公約数であることが思いついた場合

a×b ) A0 B0
　　　----------
　c ) A2 B2
　　　----------
　　　　A3 B3

と、成るだけですね。
しかし、注意しないといけないのは本当にA3とB3に公約数が無いかどうかです。
ある場合には答えが違いますので、念のために素数で考えた方が無難でしょう。

この回答へのお礼

ありがとうございました。
僕は小学５年生です。
とっても良くわかりました。僕たちは今、約数や公倍数を習っているのですが
素数という言葉も習ってないし、割り算の反対のような式で、2つの数の
最大公約数や最小公倍数の出し方も習っていません。
それで　その出し方は親に聞いたのですが、なぜ素数でなければならないかが
よくわからなかったのです。
でも、よくわかりました。

お礼日時：2001/08/25 09:22

No.1 回答者： ymmasayan 回答日時： 2001/08/24 21:42

公倍数や公約数を求めるためにはそれぞれの数がどんな数の掛け算の形で表されるかを知る必要があります。

例えば３６０は
３６０＝２×２×２×３×３×５に分解します。
素数でない数で割る事はまだ分解しきれていないことになります。
完全に分解しきるには素数で割っていくべきなのです。

この回答へのお礼

ありがとうございました。
僕は小学５年生です。
とっても良くわかりました。僕たちは今、約数や公倍数を習っているのですが
素数という言葉も習ってないし、割り算の反対のような式で、2つの数の
最大公約数や最小公倍数の出し方も習っていません。
それで　その出し方は親に聞いたのですが、なぜ素数でなければならないかが
よくわからなかったのです。
でも、よくわかりました。

お礼日時：2001/08/25 09:22