以前の記事、『mod pのパスカルの三角形で、全ての整数が一度ずつ現れる行のあるもの』で書いた内容を証明します
pを奇素数、aをpと互いに素な整数とします
１行目にa,－aという２つの数を隣り合わせて配置したパスカルの三角形を考えるとき
(p－1)行目をmod pで考えると（つまりpで割った余りを考えると）、0からp-1までのp個の数が一度ずつ現れることを示します
１行目の左側にa、右側に－aが配置されているとします
１行目がもしaだけならば、(p－1)行目には通常のパスカルの三角形の(pー1)行目をa倍したものが左詰めに並びます
同様に、１行目が－aだけならば、(p－1)行目には通常のパスカルの三角形の(pー1)行目を－a倍したものが右詰めに並びます
通常のパスカルの三角形の、(p－1)行目の左からn個目は(p-2)C(n-1)と表せます。（Cは組み合わせのCです）
また、１行目がaだけの場合と１行目が－aだけの場合を足し合わせると、１行目がa,－aのものになるので
１行目がa,－aのパスカルの三角形の(p－1)行目の左からn個目は
a×(p-2)C(n-1)－a×(p-2)C(n-2)
と表せます
なので、これのnが1以上p以下の場合をmod pで考えたとき、0からpまでの数が一度ずつ現れることを示せばよいです
a×(p-2)C(n-1)－a×(p-2)C(n-2)
をmod pで考えると
a( (-2)C(n-1)－(-2)C(n-2) ) （mod p）
となります
(-2)C(n-1)＝(－2)×(－3)×…×(－n)/(n－1)!
＝(－1)^(n-1)×n
(-2)C(n-2)＝(－2)×(－3)×…×(－n+1)/(n－2)!
＝(－1)^(n-2)×(n－1)
なので
a( (-2)C(n-1)－(-2)C(n-2) )
＝a( (－1)^(n-1)×n－(－1)^(n-2)×(n－1) )
＝a( (－1)^(n-1)×n＋(－1)^(n-1)×(n－1) )
＝a(－1)^(n-1) × (n＋(n－1) )
＝a(－1)^(n-1) × (2n－1)
となり
１行目がa,－aのパスカルの三角形の(p－1)行目の左からn個目は、
mod pでa(－1)^(n-1) × (2n－1)になると分かりました
nが1以上p以下のとき、a(－1)^(n-1) × (2n－1) （mod p）が0から(p-1)までの値を一度ずつとると証明するには
x,yを1以上p以下の整数でx≠yとするとき
a( (－1)^(x-1)×(2x－1)－(－1)^(y-1)×(2y－1) )
がmod pで0にならないと示せればよいです
x,yの偶奇が一致するとき、(－1)^(x-1)＝(－1)^(y-1)なので
a( (－1)^(x-1)×(2x－1)－(－1)^(y-1)×(2y－1) )
＝a(－1)^(x-1) × ( (2x－1)ー(2y－1) )
＝a(－1)^(x-1) × 2(xーy)
となり、x≠y （mod p）なのでこれはmod pで0になりません
x,yの偶奇が一致しないとき、－(－1)^(x-1)＝(－1)^(y-1)なので
a( (－1)^(x-1)×(2x－1)－(－1)^(y-1)×(2y－1) )
＝a(－1)^(x-1) × ( (2x－1)＋(2y－1) )
＝a(－1)^(x-1) × 2(x＋y－1)
となり
x,yが1以上p以下の整数で偶奇が異なることから、(x＋y－1)はpの倍数にならず、これもmod pで0になりません
よって、(p－1)行目をmod pで考えると、0からp-1までのp個の数が一度ずつ現れることが証明できました。
ちなみに
『打ち消しあうパスカルの三角形とカタラン数』で考えたパスカルの三角形は今回考えたもののa＝－1のバージョンなので、
このパスカルの三角形の(p－1)行目をmod pで考えても、0からp-1までのp個の数が一度ずつ現れることが分かります
以上です 結構前に考えた予想ですが、証明できてよかったです
お読みいただきありがとうございました！
