>>77
その書き方だと，「∀n∈N ∃k∈N s.t. ...」 と読んでしまった。
（そうだとしたらk=a^n+2で成り立ってしまうんで自明だわな）
(2)は，なんか見たことあると思ったが，Sierpinski numberの存在証明だったのね。

(1)
k*a^n+1=k(a^n-1)+k+1だから、k=a-2とすれば任意の自然数nに対してk*a^n+1は
a-1(≧2)で割り切れ、商はk(a^n-1)/(a-1)+1≧k+1=a-1、よってk*a^n+1は合成数。(証明終)

(2)
mod3, mod5, mod7, mod13, mod19, mod37, mod73での2の位数はそれぞれ
2, 4, 3, 12, 18, 36, 9だから、mを非負整数とすると
(※) k*2^(2m)+1≡k+1(mod3),
　　 k*2^(4m+1)+1≡2k+1(mod5),
　　 k*2^(3m+1)+1≡2k+1(mod7),
　　 k*2^(12m+11)+1≡7k+1(mod13),
　　 k*2^(18m+15)+1≡12k+1(mod19),
　　 k*2^(36m+27)+1≡6k+1(mod37),
　　 k*2^(9m+3)+1≡8k+1(mod73)。
中国剰余定理によりkを
　　k≡-1(mod3),
　　≡-1/2≡2(mod5),
　　≡-1/2≡3(mod7),
　　 ≡-1/7≡11(mod13),
　　 ≡-1/12≡11(mod19),
　　 ≡-1/6≡6(mod37),
　　 ≡-1/8≡9(mod73)
を満たすようにとる。つまりk≡78557(mod70050435)とする。このとき
(※)の右辺はすべて≡0となるが，任意の自然数nは，ある整数mによって
2m, 4m+1, 3m+1, 12m+11, 18m+15, 36m+27, 9m+3
のいずれかの形に表されるから，これはk*2^n+1が3,5,7,13,19,37,73のいずれかで
割り切れることを示している。kのとり方からk*2^n+1>73だから，k*2^n+1は合成数。(証明終)