【数学】有理数と$n$ 進法の小数

《キーワード:有理数、循環小数、位数》

$r\in\mathbb{R}$ に対し、

『$r$が有理数であるためには$r$が有限小数もしくは循環小数であることが必要十分』

が成り立つ。一般に、 $n$ を正整数とするとき、

『$r$が有理数であるためには$r$は$n$進法で有限小数もしくは循環小数であることが必要十分』

これについて証明する。

十分性$(\Leftarrow)$ については $10$ 進法のときと同様に示せるので、略。

必要性$(\Rightarrow)$ が問題になるが、鍵となるのは位数の概念

$n,a\in\mathbb{Z}_{>0},\gcd(n,a)=1$ とするとき、 $$a+n\mathbb{Z}\in(\mathbb{Z}/n\mathbb{Z})^\times$$ の位数 $$m=\mathrm{ord}(a+n\mathbb{Z})$$ は次を満たす最小の正整数 $$a^{m}\equiv1\bmod{n}$$

まず$r$ は有理数なので、整数 $a$ と正整数 $b$ を用いて、 $$r=\frac{a}{b},\gcd(a,b)=1$$ と書ける。

① $\gcd(n,b)=1$

$b=1$ なら、 $r$ は整数なので、小数部分は $0$ となり、有限小数。

それ以外を考える。

$$m=\mathrm{ord}(n+b\mathbb{Z})$$

とおくと、

$$n^{m}\equiv1\bmod{b}$$

だから、

$$n^{m}a\equiv a\bmod{b}$$

つまり、ある整数 $k$ が存在して、

$$n^{m}a-a=bk$$

と書けるから、

$$n^{m}\frac{a}{b}-\frac{a}{b}=k$$

したがって、 $r$ の $n$ 進法表示の小数第 $i$ 位と小数第 $(i+m)$ 位は一致するから、 $r$ は循環小数で循環節の長さは $m $。

② $\gcd(n,b)\neq1$

$$t=\max\{e\in\mathbb{N}\mid n\text{の素因数}p\text{が存在して}b\text{は}p\text{で最高で}e\text{回割りきれる}\}$$

とおくと、

$$\gcd(n,\frac{b}{\gcd(n^t,b)})=1$$

であり、

$$n^tr=\frac{n^ta}{b}=\frac{\frac{n^t}{\gcd(n^t,b)}a}{\frac{b}{\gcd(n^t,b)}}$$

となり、$n^tr$ は①から、$n$ 進法で有限小数または循環小数。

$r$ の $n$ 進法表示は $n^tr$ の表示から、$t$ 個分小数点を左にずらせばいいから、有限小数または循環小数。

例として、$r=\frac{7}{15}$ を考える。

$n=8$ のとき

$$8^2\equiv4\bmod{15},8^4\equiv1\bmod{15}$$

であるから、

$$\mathrm{ord}(8+15\mathbb{Z})=4$$

$$8^4\frac{7}{15}-\frac{7}{15}=\frac{4095\cdot7}{15}=273\cdot7=(3567)_8$$

よって、 $$r=(0.\dot{3}56\dot{7})_8$$

$n=12$ のとき

$3^1\mid15$

であるから、

$$12^1\cdot\frac{7}{15}=\frac{28}{5}$$

また、

$$12^2\equiv4\bmod{5},12^4\equiv1\bmod{5}$$

であるから、

$$\mathrm{ord}(12+5\mathbb{Z})=4$$

$$12^4\frac{28}{5}-\frac{28}{5}=\frac{20735\cdot28}{5}=4147\cdot28=(57244)_{12}$$

よって、 $$r=(5.\dot{7}24\dot{4})_{12}$$

※ $n$ 進法での小数表示を求めるだけなら、

\begin{align*} \frac{7}{15}\cdot8&=3+\frac{11}{15}\\ \frac{11}{15}\cdot8&=5+\frac{13}{15}\\ \frac{13}{15}\cdot8&=6+\frac{14}{15}\\ \frac{14}{15}\cdot8&=7+\frac{7}{15} \end{align*}

より、$r=(0.\dot{3}56\dot{7})_8$ とした方が楽

2018-07-14

【数学・論理学】演繹定理

公理系と仮定 $P$ から命題 $Q$ の証明ができる(これを$P\vdash Q$ で表す)とき、「 $Q$ は $P$ の演繹である」「 $Q$ は $P$ から演繹可能である」という。

これについてエルブランによる次の演繹定理が成り立つ:

$P\vdash Q$ ならば、 $\vdash P\rightarrow Q$

証明は演繹の長さの帰納法でできる。

$P\vdash\lnot\lnot P$を例としてみていく。まずは証明図を書く。

