【カーマイケル数】
gcd(a,n)=1 をみたす任意のa∈Zに対して、a^(n-1)≡1 (mod n) をみたすn∈Nをカーマイケル数という。
以下を証明せよ。

(1) カーマイケル数は奇数である。

(2) n∈Nに対して、nがカーマイケル数であるための必要十分条件は、(i)かつ(ii)である。
　(i) nは合成数で、平方因子をもたない
　(ii) nの任意の素因数pに対して、n-1はp-1で割り切れる

(3) カーマイケル数は、３個以上の異なる素数の積である。

(4) 6k+1、12k+1、18k+1がすべて素数のとき、n = (6k+1)(12k+1)(18k+1) はカーマイケル数である。