1111111の素因数分解

質問

1111111という1が並ぶ数の中でも少ない桁数のものが、4649(よろしく)で割り切れることを知り、大変興味深く感じました。そこで1111111=239×4649という素因数分解を工夫してできないかを考えています。イメージ的には、例えば9991の素因数分解なら100^2－3^2と変形することで因数分解公式から103×97と分解できる、という具合です。何卒お知恵拝借いただきたく存じます。

回答No.5

sunflower-san · ベストアンサー

画像ファイルの(2/2)です。

お礼

遅くなってすみません！ひととおり読みました。一応理解できたと思います。フェルマーの小定理は大学で学んだ以来で懐かしい気持ちでした。今回みたいな素因数分解ではもろ当てはまる性質ですね。1(mod7)で素因数候補を限定すれば確かに楽になります。いい方法を知りました。ありがとうございます。

回答No.6

sunflower-san

回答に画像を添付した者です。

画像の事実の特別な場合(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, ...

となかなか面倒ですから、画像の事実を使うと効果的ですね。

回答No.4

sunflower-san

説明不足ですみません。
以下のような一般的な事実の、p = 7, n = 10 の場合を用いています。
画像ファイルの大きさの制限により、2回に分けて投稿させていただきます。

まず(1/2)です

回答No.3

sunflower-san

9991のように簡単な素因数分解の方法は思いつきませんでしたが、少し調べる手間を減らすことは可能です。(画像を参照してください)

お礼

ご回答ありがとうございます。割る素数の候補を減らす、というのは考えませんでした。かなり効率化できたと思います。

補足

１点お聞きしたいのですが、すべての素因数がmod7で1と結論できるのはなぜでしょうか。10^7－1≡3^7－1≡2^3・3－1≡2、10－1≡2から、1111111≡1なのはわかりますが、それで素因数が≡1といえるわけではないようです。（反例3×5≡1(mod7)）
呑み込みが悪くて申し訳ありません。

回答No.2

bran111

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の方に補足させて頂いたとおりです。

回答No.1

mshr1962

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というビジュアルや特徴に着眼した変形で分解する術がないかをお聞きしています。