- ベストアンサー
1111111の素因数分解
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (5)
- sunflower-san
- ベストアンサー率72% (79/109)
回答に画像を添付した者です。 画像の事実の特別な場合(n = 2)、 N(2, p) = 2^p - 1 なので、 「pが素数ならば 2^p - 1 の素因数はpで割って1余る」 ということがわかります。 このことを使うと、たとえば以下のように 2^11 - 1 = 2047 の素因数分解をすぐに導くことが出来ます。 素因数は11で割って1余る奇数なので、22で割って1余る数です。 そのような素数は、 23, 67, 89, ....ですが、とりあえず小さい方から試しに割ってみると、 2047 ÷ 23 = 89 と一発目でみごと割り切れ、素因数分解 2047 = 23 × 89 が得られました！ 奇素数 3, 5, 7, 11, 13, 17, 19, 23, ... で順に割れるかどうか試す地道な計算に比べれば、かなり計算量が減らせますね。 また、同様にN(10, 5) = 11111 の素因数分解も、素因数が全て5で割って1余る(奇)数とわかるので、10で割って1余る素数を書き出していくと、 11, 31, 41, ... ですが、割り算を試すこと3回目で、 11111 = 41 × 271 という素因数分解が得られます。 これも地道に素因数を探す場合、 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ... となかなか面倒ですから、画像の事実を使うと効果的ですね。
- sunflower-san
- ベストアンサー率72% (79/109)
説明不足ですみません。 以下のような一般的な事実の、p = 7, n = 10 の場合を用いています。 画像ファイルの大きさの制限により、2回に分けて投稿させていただきます。 まず(1/2)です
- sunflower-san
- ベストアンサー率72% (79/109)
9991のように簡単な素因数分解の方法は思いつきませんでしたが、少し調べる手間を減らすことは可能です。(画像を参照してください)
お礼
ご回答ありがとうございます。割る素数の候補を減らす、というのは考えませんでした。かなり効率化できたと思います。
補足
１点お聞きしたいのですが、すべての素因数がmod7で1と結論できるのはなぜでしょうか。10^7－1≡3^7－1≡2^3・3－1≡2、10－1≡2から、1111111≡1なのはわかりますが、それで素因数が≡1といえるわけではないようです。（反例3×5≡1(mod7)） 呑み込みが悪くて申し訳ありません。
- bran111
- ベストアンサー率49% (512/1037)
1111111=239×4649=x^2-y^2=(x+y)(x-y) x+y=4649 x-y=239 x=2444 y=2205 1111111=2444^2-2205^2 2444^2-2205^2=5973136-4862025=1111111 OK?
補足
質問の仕方が悪くて申し訳ありませんでした。No.1の方に補足させて頂いたとおりです。
- mshr1962
- ベストアンサー率39% (7418/18948)
x^2-y^2=(x+y)(x-y) x+y=4649 x-y=239 だから 2x=(x+y)+(x-y)=4649+239=4888 x=2444 y=4649-x=4649-2444=2205 となるので 2444^2-2205^2=1111111
補足
質問の仕方が悪くて申し訳ありませんでした。4649で割れることを前提とせず単に、「1111111を素因数分解せよ」と問われたときにどう工夫できるかをお聞きしたかったものです。9991の場合は10000に近い数なので100^2-3^2の変形に気づくのが容易です。同様に1111111というビジュアルや特徴に着眼した変形で分解する術がないかをお聞きしています。
関連するQ&A
- 素因数分解
素因数分解はわらずとも解に至ります。それをどうしたら、みなさんにお伝えできるか 数学教育協議会等にも顔を出したり、ずいぶん前から、たくさんの新しい事を創り、双子素数などは、 ペア素数の定理として、すべて一括に実証されます、素因数分解などは、桁数は関係ありません。素因数分解の世界記録、現在NTT総合研究所とドイツのボン大学とスイスのローザンヌ大学とフランス、オランダの研究機関が共同で３年もかかってしまう、わずか２３２桁です、これは、すべて、割るがベースにある からです。割るを、使わずとも、解に至ります。どうして、理解しようとしないのか、わかりません。 古代バビロニアの人々ですらできたのです。４０００年も前です、基本は考え方です。難しく、難解な高等数学入りません。平方根を厳密解を求める、つまり、開平がちゃんと、理解でき、従来の２個ずつ、開くことを拡張して、８個、とか、１６個いっぺんに開く方法もあるので、そういう工夫をすれば、よい。 あとは、大きい数値を、扱えるかどうかです。つまり素因数分解は、one-way-function出はありません。２３２桁も数分でしょう。
- 締切済み
- 数学・算数
- 素因数分解はなぜ困難？
今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。
- ベストアンサー
- 数学・算数
- 素因数分解と約数の個数
こんばんわ。早速ですが、質問に移らさせていただきます。 例えば、36=2の2乗×3の2乗、と素因数分解できます。このように、素数の積にする事により 約数の個数が解ります。この場合、 (指数+1)×(指数+1)が、約数の個数になります。 このような公式を学んだところなのですが、具体的な整数でいろいろと試してみましたが、なぜ、そのような公式になるのかが、検討もつきません。何か、手がかりがあれば、よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- どんな素因数も一瞬で分解できる人がいたと思いますか
人類史上どんな素因数も一瞬で分解できるという人はいたことありますか？ (大量の素因数を持つものについて、分解したことを私たちに証明するためにそれらの数字を書き出す作業時間は考慮しない。) 私自身は今現在はいないという立場であります。 理由としては、RSA暗号など素因数を利用した高度な暗号を解読したとのことで不正アクセスの罪で捕まった人の中で「私はどんな素因数も一瞬で分解出来る自分の脳に酔って魔が差したんだ」といった供述をした人を古今東西で見たことがないからです。 それぞれの分野には秀でた人がいるものですが、トップと次席、それ以降に続いていく人達の実力差は連続的なものです。 油断してれば上位の者は下位の者追い抜かされ序列が塗り替わるということもあるでしょう。 ノーベル賞を取るような人についてだって、実は陰ではもっと前から同じような実績を残していたという事実が往々にして科学史にはあります。 ようするにどんな分野のものさしで測っても私たちはどっこいどっこいの者同士の連続体でしかないのです。ある人を除き。 私はそれこそ「あらゆる素因数を一瞬で分解できる人」と考えます。 リーマン予想も肯定的に解決されてないなかでその能力は人知を超越しているというほかありません。 コンピュータでも最低で一年以上かかるとされる３００桁の数字の素数判定ないし素因数分解も、一瞬で。もうラマヌジャンがすごいとかいうレベルではありません。 そういう人は「素因数を分解する能力」というものさしで測ったとき、まさにその他の全人類から群を抜いているということになるでしょう。 その次席の人がいくら頑張って努力しても、連続的でないその能力差という壁は越えられない ・・・そういう人、「ある分野のものさしで測ったとき絶対的にずば抜けている人」を、ちなみにですが、私は真の天才と呼んでいます。 その頭脳の稀少性は数理科学者の権威とも比較にもならないでしょう。 それだけのギフトの持ち主がいたらならば、自惚れもするでしょうよ。自分の能力を試してみないわけにはいかなくなるでしょうよ。 そういうことが私の狭い見聞のもとでは今まで犯罪史になかったと推測されるので、 そのようなことで己惚れるだけの能力を持っていた人が過去いなかったと考えるのです。 質問に至る背景説明が長くなってしまいましたが、 貴方はそのような人がいたと思いますか？いなかったと思いますか？
- ベストアンサー
- 数学・算数
- 因数と素因数およびそれを用いた証明
他の方の質問に回答しているやりとりの中でどうしても腑に落ちないことがあり、これ以上その方の回答欄に書くわけにもいかないと思い質問します。 「素因数」…ある整数の約数である素数のこと。 「因数」…一つの数または式がいくつかの数または式の積によって形成されている場合、その個々のその個々の数や式、因子。 (いずれも広辞苑より) とあります。 この説明を読む限りでは、素因数⊂因数だと思います。つまり、整数が因数の積で表される時、その因数が素数の時は特に素因数と呼ぶ、と。 ということは、証明においてある整数の因数全体で成り立つことが示せれば、その整数の素因数でも成り立つことは自明だと思うのですが、違うのでしょうか？ また、ほとんどの参考書および教科書では、 「ある整数Aと１を除く自然数ｍにおいて、A^3がｍの倍数⇔Aがｍの倍数」であることを自明のこととして扱っています(mが素数かどうかに関わらず)。事実私もそうでした。しかし、自明ではないという意見もあるようです。どちらなのでしょうか？ 自明であるという意見の方はその理由を、自明でないと言う方は反例をあげて下さい。 長文になりましたが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 因数分解について教えて下さい。
数学が苦手な中3です。 因数分解でわからないところがあります。 [x^2+2ax+a^2とx^2-2ax+a^2の公式]という項目にある 「x^2+6x+9を因数分解しなさい」という問題はなんとか理解できたのですが、 「4x^2-12x+9を因数分解しなさい」という問題が理解できません。 答えには、 4x^2-12x+9 =(2x)^2-2×3×(2x)+3x^2 =(2x-3)^2 とあるのですが、なぜこうなったのか全く理解できません。 解き方を教えて下さい。 それと、因数分解の「式の利用」というところの、 問１「次の■に当てはまる数を書き入れ、計算の答えを求めろ」 101^2=(100+1)^2 =100^2+2×■×■+■^2 =■ 問２「情報公式や因数分解を利用して、次の計算をしろ」 (1)99^2 (2)51×49 (3)81^2-80^2 の解き方がわかりません・・・。 最後に、「6、7、8のような連続する3つの整数では、中央の数の2乗から1をひいた差は、残りの2数の積に等しくなる。このことを証明しろ」と言う問題は、単純に 7^2-1=48 6×8=48 よって、中央の数の2乗から1をひいた差は、残りの2数の積に等しくなる。 これで良いのでしょうか？ ご教授のほど、よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
遅くなってすみません！ひととおり読みました。一応理解できたと思います。フェルマーの小定理は大学で学んだ以来で懐かしい気持ちでした。今回みたいな素因数分解ではもろ当てはまる性質ですね。1(mod7)で素因数候補を限定すれば確かに楽になります。いい方法を知りました。ありがとうございます。