n：自然数
X(n)=(10^n)-1
のとき、
X(n)/{X(5)^2}が割り切れるときのnを求めよ。
おそら条件を満たすnは無数にあると思うので、一般化して頂ければ問題ありません。計算過程もいただけると嬉しいです。どうぞよろしくお願い致します。
No.2
9
1
60pt
X(n)はX(n)=999..99と9がnけた並ぶ数を返してくれる関数なのを確認しておきます。ちょっと試してみればわかりますね。
とりあえず式を変形してみましょう。注目している式をZ(n)とします。
つまり、この問題は「111...11(nケタ)という数が11111^2と9で割り切れるnを求めよ」という問題に帰着します。
11111と9は互いに疎ですから、111...11(nケタ)が9で割り切れ、かつ11111^2でも割り切れればよいわけです。
9で割り切れることの判定法は有名なのかちょっとわからないのですが(知らない場合以下がわかりやすいでしょうか: http://www.shinko-keirin.co.jp/kosu/mathematics/qanda/01-05.html http://plaza.rakuten.co.jp/kuragebiyori/diary/200712090000/ )、各桁の数字をすべて足したものが9の倍数であればいいわけですから、つまり桁数が9の倍数であればいいことになります。自然数mを使ってn=9aと表せればよいわけです。
まず11111で割り切れる条件を考えましょう。これは筆算をやってみると、nが5の倍数であればいいことがわかると思います。下の図の商と割る数をかければ割られる数に戻るのがわかるでしょう。
421
377
100001.......0100001
--------------------------
11111 ) 1111111111.......1111111
この商は、元の数が5b桁だったとすると{1+100000+100000^2+...+100000^(b-1)}と書けます。b=1やb=2で確かめてみるといいでしょう。
さて、11111^2で割り切れる条件を考えているのですから、この商がもう一度11111で割り切れればよいわけです。
とりあえず小さいbについてこの{...}を11111で割ってみると、b=1のとき余りは1、b=2のとき余り2、b=3のとき余り3となります。どうも余りがbと等しいように見えますね。これは実際成り立っていることが次のようにして示せます(もちろんb=11112とかのときは余りは11112ではなくて1になるわけですが)。
100000は11111で割ると余りが1になるので、整数kによって 100000=11111k + 1 と表せます。なので一般に自然数mについて、10000^m=(11111k + 1)×(11111k + 1)×...×(11111k + 1) = (11111の倍数) + 1 となりますから、10000^mを11111で割った余りも1となります。ですから{1+100000+100000^2+...+100000^(b-1)}を11111で割った余りは{1 + 1 + 1 + ... + 1}となります（ただしb<11111の場合）。もともと{}内の項数がb個でしたから、これはつまりbそのものです。b≧11111の場合はb={1 + 1 + 1 + ... + 1}を11111で割ったあまりとなります。
つまり、bが11111の倍数であれば{1+100000+100000^2+...+100000^(b-1)}は11111で割り切れる、すなわち111..11(5bケタ)は11111^2で割り切れるというわけです。n=5bでしたから、つまりnが5の倍数で、かつ11111の倍数でもあればいいということになります。
nが5、9、11111の倍数であればいいわけですから、(5、9、11111は互いに疎なので)mを自然数として
n=(5×9×11111)m
が求める条件となります。ちなみに「自然数」に0を含めた時もこの条件は成り立ちます。
No.1
79184
10pt
n=2*5*9*41*271*N Nは自然数です。
最小のnは999990です。その時のX(n)/{X(5)^2}の値は２３０万桁でした。
略解はこうなります。
まず、
X(5)=99999=9*41*271
初めに、X(n)=(10^n)-1でX(n)がf(5)で割り切れるためにnが5の倍数かつ2の倍数であることを導きます。
n=2*5*pとすると
X(n)/{X(5)^2}=(10^(5p)-1)(10^(5p)+1)/(10^5-1)^2
分子の第一項目は(10^5-1)で割り切る。よってこの条件下でpを求めます。
また、X(n)は9,41,271で割り切れることが必要です。
それは下記のように考えてください。
フェルマの小定理でs^p-sは(s,p)=1であればpで割り切れます。
即ち(s,p)=1とはxとpが最大公約数が１を意味します。互いに素ということです。
ここでs=10^5とします。
p=9*41*271の時、(s,p)=1です。したがってs^9*41*271-sは9*41*271で割り切れます。
s^p-s=s^p-1-(s-1)=s^p-X(5)で,これはpで割り切れます。
推論に飛びがありますが、こんな流れだと思います。
> 最小のnは999990です。その時のX(n)/{X(5)^2}の値は２３０万桁でした。
ありがとう。
けど、この一行で違うと確信しました。
nが999990のとき、すなわちX(999990)は99万9990桁と思います。それを{X(5)^2}で割るのですから、X(n)/{X(5)^2}の桁数はもっと少ないです。
ただ、nが999990のとき割り切れることは確認しました。しかし最小ではない気がしています。ポイントは送ります。本当にありがとう。
No.2
91
ここでベストアンサー
60pt
X(n)はX(n)=999..99と9がnけた並ぶ数を返してくれる関数なのを確認しておきます。ちょっと試してみればわかりますね。
とりあえず式を変形してみましょう。注目している式をZ(n)とします。
つまり、この問題は「111...11(nケタ)という数が11111^2と9で割り切れるnを求めよ」という問題に帰着します。
11111と9は互いに疎ですから、111...11(nケタ)が9で割り切れ、かつ11111^2でも割り切れればよいわけです。
9で割り切れることの判定法は有名なのかちょっとわからないのですが(知らない場合以下がわかりやすいでしょうか: http://www.shinko-keirin.co.jp/kosu/mathematics/qanda/01-05.html http://plaza.rakuten.co.jp/kuragebiyori/diary/200712090000/ )、各桁の数字をすべて足したものが9の倍数であればいいわけですから、つまり桁数が9の倍数であればいいことになります。自然数mを使ってn=9aと表せればよいわけです。
まず11111で割り切れる条件を考えましょう。これは筆算をやってみると、nが5の倍数であればいいことがわかると思います。下の図の商と割る数をかければ割られる数に戻るのがわかるでしょう。
100001.......0100001
--------------------------
11111 ) 1111111111.......1111111
この商は、元の数が5b桁だったとすると{1+100000+100000^2+...+100000^(b-1)}と書けます。b=1やb=2で確かめてみるといいでしょう。
さて、11111^2で割り切れる条件を考えているのですから、この商がもう一度11111で割り切れればよいわけです。
とりあえず小さいbについてこの{...}を11111で割ってみると、b=1のとき余りは1、b=2のとき余り2、b=3のとき余り3となります。どうも余りがbと等しいように見えますね。これは実際成り立っていることが次のようにして示せます(もちろんb=11112とかのときは余りは11112ではなくて1になるわけですが)。
100000は11111で割ると余りが1になるので、整数kによって 100000=11111k + 1 と表せます。なので一般に自然数mについて、10000^m=(11111k + 1)×(11111k + 1)×...×(11111k + 1) = (11111の倍数) + 1 となりますから、10000^mを11111で割った余りも1となります。ですから{1+100000+100000^2+...+100000^(b-1)}を11111で割った余りは{1 + 1 + 1 + ... + 1}となります（ただしb<11111の場合）。もともと{}内の項数がb個でしたから、これはつまりbそのものです。b≧11111の場合はb={1 + 1 + 1 + ... + 1}を11111で割ったあまりとなります。
つまり、bが11111の倍数であれば{1+100000+100000^2+...+100000^(b-1)}は11111で割り切れる、すなわち111..11(5bケタ)は11111^2で割り切れるというわけです。n=5bでしたから、つまりnが5の倍数で、かつ11111の倍数でもあればいいということになります。
nが5、9、11111の倍数であればいいわけですから、(5、9、11111は互いに疎なので)mを自然数として
n=(5×9×11111)m
が求める条件となります。ちなみに「自然数」に0を含めた時もこの条件は成り立ちます。
完璧だと思います。熟読致しました。
本当にありがとうございました。
いるか贈ります。
Hyperion64
2009/08/11 16:38:01
yoshifuku
Moonbal_Sunbal
1
1
1
完璧だと思います。熟読致しました。
本当にありがとうございました。
いるか贈ります。