😊出会いの泉😊

正の整数 n について
(109*10^n -1)/9
は、かならずしも合成数とはかぎりません。

さて、どうしてでしょうか？

[前者]
分子が3339,33399,333999,3339999,…のようになる

n=3mのとき
分子が333999,333999999,333999999999,…のように3m+3桁だから
333で割り切れ、333÷9=37なので与式は37で割り切れる

n=3m-1のとき
分子は33399,33399999,33399999999,…だから
与式は3711,3711111,3711111111,…のようになり
全桁の合計が3の倍数だから3で割り切れる

n=6m-2のとき
分子は3339999,3339999999999,3339999999999999999,…のようになり
3339999÷13=256923、999999÷13=76923だから
分子÷13は256923,256923076923,256923076923076923,…となり分子は13で割り切れる
そして13は分母の9と互いに素だから与式も13で割り切れる

n=6m-5のとき
分子は3339,3339999999,3339999999999999,…のようになり
3339÷7=477、999999÷7=142857だから
分子÷7は477,477142857,477142857142857,…となり分子は7で割り切れる
そして7は分母の9と互いに素だから与式も7で割り切れる

まとめ
n=3mのとき37で割り切れ、
n=3m-1のとき3で割り切れ、
n=6m-2のとき13で割り切れ、
n=6m-5のとき7で割り切れるから
常に合成数。

[後者]
n=136のとき素数という反例があるから合成数とは限らない。

素晴らしいです。

なおネタ元は以下です。
https://oeis.org/A112386

追伸：
https://oeis.org/A107612
こちらも、参考にしました。

A112386はなぜこんなにちょっとしかデータがないんでしょうね。
せっかく37の例を載せているんだから
251,26111,271,281,29111111,3011,311,3211111111111111111111111111111111111,34111111,3511,361111,-1
ぐらい載せればいいのに。
（先頭の3行のところではなくLINKSにある表のことです）
ちょっと調べてたくさん追加してみようかな。

正攻法で真面目に素因数分解をしていくと
56111…11
(505*10^n -1)/9
での素数探しで計算量が爆発するのではと
危惧いたします。

以前あった 381111…… の話かと思ったら、今回は 371111…… なのですね。

http://shochandas.xsrv.jp/mathbun/mathbun1315.html

381…1
は個人的は未解決だったのでした。
これは
(343*10^n -1)/9
ですが

（1）n ≡ 0 (mod 3)
のときには、
n = 3*k
とおいて
343 = 7^3
に留意すると
((7*10^k)^3 -1^3)/9
ですから、分子は（3乗−3乗）の形となり
因数分解できることから
合成数でありそうです。

（２）n ≡ 1 (mod 3)
のときには
381, 381111, 381111111……
などですから
３の倍数です。

（３）n ≡ 2 (mod 3)
のときには
どうしたものでしょうか？

あっそうですね。

（３）n ≡ 2 (mod 3)
ということは

3811, 3811111, 3811111111
ですが、
3811 は　37 の倍数、
111 は　37 の倍数ですね。

(a10^n-1)/9とかa10^n-1にしたらどうでしょう。

aは2m,2m+1とか、3m,3m+1,3m+2とか、10m,10m+1,10m+2,10m+3,10m+4,10m+5,10m+6,10m+7,10m+8,10m+9なんかどうでしょう・・・・・

一応言い出しっぺなので、形だけでもなんとか・・・・・

１．a=10mとすると、(mは自然数）
a10^n-1=10m10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9
11・・11を考えると1がn+1並んだ数なので、n+1が合成数なら、かならず割れる。
n+1=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、n+1が偶数なら、11の倍数。
n+1が3の倍数なら、111(=3x37)の倍数。
n+1が5の倍数なら、11111(=41x271)の倍数。
n+1が7の倍数なら、1111111(=239x4649)の倍数。
n+1が11の倍数なら、11111111111(=21649x513239)の倍数。
n+1が13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m-1)10^(n+1)は、(m-1)x2^(n+1)x5^(n+1)
したがって、
n+1が偶数なら、m-1は11の倍数なら、a10^n-1は11の倍数。
n+1が3の倍数なら、m-1は3か37の倍数なら、a10^n-1は3か37の倍数。
n+1が5の倍数なら、m-1は41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略

