数学してよアライㄜん

アライㄜんが数学をしないで数学について書くのだ

有限体の紹介

有限体のちょっと知られている事実をわかりやすく書こうと思ったら有限体の紹介だけで相当な文字数になったから分離するのだ……

記号

集合を導入するのだ。数字の集まりだと思ってればいいのだ

<$>\begin{aligned} \Z&\coloneqq\{\ldots,-2,-1,0,1,2,\ldots\}\\ \N&\coloneqq\{1,2,3,4,\ldots\} \end{aligned}<$>

が度々登場するし、他にも数字の集まりを扱うことがあるので注意なのだ。高校数学の範疇で十分なので過度に心配する必要はないのだ

この記事独特の表現として

<$>\begin{aligned} [a,b]&\coloneqq\{a,a+1,\ldots,b-1,b\}\\ [a,b)&\coloneqq\{a,a+1,\ldots,b-2,b-1\} \end{aligned}<$>

を使うことにするのだ。いちいち書くのがめんどくさくて……

注意

これから「当たり前のこと」を一つ一つ証明していくのだ

つまらないかもしれないから「当然だなー」と思ったら省略してほしいのだ

余り計算

これから「$13\div 4=3$ あまり $1$」だとか「$13$ を $4$ で割った余りが……」とかいちいち言ってられないくらい余りを扱うのだ

よって $13\bmod 4$ という記号を使って「$13$ を $4$ で割った余り」を表すことにするのだ

ただし、$-5\bmod 4$ なんかも今回は定義したいのだ。だから、「ちゃんと定義できるか」も証明の練習がてら確かめてみたいのだ

$a\in\Z,\ n\in\N$ に対して $a=nq+r$ となるような $q\in\Z,\ r\in[0,n)$ が一つだけ存在するのだ

よって「$a$ を $n$ で割った余り」に $a\bmod n$ という記号を当て、$a\bmod n\coloneqq r$ とするのだ

$a\geq 0$ のときは数学的帰納法を使って存在を証明するのだ

$a\in[0,n)$ に対しては自明に $a=0\times n+a$ で $0\in\Z,\ a\in[0,n)$ だから $q=0,\ r=a$ とすればいいのだ

さらに $a\geq n$ のときを考えるのだ。帰納法の仮定より $a-n\in[0,a)$ に対して $a-n=\overline qn+r$ となるような $\overline q\in\Z,\ r\in[0,n)$ が存在するのだ

$a=(\overline q+1)n+r$ と書けるから、$\overline q+1\in\Z,\ r\in[0,n)$ より $q=\overline q+1$ とすればいいのだ

よって数学的帰納法によって $a\geq 0$ のときは示せたのだ

では、$a< 0$ のときを考えるのだ

$a-2na>0$ だから $a-2na=\overline qn+r$ となるような $\overline q\in\Z,\ r\in[0,n)$ が存在するのだ。よって $a=(2a+\overline q)n+r$ から $q=2a+\overline q$ とすればいいのだ

よって存在が言えたのだ

次は「一つしか存在しないこと」なのだ

$a=\overline qn+\overline r=qn+r\ (\overline q,q\in\Z,\ \overline r,r\in[0,n),\ \overline q>q)$ としたときに、「$\overline q=q,\ \overline r=r$」であることを証明するのだ

$(\overline q-q)n+(\overline r-r)=0$ であることに注意するのだ

$\overline q-q\ne 0$ とすると、矛盾が導けるのだ

$\overline r-r < n,\ (\overline q-q)n >n$ だから $(\overline q-q)n+(\overline r-r)>0$ となって矛盾なのだ

よって $\overline q-q=0$ さらに $\overline r-r=0$ なのだ

$a\bmod n$ はいつでも非負の値をとるのだ。例えば $-5\bmod 4=3$ なのだ

なぜなら $-5=(-2)\times 4+3$ で $-2\in\Z,\ 3\in[0,4)$ だからなのだ

これが至る所に登場するからしっかり憶えてほしいのだ

