|
9n の下４桁が 0001 となる最小の自然数ｎの値は？
解答
上記サイト http://blogs.yahoo.co.jp/oka_yadokary/24368860.html より Orz〜
[解答1]
91＝9， 92＝81， 93＝729， 94＝6561，…… だから、下１桁が１になるのはｎが偶数のときなので、n＝2a とおきます。 92a＝(1＋80)a＝1＋aＣ1･80＋aＣ2･802＋aＣ3･803＋aＣ4･804＋………… だから、 aＣ1･80＋aＣ2･802＋aＣ3･803 が 10000の倍数、 80a＋6400･aＣ2＋512000･aＣ3 が 10000の倍数、 80a＋6400･aＣ2＋2000･aＣ3 が 10000の倍数、 a＋80･aＣ2＋25･aＣ3 が 125の倍数、 ａは５の倍数だから、a＝5b として、 5b＋80･5bＣ2＋25･5bＣ3 が 125の倍数、 b＋16･5bＣ2＋5･5bＣ3 が 25の倍数、 b＋8(5b)(5b−1)＋5(5b)(5b−1)(5b−2)/6 が 25の倍数、 ここで、25b(5b−1)(5b−2)/6 は自然数で、25 は約分できないから25の倍数になって、 b＋8(5b)(5b−1)＝25･8b2−39b が 25の倍数、 結局、ｂは 25の倍数になります。 b＝25c とおくと、n＝2a＝2･5b＝2･5･25c＝250c ですので、 最小の自然数ｎは、n＝250 です。 [解答2] uch*n*anさんのコメントより まず，下(m＋1)桁が 00…(０がｍ個)…001 を 「0m1 である」と書くことにします。 9n が 0k-11 となる最小のｎに対して，ａを自然数として，9n＝10ka＋1 と書けます。 明らかに，9c (1≦c≦n−1) を掛けても 0k1 になることはないので，0k1 となる候補は (9n)m です。 そこで，具体的に mod 10000 で調べていくと， 92≡81，(92)m≡(80＋1)m≡512000mＣ3＋6400mＣ2＋80m＋1 初めて 011 となるのは m＝5 で，910≡4000＋400＋1≡4401≡4400＋1 同様の計算で，021 は 5 乗したときが最小で，950≡2000＋1≡2001 同様に，031 となるのも 5 乗したときが最小で，9250≡1≡0001 そこで，答えは 250 になります。 ちなみに，9250≡10001 (mod 100000) なので，この後は 10 乗ずつかな。 ☆ その通りです。 9n が 0k1 となる最小のｎは、k≧3 に対して n＝10k/4 です。 [参考] 9n の下４桁が 0001 となるものが存在する理由 自然数の下４桁は 0000〜9999 の 10000種類だけですので、10001個の数 91，92，93，……，910001 の中には必ず下４桁が同じものがあります。 それを、9a，9b (a＜b) とすれば、 9b−9a＝9a(9b-a−1) が 10000の倍数で、 9a は 10000 と互いに素だから、9b-a−1 は 10000の倍数です。 これは、9b-a の下４桁が 0001 になることを示しています。 また、b−a は 10000以下の自然数ですので、 9n の下４桁が 0001 となるものが n≦10000 の範囲にあります。 同様に、m と 10 とが互いに素であれば、 mn の下４桁が 0001 となるものが n≦10000 の範囲にあります。 更に、 9n の一の位が 1 または 9 であることを考慮すると、 9n の下４桁は高々2000種類ですので、 9n の下４桁が 0001 となるものが n≦2000 の範囲にあります。 また、 92n＝(1＋80)n を２項定理で展開すると 1＋(80の倍数) になり、 92n+1＝9･92n は 9＋(80の倍数) になります。 従って、9n の下４桁は高々 (10000/80)･2＝250 種類で、 9n の下４桁が 0001 となるものが n≦250 の範囲にあります。 ・uch*n*anさんの追加コメ Orz〜
(解法1)は，[解答1]と基本的な考え方は同じですが，n は偶数の後は，
9^n = (10 - 1)^n = (10000 の倍数) - nC3 * 1000 + nC2 * 100 - nC1 * 10 + 1 nC3 * 1000 - nC2 * 100 + nC1 * 10 = (10000 の倍数) から解いていきました。手間はあまり変わらないようです。 (解法2)は，[解答2]です。コメントは文字制限があるので合同式を使いましたが，
合同式になれていない方は， mod 10000 の a ≡ b は，a = (10000 の倍数) + b，の意味 などと思って読んでください。 もやもやしているのは[参考]のような方針でうまくできないかな，ということです。
初等整数論のオイラーの定理を使えば，n が 4000 の約数であることはすぐに分かります。 ただ，そこから 250 に絞り込むのには， [参考]の後半や[解答]のような議論が必要になるように思われ， オイラーの定理を使うメリットがないようです。 ・uch*n*anさんの追加コメ Orz〜
(解法3) オイラーの定理の利用
まず，問題は合同式で書くと，9^n ≡ 1 (mod 10000) となる最小の n を求める， となります。この n に対して，一般に 9^m ≡ 1 (mod 10000) とすると， m = nq + r，0 <= r <= n-1 なので 9^r ≡ 1 (mod 10000) となって， n の最小性より，r = 0，m = nq となります。 つまり，9^m ≡ 1 (mod 10000) となる m は n の倍数，n は m の約数になります。 さて，9，10000 は互いに素なので，φをオイラー関数として，オイラーの定理より，
9^φ(10000) ≡ 1 (mod 10000) φ(10000) = φ(2^4) * φ(5^4) = (2^4 - 2^3) * (5^4 - 5^3) = 4000 9^4000 ≡ 1 (mod 10000) 9^4000 ≡ 1 (mod 625)，(9^2000 - 1)(9^2000 + 1) ≡ 0 (mod 625) 9^偶数 ≡ 1 (mod 10) なので，9^2000 + 1 は 5 の倍数にはなれないから， 9^2000 ≡ 1 (mod 625) また，9^2 ≡ 1 (mod 16)，9^2000 ≡ 1 (mod 16) より，9^2000 ≡ 1 (mod 10000) です。 同様にして， 9^1000 ≡ 1 (mod 10000)，9^500 ≡ 1 (mod 10000)，9^250 ≡ 1 (mod 10000) になります。 さらに，9^奇数 ≡ 9 (mod 10)，9^偶数 ≡ 1 (mod 10) なので，
n の候補は 250 の約数のうち 2，10，50，250 です。そこでこれらをチェックしていくと。 9^2 ≡ 81 (mod 10000) 9^10 ≡ (9^2)^5 ≡ (80 + 1)^5 ≡ 4000 + 400 + 1 ≡ 4401 ≡ 4400 + 1 (mod 10000) 9^50 ≡ (9^10)^5 ≡ 2000 + 1 ≡ 2001 (mod 10000) 9^250 ≡ 1 ≡ 0001 (mod 10000) そこで，答えは 250 になります。 *なはっ...わたしゃ...そのオイラーの定理を使って(逃げの手 ^^;)考えちゃいました...Orz...
9^n-1 が (9+1) を４個持つわけだから...ってことから攻めたんですが...上手くいかず...けっきょく...
フェルマーの小定理使って計算... (*フェルマーの小定理、オイラーの定理に関してはまた「証明欄」にアップしたいと思います...Orz...)
9^φ(10000)≡1 mod 10000
φ(10000)=(2^4-2^3)(5^4-5^3)=8*500=4000 つまり... 9^4000≡1 できるだけ小さい数を探してみる... 4000=2^5*5^3 4000/2=2000 2000/2=1000 1000/2=500 500/2=250 250/2=125 9^125=((9^5)^5)^5=((9049)^5)^5 ≡(4401*4649)^5 ≡(0249)^5 ≡6249 9^250≡(6249)^2 ≡0001 じつは...n は偶数なので...250から探せばよかったわけなんでした...
・わたしの友人からのもの...
1の位より 81^m=10000A+1 m=2n とおける
(81-1){1+81+81^2+……..81^(m-1))=10000A 80で割って 1+81+81^2+……..81^(m-1)=125A 1000は125の倍数だから下3桁が 000,125,250,375,500,625,750,875 になることが必要十分 下3桁のみで考えると 1+81+,,,,,,,,81^4 =805 で、これを繰り返すから、まずこの5倍であることが必要 805*5=4025 5倍すると下3桁125でOK よってm=125 よってn=250 *熟読玩味...^^;
|
- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用
コメント（1）