２．a=10m+1とすると、(mは自然数）
a10^n-1=(10m+1)10^n-1=m10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると1がn並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、m10^(n+1)は、mx2^(n+1)x5^(n+1)
したがって、
nが偶数なら、mは11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略

３．a=10m+2とすると、(mは自然数）
a10^n-1=(10m+2)10^n-1=(m+1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると1がn並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m+1)10^(n+1)は、(m+1)x2^(n+1)x5^(n+1)
したがって、
nが偶数なら、(m+1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略

> "Dengan kesaktian Indukmu"さんが書かれました:
> 正攻法で真面目に素因数分解をしていくと
> 56111…11
> (505*10^n -1)/9
> での素数探しで計算量が爆発するのではと
> 危惧いたします。

A069568;
によりますと５６の後に1が18470個も続くようです。

"GAI"さんが書かれました:

> A069568;
> によりますと５６の後に1が18470個も続くようです。

わあっ！！
A069568
にはちやんと 38111…111
について も 触れてあるのですね！！
見落とし、恥ずかしいです。

私は次に挙げる「模範解答」をみていて
意味がわからずに難儀していたのでした。

http://bxmo.org/problems/bxmo-problems-2015-zz.pdf

3乗マイナス3乗だと気がつくことで
個人的には納得したのですが
いまだにこの模範解答の筋立ての意味を
つかみかねています。

４．a=10m+rとすると、(mは自然数、rは3,4,5,6,7,8,9のいずれか）
a10^n-1=(10m+r)10^n-1=(m+r-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると1がn並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(m+r-1)10^(n+1)は、(m+r-1)x2^(n+1)x5^(n+1)
したがって、
nが偶数なら、(m+r-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+r-1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+r-1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略

５．a=10m+sとすると、(mは自然数、sは1,2,3,4,5,6,7,8,9のいずれか）
a10^n-1=(10m+s)10^n-1=(m+s-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
より、10^n-1は、３の倍数。
また、(m+s-1)10^(n+1)は、(m+s-1)x2^(n+1)x5^(n+1)
より、m+s-1が３の倍数なら、a10^n-1は、３の倍数。

６．a=10mとすると、(mは自然数）
a10^n-1=(10m)10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9
より、10^(n+1)-1は、３の倍数。
また、(m-1)10^(n+1)は、(m-1)x2^(n+1)x5^(n+1)
より、m-1が３の倍数なら、a10^n-1は、３の倍数。

> Dengan さん

まさしく No.1089 と No.1090 で述べられている通りの記述に見えますが、疑問点はどこなのでしょう？

DD++ さん。
ご指摘をありがとうございました。
仰る通りです。

慎重に読み直したところ、私の誤読とわかりました。

正しくは模範解答の PDF にありますとおり、
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 · · · 99
= (7*10^k)^3 −1
which is properly divisible by 7*10^k − 1,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime.

なのですが、私はとんでもない読み間違いを
しておりました。すなわち。
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 · · · 99
= (7*10^k)^3 −1
which is properly divisible by (7*10^k)^3 −1
,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime.　

こんな読み方をしていてはダメダメに決まっています。[ pdf を読みながらノートに写経したときの転記ミスが最初のきっかけです。いったん思い込むと沼にはまる悪い癖が今回も発生しましました。]

DD++ さん、ご教示をありがとうございました。
また、みなさまにつきましては
私からのわけの分からない投稿で
御迷惑をおかけしましたこと、
お詫び申し上げます。

> "らすかる"さんが書かれました:
> A112386はなぜこんなにちょっとしかデータがないんでしょうね。

1331,　13311,　133111,　1331..1
がヤバそうです。
これは
(1198*10^n -1)/9
ですが、任意の正の整数 n について
合成数のような！？
なかなか素数がみつからず
さりとてなぜ合成数になるのか
見通しもつけられず、、、

間違っておりました。よくよく考えると、これでいいと思います。

a10^n-1=(a-1)10^n+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えると1がn並んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以下省略
また、(a-1)10^nは、(a-1)x2^nx5^n
したがって、
nが偶数なら、(a-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(a-1)は3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(a-1)は41か271の倍数なら、a10^n-1は41か271の倍数。
以下省略

また、a-1が３の倍数なら、a10^n-1は、３の倍数。
特に、a-1が9の倍数なら、a10^n-1は、9で割れて、{(a-1)/9}x10^n+(11・・11)となる。

> 1331,　13311,　133111,　1331..1
> がヤバそうです。
> これは
> (1198*10^n -1)/9
> ですが、任意の正の整数 n について
> 合成数のような！？

おそらく
(1198*10^2890-1)/9　（133の後に1が2890個）
が素数だと思います。

しかし、GAIさんが書かれたA069568に118までのデータが載っていますので、
A112386は56で巨大な数になることを考えてもせめて55までは載っていても
いいのに、とは思います。

(追記)
「(1198*10^2890-1)/9は多分素数」の理由
ミラーラビン法で15000以下の素数1754個をそれぞれ底にしてテストしたところ、
すべてパスしましたので、「合成数である確率」は1/10^1000未満となります。

昨日はとんちんかんなことを書いてしまいました。毎度のことですみません。

根本的に、間違いであることを指摘しました。

緑色のうんざりはちべえをクリックしてください。

> "らすかる"さんが書かれました:
> おそらく
> (1198*10^2890-1)/9　（133の後に1が2890個）
> が素数だと思います。

> 「(1198*10^2890-1)/9は多分素数」の理由
> ミラーラビン法で15000以下の素数1754個をそれぞれ底にしてテストしたところ、
> すべてパスしましたので、「合成数である確率」は1/10^1000未満となります。


らすかるさん。検証をありがとうございました。
確率的素数ということですね。

一点、質問をさせていただきたく思います。
ミラーラビンの底には素数をとるのが良いのでしょうか？　確率の評価に影響をあたえますか？