当たり前の性質として次があるのだ:

$n\in\N,\ a\in[0,n)$ に対して $a\bmod n=a$ なのだ

$a=0\times n+a$ と書けて、$0\in\Z,\ a\in[0,n)$ より $a=a\bmod n$ なのだ

$a,b\in\Z,\ n\in\N$ に対して $(a+bn)\bmod n=a\bmod n$ なのだ

$a=qn+r,\ q\in\Z,\ r\in[0,n)$ とするのだ

<$>\begin{aligned} a+bn &= qn+r+bn\\ &=(q+b)n+r \end{aligned}<$>

と書き下せて、$q+b\in\Z,\ r\in[0,n)$ より言えたのだ

当たり前の事だけど、ちゃんと証明しないといけないのだ

$\Bbb{F}_p$ の導入

有限な加法と乗法

$a,b\in\Z,\ n\in\N$ に対して

<$>\begin{aligned} a+_n b&\coloneqq (a+b)\bmod n\\ a\times_n b&\coloneqq (a\times b)\bmod n\\ \end{aligned}<$>

とするのだ

当然成り立つ性質として次があるのだ:

$a,b\in\Z,\ n\in\N$ に対して

  • $a+_n b=b+_n a$
  • $a\times_n b=b\times_n a$

また $n\in\N,\ a,b\in[0,n)$ に対して

  • $a+_n 0=a$
  • $a\times_n 1=a$

なのだ

これは簡単なので省略なのだ

$a,b\in\Z,\ n\in\N$ に対して

  • $(a\bmod n)+_n b=a+_n b$
  • $(a\bmod n)\times_n b=a\times_n b$

なのだ

$a=qn+r\ (q\in\Z,\ r\in[0,n))$ とするのだ

このとき、

<$>\begin{aligned} a+_n b&=(a+b)\bmod n\\ &=(qn+r+b)\bmod n\\ &=(r+b)\bmod n\\ &=r+_n b\\ \\ a\times_n b&=(a\times b)\bmod n\\ &=[(qn+r)\times b]\bmod n\\ &=[(qb)n+r\times b]\bmod n\\ &=(r\times b)\bmod n\\ &=r\times_n b \end{aligned}<$>

より言えたのだ

これで普通の加法乗法で言えることが証明できるのだ:

$a,b,c\in\Z,\ n\in\N$ に対して

  • $(a+_n b)+_n c=a+_n(b+_n c)$
  • $(a\times_n b)\times_n c=a\times_n(b\times_n c)$
  • $a\times_n(b+_n c)=a\times_n b+_n a\times_n c$

なのだ

<$>\begin{aligned} (a+_n b)+_n c&=[(a+b)\bmod n]+_n c\\ &=(a+b)+_n c\\ &=(a+b+c)\bmod n\\ &=a+_n(b+c)\\ &=a+_n[(b+c)\bmod n]\\ &=a+_n(b+_n c) \end{aligned}<$>($\times_n$ と分配法則も同じなのだ)

後はマイナスを $[0,n)$ で定義できるのだ:

$n\in\N,\ a\in[0,n)$ に対して、$-_n a\coloneqq(-a)\bmod n$ とすると、$a+_n(-_n a)=0$ となるのだ

これによって減法 $a-_n b\coloneqq a+_n(-_n b)$ が定義できるようになったのだ

有限な割り算

加法乗法減法……ときたら除法なのだ! 実は $p$ を素数 ($2,3,5,7,11,13,17,\ldots$) としたとき、$[0,p)$ では割り算が定義できることが知られているのだ:

$p:$ 素数$,\ a\in[1,p)$ に対して $a\times_p b=1$ となるような $b\in[1,p)$ がただ一つだけ存在するのだ

まずちょっとわかりづらいので例を出すのだ

$p=3$ としたとき、

<$>\begin{aligned} 1\times_3 1&=1\\ 2\times_3 2&=1 \end{aligned}<$>

$p=7$ としたとき、

