５桁×５桁＝１２３４５６７８９

○○○○○×○○○○○＝１２３４５６７８９
という問題があるのですが、○○○○○にはどの数字が入るのでしょうか？
気になっています。どなたか教えてください。

No.3 ベストアンサー 回答者： siegmund 回答日時： 2001/12/26 00:08

> どうしたら答えが出せるんですか？

基本的には素因数分解しかないんじゃないかと思います．
123456789 が９(=3^2)で割れるのはすぐ見えます．
1+2+3+4+5+6+7+8+9=45 ですから，有名な判定法です．
123456789÷9 = 13717421
ですが，これの素因数分解はちょっと面倒です．
√13717421 ≒ 3703.7
ですから，コンピューター使うなら 3703 以下の素数で次々割ってみればよいわけで，
この程度でしたらあっという間にできるでしょう．
123456789 = 3×3×3607×3803
が素因数分解で，これから５桁×５桁にするには
(3×3607)×(3×3803) = 10821×11409 にするしかないことがすぐわかります．

一般に，与えられた自然数が素数かどうか判定し，素数でないなら素因数分解する，
というのは大きな数に対しては非常に困難な問題のようです．
この困難さが公開鍵暗号の本質だと聞いています．
最近，何か新しいアルゴリズムの発展があったとどこかで見たか，聞いたかした
覚えがありますが，忘れちゃいました．

この回答へのお礼

丁寧な解説、ありがとうございました。やっと理解できました。

お礼日時：2001/12/26 00:40

No.2 回答者： finalanswer 回答日時： 2001/12/26 00:01

123456789を素因数分解すると 3*3*3607*3803 となります。

したがって、積が123456789となる5桁と5桁の整数の組み合わせは、sinnamonさんが答えたように、10821と11409のみとなります。

この回答へのお礼

【素因数分解】すっかり忘れてました。「はぁ～」と、ただただ感心するばかりです。ありがとうございました。

お礼日時：2001/12/26 00:35

No.1 回答者： noname#2697 回答日時： 2001/12/25 22:47

１０８２１　×　１１４０９　＝　１２３４５６７８９

のようです。

この回答への補足

すごい！
どうしたら答えが出せるんですか？
感激です。

補足日時：2001/12/25 23:08

この回答へのお礼

とっても早いご回答に感謝します。おかげさまでスッキリしました。

お礼日時：2001/12/26 00:34