Dirichlet の算術級数定理（２）

2. mod

自然数 $m$ および整数 $a, b$ に対し， $m$ が $a-b$ を割り切るとき，
$a\equiv b \quad\mathrm{mod}\quad m$
と書く．次は容易に確かめられる．

命題2.1
$\equiv$ は同値関係．すなわち，
(1) $a\equiv a\quad\mathrm{mod}\quad m$
(2) $a\equiv b\quad\mathrm{mod}\quad m$ ならば $b\equiv a\quad\mathrm{mod}\quad m$
(3) $a\equiv b\quad\mathrm{mod}\quad m,\quad b\equiv c\quad\mathrm{mod}\quad m$ ならば， $a\equiv c\quad\mathrm{mod}\quad m.$

整数 $a$ の同値類
$\bar{a}=(a\quad\mathrm{mod}\quad m)=\{x\in \mathbb{Z}\mid x\equiv a\quad\mathrm{mod}\quad m\}$
を， $m$ を法とする $a$ の剰余類と言う．
商集合すなわち同値類全体の集合を，
$\mathbb{Z}/m\mathbb{Z}=\{\bar{0}, \bar{1}, \dots , \overline{m-1}\}$
と書く．次も容易．

命題2.2
自然数 $a, b$ の剰余類 $x, y$ に対し， $a+b, ab$ の属する剰余類は $x, y$ のみによって決まる．
これをそれぞれ $x+y, xy$ と書く．

補題2.3 自然数 $a, b$ に対し， $(a, b)=ax+by$ 　をみたす整数 $x, y$ が存在する．
ここで， $(a, b)$ は $a, b$ の最大公約数．

証明（Euclid の互除法）
２つの自然数に対し，「大きい方を，それから小さい方を引いたものにおきかえる」という操作を考える．
この操作を続けると，有限回で２つの自然数が等しくなる．
自然数 $a, b, a>b$ に対し， $(a-b, b)=(a-b)x+by$ とすると，
$(a, b)=(a-b, b)=(a-b)x+by=ax+b(y-x).$
したがって，補題は $a=b$ の場合に帰着されるが，その場合は明らか．//

補題2.4
(1) 自然数 $m$ とたがいに素な整数 $a$ に対し， $ax\equiv 1 \quad\mathrm{mod}\quad m$ となる $m$ とたがいに素な整数 $x$ が存在する．
(2) 自然数 $m$ とたがいに素な整数 $a, b$ に対し， $ab$ も $m$ とたがいに素．
(3) 素因数分解は一意的．

証明
(1) $(m, a)=1$ なので，補題2.1より， $ax+my=1$ となる整数 $x, y$ が存在する．このとき $(m, x)=1.$
(2) $b=b(ax+my)=(ab)x+m(by)$ より， $ab, m$ の公約数は $b, m$ の公約数．
(3) 素数 $p$ が素数の積 $p_1\cdots p_n$ を割り切るとすると，
(2)より， $p$ は $p_1,\dots , p_n$ のいずれかに一致する．//

自然数 $m$ を法とする， $m$ とたがいに素な整数の剰余類の集合を $(\mathbb{Z}/m\mathbb{Z})^\times$ とする．
その元の個数を $\varphi(m)$ と書く．
$G=(\mathbb{Z}/m\mathbb{Z})^\times$ とおくと，次が成り立つ．

命題2.5
(1) $x, y\in G$ に対し， $xy\in G.$
(2) $x, y, z\in G$ に対し， $(xy)z=x(yz).$
(3) $x, y\in G$ に対し， $xy=yx.$
(4) $\bar{1}\in G.$ 　 $x\in G$ に対し， $\bar{1}x=x\bar{1}=x.$
(5) $x\in G$ に対し， $xx^{-1}=x^{-1}x=\bar{1}$ となる $x^{-1}\in G$ がただ一つ存在する．