18316：証明...約数に2も5も持たない整数の累乗は 00・・・01(0は任意個)を末尾にもつ...^^;

問題18316・・・http://www.maroon.dti.ne.jp/hashirimedes/mondai5.html より 引用 Orz〜

約数に２も５も持たない正整数のある累乗は
００・・・０１（０は任意個）を末尾とすることを示せ。

解答

・わたしの...

例えば...

3^4≡1 (mod 2 or 5)

3^20-1

=(3^4)^5-1 (≡0  mod 10)

=(3^2)^10-2

=((3^2)^5+1)((3^2)^5-1)

は3^2-1≡0 (mod 10)を持つので ≡0 (mod 10)

so...

3^20は...末尾2桁は01

7^4+1≡0 (mod 10)

11^60-1

≡(11^12)^5-1 ≡0・・・フェルマーの小定理

=(11^2)^30-1

=((11^2)^15+1)((11^2)^15-1)

=((11^2)^15+1)((11^6)^3-1)

は(11^6-1)、つまり、11^2-1を因数に持つので≡0

奇数の下一桁は、1,3,7,9 なので、

上のように、01となる累乗がある...

でいいのかしらん？

・上記サイトより Orz〜

正整数をＡ、０はｎコとする。
鳩ノ巣原理（しわ寄せ原理）により Ａⁱ ≡ Ａ^j (mod 10ⁿ⁺¹)
となる異なる正整数ｉ、ｊ （i＞j） が存在する。・・・ここがよくわからない ^^;
Ａⁱ - Ａ^j = Ａ^j(Ａ^i-j - 1) は 10ⁿ⁺¹ の倍数で、仮定より、 Ａ^i-j - 1 は 10ⁿ⁺¹ の倍数となる。
よって Ａ^i-j は ００・・・０１（０はｎ個）を末尾とする。　　　　　　//

・鍵コメT様からのもの Orz〜

「ある累乗は00…01 (0は任意個)を末尾とする」は
あまり分かりやすい問題文とは思いませんが，
「0の個数がいくつであれ．末尾が00…01となるように累乗をとれる」
という意味です．

途中の「3^2-1≡0 (mod 10)」は誤りであり，・・・3^2+1≡0 (mod 10) でしたわ ^^;
意味するところがよくわかりません．

次のようにできます．
約数に2も5も持たない正整数nは，一の位が1,3,7,9のいずれか．
nの一の位が1のとき，n^1の一の位が1，
nの一の位が3のとき，n^4の一の位が1，
nの一の位が7のとき，n^4の一の位が1，
nの一の位が9のとき，n^2の一の位が1である．
n^aの一の位が1のとき，
n^((10^k)a)は，(10x+1)^(10^k)と表され，
その末尾は，「0(k個)1」となるから，題意は示された．・・・なるほどぉ☆

なお，「上記サイト」の解は，多分次のような意味です．

n,n^2,n^3,… (n^t)は，いずれも2,5では割り切れない．
十分多数のtをとれば，その下k+1桁が一致する．
n^aとn^b (a<b)が同じ下k+1桁を持つとして，
n^b-n^aは10^(k+1)で割り切れ，
n^(b-a)-1も10^(k+1)で割り切れるから，n^(b-a)の下k+1桁は「0(k個)1」．
よって，題意は示された．

*よくわかりました ^^♪

[スモークマン]

＞11:29pmの鍵コメT様へ ^^
そう言いたかったのですが...うまく言えませんでした ^^;;

後半は...例えば...末尾が001ならば...n,n^2,...,n^500まで考えれば(末尾が偶数にはならないので)...鳩の巣原理で少なくとも2種類のn^i,n^jがあるからなのですね ^^

紹介させていただきまっす〜m(_ _)m〜v