|
問題2505・・・ひよこさんのブログ http://myhome.cururu.jp/gersdorffite/blog/article/71001823140 より Orz〜
任意の桁数の automorphic_number は存在するか。
* 具体的にいくつかのkについて、1つだけ求めてみると、
1桁 ： 5 （5＾2 = 25）
2桁 ： 25 （25＾2 = 625）
3桁 ： 625 （625＾2 = 390625）
4桁 ： 9376 （9376＾2 = 87909376）
5桁 ： 90625 （90625＾2 = 8212890625）
・・・
解答
上記サイトより Orz〜
・否定する者さんのもの Orz〜
正整数nを任意に固定する。
このとき、次の補題A,B,Cが成立する。
「補題A」
x^2≡x (mod.10^n) を満たすような
整数x∈(1,10^n)はちょうど2つ存在する。
「証明」
整数x∈(1,10^n)に対して、
x^2≡x (mod.10^n) ⇔ 10^n|x(x-1)
⇔「2^n|x ∧ 5^n|x-1」∨「2^n|x-1 ∧ 5^n|x」
中国剰余定理より、2^n|x ∧ 5^n|x-1 を満たす
整数x∈(1,10^n)は唯一つ存在し、また、
2^n|x-1 ∧ 5^n|x を満たす整数x∈(1,10^n)
も唯一存在するといえる。よって示せたといえる。
「補題B」
上記の2つの整数をa,bとするとき、
(10, a-b)=1 が成立するといえる。
「証明」
x=a,b とすれば、次がいえる。
「2^n|x ∧ 5^n|x-1」∨「2^n|x-1 ∧ 5^n|x」
とくに「2|x ∧ 5|x-1」∨「2|x-1 ∧ 5|x」
これより、aとbのパリティは異なるといえて、
また、a-b≡1-0=1 or a-b≡0-1≡-1 (mod.5)
がいえるので、(10,a-b)=1 が示せたといえる。
上記a, bに対して、a+b=10^n+1 が成立する。
「証明」
a^2≡a, b^2≡b (mod.10^n) より、
a^2-b^2≡a-b (mod.10^n) を得る。
よって、10^n|(a-b)(a+b-1) を得る。
これと、補題Bより、10^n|a+b-1 を得る。
よって、a+b=k*10^n+1 ・・・?
を満たす正整数kが取れる。
a,b＜10^n より、a+b＜2*10^n ・・・?
であるから、これと?より、
k*10^n+1＜2*10^n を得る。
ここで、k≧2と仮定すれば、
2*10^n+1≦k*10^n+1 であるから、
これと?より、
2*10^n+1＜2*10^n ⇔ 1＜0 を得る。
これは矛盾である。
よって、k=1 であるといえる。
よって、再び?より、a+b=10^n+1
したがって、示せたといえる。
任意の桁数でautomorphic_numberは存在する。
(証明)
正整数xがn桁のautomorphic_numberであるというのは、
x^2≡x (mod.10^n) かつ 10^(n-1)≦x＜10^n
を満たすことである。そこで、ある正整数nがあって、
n桁のautomorphic_numberが存在しないと仮定する。
まず補題Aより、x^2≡x (mod.10^n) を満たす
正整数x∈(1,10^n)はちょうど2つ存在するので、
そのような2つの正整数をa, bとする。
仮定より、a,b＜10^(n-1) がいえるから、
a+b＜10^(n-1)+10^(n-1)=2*10^(n-1) がいえる。
これと補題Cより、10^n+1＜2*10^(n-1)
⇔ 8*10^(n-1)+1＜0 を得るが、これは矛盾である。
したがって、証明は完了したといえる。
すごい論理力 ^^;
中国剰余定理ってのは今一咀嚼できてないけど、、、
取り敢えずついてはいけました Orz...v
|
コメント（0）