<$>\begin{aligned} 1\times_7 1&=1\\ 2\times_7 4&=1\\ 3\times_7 5&=1\\ 4\times_7 2&=1\\ 5\times_7 3&=1\\ 6\times_7 6&=1 \end{aligned}<$>

では証明なのだ

$a\in[1,p)$ に対して $a\times_p b=1$ となるような $b\in[1,p)$ が存在することを数学的帰納法で証明するのだ

$a=1$ のときは自明に $b=1$ をとれば $a\times_p b=1\bmod p=1$ なのだ

$a\in[2,p)$ のときを考えるのだ。帰納法の仮定は「$c\in[1,a)$ に対して $c\times_p d=1$ となるような $d\in[1,p)$ が存在する」なのだ

このとき、$p=qa+r$ となるような $q\in\Z,\ r\in[0,a)$ をとると、$p:$ 素数より $r\ne 0$、とくに $r\in[1,a)$ なのだ

よって $r\times_p c=1$ となるような $c\in[1,p)$ が存在するのだ

このとき、$b\coloneqq(-qc)\bmod p$ とすれば、

<$>\begin{aligned} a\times_p b&=a\times_p[(-qc)\bmod p]\\ &=(-qca)\bmod p\\ &=(r-p)c\bmod p\\ &=(rc-cp)\bmod p\\ &=rc\bmod p\\ &=r\times_p c\\ &=1 \end{aligned}<$>

より、$a\times_p b=1$ となる $b\in[1,p)$ がとれたので帰納法より存在証明が出来たのだ

ただ一つだけ存在するのは $a\times_p b=1,\ a\times_p c =1$ となるような $b,c\in[1,p)$ があったとしたら $b=b\times_p(a\times_p c)=(b\times_p a)\times_p c=c$ より直ちにわかるのだ

$a\in[1,p)$ に対して、$a\times_p b=1$ となるような $b\in[1,p)$ を $a^{\times_p -1}$ と書いて「$a$ の逆数」と呼ぶことにするのだ

また、$c\in[0,p),\ c\in[1,p)$ に対して $c\div_p d=c\times_p d^{\times_p -1}$ と定義するのだ

これで割り算が定義できたのだ。なんか分数にすらならないのが不思議な感じなのだ

有限体とは

「有限な集合に四則演算が定まる」というのを一つの性質としてまとめたのが「有限体」なのだ:

有限集合 $K$ とその上の加法と乗法 $+_K,\ \times_K,$ さらにマイナス倍や逆数をとる演算 $-_K,\ \bullet^{\times_K -1}$、あと $0_K,1_K\in K$ が有限体になるとは次が成り立つことをいうのだ:

  • $a+_K 0_K=a,\ a\times_K 1_K=a$
  • $a+_Kb=b+_Ka,\ a\times_K b=b\times_K a$
  • $(a+_K b)+_K c=a+_K(b+_K c),\ (a\times_K b)\times_K c=a\times_K(b\times_K c)$
  • $a+_K(-_K a)=0_K,\ a\times_Ka^{\times_K -1}=1_K$
  • $a\times_K(b+_K c)=a\times_K b+_K a\times_K c$

この定義に従うと $([0,p),+_p,\times_p,-_p,\bullet^{\times_p -1},0,1)$ は有限体になることがわかるのだ

このとき、$[0,p)$ に「有限体である」という意味を込めて $\Bbb{F}_p$ と書くのだ

他にも有限体はたくさん存在してるけど、なかなか例を挙げるのが難しいのだ

例えば $K=\{0,1,\alpha,\alpha+1\}$ とかはわりと小さい有限体なのだ

これに $x+x=0\ (x\in K),\ \alpha\times_K(\alpha+1)=1$ 以外は普通の演算を定義すると有限体になるのだ

具体的に $\Bbb{F}_p$ が有限群になるからいくつか当たってみると面白いのだ。$\Bbb{F}_{11}$ で $7^{\times_{11} -1}$ とかを計算してみると少しは楽しいかもしれないのだ

有限体の導入はこれくらいなのだ