p×p巡回行列式として表せる整数の必要十分条件
はじめに
一ヶ月半ほど前に
整数$n$が整数$a,b,c$を用いて
$a^3+b^3+c^3-3abc=n$
と表しうる必要十分条件は
「$n$は$3$で割りきれない、または$n$は$9$で割り切れる」
を示したとツイートしました(
これ
)
この一般化として
$p$は素数、$\zeta=e^{2\pi i/p}$とする
整数$n$が整数$a_0,a_1,\cdots,a_{p-1}$を用いて
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})=n$
と表しうる必要十分条件は
「$n$は$p$で割り切れない、または$p^2$で割り切れる」
を示していきます
$p$で割り切れない場合
$0< x< p$,$a$は整数とします
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$に
$a_0=\cdots=a_{x-1}=a+1,a_x=\cdots=a_{p-1}=a$
を代入すると
$\displaystyle\prod^{p-1}_{k=0}((a+1)+\cdots+(a+1)\zeta^{(x-1)k}+a\zeta^{xk}+\cdots+a\zeta^{(p-1)k})=$
$\displaystyle(ap+x)\prod^{p-1}_{k=1}(1+\cdots+\zeta^{(x-1)k})=$
$\displaystyle(ap+x)\prod^{p-1}_{k=1}\frac{1-\zeta^{xk}}{1-\zeta^k}$
$\displaystyle\prod^{p-1}_{k=1}(1-\zeta^{xk})=\prod^{p-1}_{k=1}(1-\zeta^k)$より
$\displaystyle\prod^{p-1}_{k=0}((a+1)+\cdots+(a+1)\zeta^{(x-1)k}+a\zeta^{xk}+\cdots+a\zeta^{(p-1)k})=ap+x$
となります
つまり、$a$は任意の整数としてよいので、$p$で割って$x$余る数は表せますね！
また、$x$の条件は$0< x< p$なので、$p$の倍数でない数は全て表せますね！！
というわけで
$n$が$p$で割り切れないならば
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})=n$
と表せる
が得られた！！！！
$p$で割り切れて$p^2$で割り切れない場合
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$が$p$で割り切れるなら$p^2$でも割り切れる事を示します
(つまり、$p$で割り切れて$p^2$で割り切れない数はこの形で表せない)
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡0\pmod p$とする
複素数の入った式の$\pmod p$を考えるのは難しいので、一工夫加えましょう
$f(b_0+b_1\zeta+\cdots+b_{p-1}\zeta^{p-1})≡b_0+b_1+\cdots+b_{p-1}\pmod p$
なる$f$を用意します
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$は式に複素数が入ってはいるが一応実数なので、$f$の定義より
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡f(\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k}))\pmod p$
という変形ができる
また、$f(zw)≡f(z)f(w)\pmod p$が成り立つ(証明略)のでさらに
$\displaystyle f(\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k}))$
$\displaystyle≡\prod^{p-1}_{k=0}f(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})\pmod p$
$\displaystyle≡\prod^{p-1}_{k=0}(a_0+a_1+\cdots+a_{p-1})\pmod p$
$\displaystyle≡(a_0+a_1+\cdots+a_{p-1})^p\pmod p$
$\displaystyle≡a_0+a_1+\cdots+a_{p-1}\pmod p$
とできた
よって
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡a_0+a_1+\cdots+a_{p-1}\pmod p$
すなわち
「$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$が$p$の倍数ならば$a_0+a_1+\cdots+a_{p-1}$も$p$の倍数」
が得られた！！
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$が$p$の倍数ならば$a_0+a_1+\cdots+a_{p-1}$も$p$の倍数であることを示せました
あとは$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$の$a_0+a_1+\cdots+a_{p-1}$じゃない部分、
$\displaystyle\prod^{p-1}_{k=1}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$
も同条件において$p$の倍数となることを示せば
「$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$が$p$で割り切れるなら$p^2$でも割り切れる」
となりますね！
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡0\pmod p$とする
さっきと同様の手法で
$\displaystyle\prod^{p-1}_{k=1}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡(a_0+a_1+\cdots+a_{p-1})^{p-1}\pmod p$
を示せるので、$a_0+a_1+\cdots+a_{p-1}≡0\pmod p$となることを使うと
$\displaystyle\prod^{p-1}_{k=1}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})≡0\pmod p$
となります
よって、$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$は$2$つ以上の$p$の倍数の積となり、すなわち
「$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$が$p$で割り切れるなら$p^2$でも割り切れる」
が得られた！！！！
$p^2$で割り切れる場合
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$に$a_0=2,a_1=a_2=\cdots=a_{p-2}=1,a_{p-1}=0$
を代入すると
$\displaystyle\prod^{p-1}_{k=0}(2+\zeta^k+\cdots+\zeta^{(p-2)k})=$
$\displaystyle p\prod^{p-1}_{k=1}(2+\zeta^k+\cdots+\zeta^{(p-2)k})=$
$\displaystyle p\prod^{p-1}_{k=1}(1-\zeta^{(p-1)k})=$
$\displaystyle p(1^0+1^1+\cdots+1^{p-1})=$
$\displaystyle p^2$
というわけで
$p^2$は$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$の形で表せる
が得られた!!
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$に$a_0=p+1,a_1=a_2=\cdots=a_{p-2}=p,a_{p-1}=p-1$
を代入すると
$\displaystyle\prod^{p-1}_{k=0}(p+1+p\zeta^k+\cdots+p\zeta^{(p-2)k}+(p-1)\zeta^{(p-1)k})=$
$\displaystyle p^2\prod^{p-1}_{k=1}(p+1+p\zeta^k+\cdots+p\zeta^{(p-2)k}+(p-1)\zeta^{(p-1)k})=$
$\displaystyle p^2\prod^{p-1}_{k=1}(1-\zeta^{(p-1)k})=$
$\displaystyle p^2(1^0+1^1+\cdots+1^{p-1})=$
$p^3$
というわけで
$p^3$は$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$の形で表せる
が得られた!!
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})=\det\pmatrix{a_0&a_1&\cdots&a_{p-1}\\a_{p-1}&a_0&\cdots&a_{p-2}\\\vdots&\vdots&\ddots&\vdots\\a_1&a_2&\cdots&a_0}$
と
$\displaystyle\det\pmatrix{a_0&a_1&\cdots&a_{p-1}\\a_{p-1}&a_0&\cdots&a_{p-2}\\\vdots&\vdots&\ddots&\vdots\\a_1&a_2&\cdots&a_0}\det\pmatrix{b_0&b_1&\cdots&b_{p-1}\\b_{p-1}&b_0&\cdots&b_{p-2}\\\vdots&\vdots&\ddots&\vdots\\b_1&b_2&\cdots&b_0}=\det\pmatrix{a_0&a_1&\cdots&a_{p-1}\\a_{p-1}&a_0&\cdots&a_{p-2}\\\vdots&\vdots&\ddots&\vdots\\a_1&a_2&\cdots&a_0}\pmatrix{b_0&b_1&\cdots&b_{p-1}\\b_{p-1}&b_0&\cdots&b_{p-2}\\\vdots&\vdots&\ddots&\vdots\\b_1&b_2&\cdots&b_0}$
(と巡回行列が積について閉じている事)より、
$m,n$がともに$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})$の形で表せるとき、$mn$もそう表せる
がわかる
$p^2,p^3$が表せることを踏まえると、$p^2$を$a$個、$p^3$を$b$個掛けた値$p^{2a+3b}$も表せるので、
$a≧0,b≧0$に対し$2a+3b$は$1$でない非負整数全てを亘るから、
「$N≠1$に対し$p^N$は表せる」
また、$p$で割り切れない数も表せるから、$p^N$と掛けると、
「$N≠1$に対し$p$で$N$回割り切れる数は表せる」
となる
$N=1$の時表せない事はもう示したので、つまり、
$p$は素数、$\zeta=e^{2\pi i/p}$とする
整数$n$が整数$a_0,a_1,\cdots,a_{p-1}$を用いて
$\displaystyle\prod^{p-1}_{k=0}(a_0+a_1\zeta^k+\cdots+a_{p-1}\zeta^{(p-1)k})=n$
と表しうる必要十分条件は
「$n$は$p$で割り切れない、または$p^2$で割り切れる」
が得られた！！！！
$Q.E.D.$！！！！
おわりに
以上、自分の発見した暫定一番好きな定理/証明でした！！
それでは！！