\begin{align*} \text{公理}&:P\rightarrow(\lnot P\rightarrow P)\\ \text{仮定}&:P\\ \text{推論}&:\lnot P\rightarrow P\\ \text{公理}&:\lnot P\rightarrow\lnot P\lor P\\ \text{公理}&:(\lnot P\rightarrow\lnot P\lor P)\rightarrow[(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)]\\ \text{推論}&:(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)\\ \text{公理}&:\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P)\\ \text{推論}&:\lnot P\rightarrow\lnot P\\ \text{公理}&:(\lnot P\rightarrow P)\rightarrow[(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P]\\ \text{推論}&:(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P\\ \text{推論}&:\lnot\lnot P \end{align*}

$\lnot\lnot P$ は証明図で前にある $$\lnot P\rightarrow\lnot P$$ と $$(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$ から推論された。前にあるから、

$$P\vdash\lnot P\rightarrow\lnot P,\;P\vdash(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$

である。

$$P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P)},\;P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P})$$

が証明できるなら、三段論法

$$(A\rightarrow\color{red}{B})\rightarrow[(A\rightarrow(\color{red}{B}\rightarrow\color{blue}{C}))\rightarrow(A\rightarrow\color{blue}{C})]$$

が公理にあるから、 $$P\rightarrow\color{blue}{\lnot\lnot P}$$ も証明できる。

$$P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P)}$$ については、 $$\color{green}{\lnot P\rightarrow\lnot P}$$ が証明できるから、公理

$$\color{green}{A}\rightarrow(B\rightarrow\color{green}{A})$$

を使えば、証明できる。

$$P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P})$$ については、証明図をみると、 $$\lnot P\rightarrow P$$ と公理 $$(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)$$ から、 $$(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$ が推論されている。よって、同様に、 $$P\rightarrow(\lnot P\rightarrow P)$$ と $$P\rightarrow[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]$$ が証明できればよい。前者は公理だから証明できて、後者は $P\rightarrow(\text{公理})$ の形だから、公理 $$\color{green}{[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]}\rightarrow(P\rightarrow\color{green}{[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]})$$ を使えば、証明できる。

以上の準備をまとめると、 $$P\rightarrow\lnot\lnot P$$ の証明図は次のようになる。

\begin{align*} \text{公理}&:\lnot P\rightarrow\lnot P\lor P\\ \text{公理}&:(\lnot P\rightarrow\lnot P\lor P)\rightarrow[(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)]\\ \text{推論}&:(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)\\ \text{公理}&:\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P)\\ \text{推論}&:\lnot P\rightarrow\lnot P\\ \text{公理}&:\color{green}{\lnot P\rightarrow\lnot P}\rightarrow(P\rightarrow\color{green}{\lnot P\rightarrow\lnot P})\\ \text{推論}&:P\rightarrow(\lnot P\rightarrow\lnot P)\cdots(1)\\ \text{公理}&:P\rightarrow(\lnot P\rightarrow P)\cdots(2)\\ \text{公理}&:(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)\cdots(3)\\ \text{公理}&:(P\rightarrow\color{red}{\lnot P\rightarrow P})\rightarrow[(P\rightarrow(\color{red}{(\lnot P\rightarrow P)}\rightarrow\color{blue}{((\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)}) )\rightarrow(P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})]\cdots(4)\\ \text{推論(2)(4)}&:[(P\rightarrow(\color{red}{(\lnot P\rightarrow P)}\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)}) )\rightarrow(P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})]\cdots(5)\\ \text{公理}&:\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}\rightarrow[P\rightarrow\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}]\cdots(6)\\ \text{推論(3)(6)}&:P\rightarrow\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}\cdots(7)\\ \text{推論(5)(7)}&:P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})\cdots(8)\\ \text{公理}&:(P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P) })\rightarrow[(P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P}) )\rightarrow(P\rightarrow\color{blue}{\lnot\lnot P})]\cdots(9)\\ \text{推論(1)(9)}&:(P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P}) )\rightarrow(P\rightarrow\color{blue}{\lnot\lnot P})\cdots(10)\\ \text{推論(8)(10)}&:P\rightarrow\lnot\lnot P \end{align*}

2018-07-13

【数学・論理学】$\lnot(P\lor Q)\vdash\lnot P\land\lnot Q$ の形式証明

ただの備忘録。命題論理のある体系での形式証明。 \begin{align*} \text{公理}&:P\rightarrow P\lor Q\\ \text{公理}&:\lnot(P\lor Q)\rightarrow(P\rightarrow\lnot(P\lor Q))\\ \text{仮定}&:\lnot(P\lor Q)\\ \text{2,3行からの推論}&:P\rightarrow\lnot(P\lor Q)\\ \text{公理}&:(P\rightarrow P\lor Q)\rightarrow( (P\rightarrow\lnot(P\lor Q) )\rightarrow\lnot P)\\ \text{1,5行からの推論}&:(P\rightarrow\lnot(P\lor Q) )\rightarrow\lnot P\\ \text{4,6行からの推論}&:\lnot P\\ \text{公理}&:Q\rightarrow P\lor Q\\ \text{公理}&:\lnot(P\lor Q)\rightarrow(Q\rightarrow\lnot(P\lor Q))\\ \text{3,9行からの推論}&:Q\rightarrow\lnot(P\lor Q)\\ \text{公理}&:(Q\rightarrow P\lor Q)\rightarrow( (Q\rightarrow\lnot(P\lor Q) )\rightarrow\lnot Q)\\ \text{8,11行からの推論}&:(Q\rightarrow\lnot(P\lor Q) )\rightarrow\lnot Q\\ \text{10,12行からの推論}&:\lnot Q\\ \text{公理}&:\lnot P\rightarrow(\lnot Q\rightarrow\lnot P\land\lnot Q)\\ \text{7,14行からの推論}&:\lnot Q\rightarrow\lnot P\land\lnot Q\\ \text{13,15行からの推論}&:\lnot P\land\lnot Q \end{align*}

2018-06-09

【数学】$\Phi_n(x)$ の $\varphi(n)-1$ 次の係数

reisr.hatenablog.com の続きで、$G$の生成元の和を求めます。

皆の投稿 - 原始根の和が0,-1,1のいずれかになることの証明 - 数学博物館すうじあむのように包除原理を使って直接求めるのが上手い気がしますが、円分多項式の係数と結びつけたのでその方向で行きます。

まず、 $n(\in\mathbb{N})$ 位の円分多項式の係数を文字でおいて $$\Phi_n(x)=\sum_{i=0}^{\varphi(n)}a_n(i)x^i$$ とします。

$p$ を $n$ の素因数にならない素数とすると、

$$\Phi_{np}(x)=\frac{\Phi_n(x^ p)}{\Phi_n(x)}$$

が成立するので

$$\Phi_n(x)\Phi_{np}(x)=\Phi_n(x^p)$$

が得られます。

両辺の $x^{p\varphi(n)-1}$ の係数(最高次より $1$ 小さい次数の係数)を比較すると

$$a_n(\varphi(n)-1)a_{np}(\varphi(np))+a_n(\varphi(n))a_{np}(\varphi(np)-1)=0$$

です。ここで、円分多項式はモニックより

$$a_n(\varphi(n))=a_{np}(\varphi(np))=1$$

なので、漸化式

$$a_{np}(\varphi(np)-1)=-a_n(\varphi(n)-1)$$

が成立します。

$n$ が相異なる素数の積 $n=p_1p_2\cdots p_r$ とすると、この漸化式から

$$a_n(\varphi(n)-1)=-a_{np_1^{-1}}(\varphi(np_1^{-1})-1)$$ $$=(-1)^2a_{np_1^{-1}p_2^{-1}}(\varphi(np_1^{-1}p_2^{-1})-1)$$ $$=\cdots=(-1)^{r-1}a_p(\varphi(p)-1)=(-1)^{r-1}=-\mu(n)$$

(ただし、 $\mu(n)$ はメビウス関数) したがって、

$$(G\text{の生成元の和 })=-(\Phi_{q-1}(x)\text{の}\varphi(q-1)-1\text{次の係数})=\mu(q-1)$$

2018-06-08

【数学】有限体の乗法群と円分多項式の係数

$F_q$を位数$q$の有限体とします。$F_q$の標数を$p$とすれば、ある自然数$f$に対して、 $$q=p^f$$ を満たします。

$G$を$F_q$の乗法群(乗法逆元を持つような元全体からなる群)とすると、$G$の位数は$q-1$になります。

この辺のことは代数学の教科書見れば載っているよく知られた事実です。

$G$の生成元を $$a_1,\dots,a_{\varphi(q-1)}$$ ($\varphi$はオイラー関数)とすると、それらは位数がちょうど$q-1$であるような$F_q$の元なので、$F_q$係数の多項式として $$\prod_{i=1}^{\varphi(q-1)}(x-a_i)=\Phi_{q-1}(x)$$ ($\Phi_n(x)$は$n$位の円分多項式)が成り立ちます。

すると、係数を比較することにより、 $$(G\text{の生成元の和})=-(\Phi_{q-1}(x)\text{の}x^{\varphi(q-1)-1}\text{の係数})$$ が分かります。

ここで、$q-1$が素数の平方で割れる、すなわち、ある素数$l$と自然数$n$に対して、$q-1=l^2n$が成り立つとすると、 $$\Phi_{q-1}(x)=\Phi_{ln}(x^l)$$ となるので(これも円分多項式について載っている代数学の教科書にほぼ載っている)、$\Phi_{q-1}(x)$の$x^{\varphi(q-1)-1}$の係数は$0$になるしかありません。したがって、この場合$G$の生成元の和は$0$です。