算術の基本定理
$ \forall n\in\Bbb{N}\exists!q:\Bbb{P}\rightarrow\Bbb{N}\cup\{0\};n=\prod_{p\in\Bbb{P}}p^{q(p)}
意外とシンプルな論理式で表せたtakker.icon
任意の正整数は、1 を除いて、一つまたはそれ以上の素数の積として(因子の順番の違いを除いて)ただ一通りに表すことができる $ \exists!ただ一つ存在
「ただ一つ存在するヨ(よ)!」で覚えたhatori.icon
existのEだと思ってた(理由はよくわからんがひっくり返っている、任意を表す記号もAがひっくり返っている)inajob.icon
拡張
1を全ての素数の0乗の積$ 1=2^0 3^0 5^0 7^0\cdotsで表せば、任意の正整数に拡張できる
こういう表し方、何とか進数みたいな名前ついてないのかなyosider.icon
「p 進数」とは「2進数」や「3進数」の総称に過ぎないらしいので違いそうyosider.icon
それぞれのpごとに考えるものっぽい
$ x=\operatorname{sgn}(x) \cdot p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{n}^{e_{n}} \quad\left(x \in \mathbb{Q}, \ e_{i} \in \mathbb{Z}\right)
$ e_iを$ xの$ p_i進付値という
暗号化に役立ちそうU.icon
例えば$ 7,19,3,11 \cdots のように素数の並びを任意に設定すればシンプルかつ高度な暗号になりそう
1 = 0000...
2 = 1000...
3 = 0100...
4 = 2000...
5 = 0010...
6 = 1100...
符号函数$ \rm sgnを使えば、$ \Bbb{Z}\setminus\{0\}に拡張できる
$ \forall n\in\Bbb{Z}\setminus\{0\}\exists!q:\Bbb{P}\rightarrow\Bbb{N}\cup\{0\};n=\mathrm{sgn}(n)\prod_{p\in\Bbb{P}}p^{q(p)}
$ \mathcal{P}(8)(2)=3
$ \mathcal{P}(8)(3)=0
$ \mathcal{P}(36)(3)=2
負の整数も含めて、$ a = \operatorname{sgn}(a) \prod_p p^{v_{p}(a)}, $ v_{p}: \mathbb{Z} \rightarrow \mathbb{N} \cup\{0\}と書ける
where$ v_{p}(a):=\left\{\begin{array}{ll} e_{i}, & \left(\exists i \ p = p_{i} \right. ) \\ 0, & \left(\forall i \ p \neq p_{i} \right. ) \end{array}\right.
$ a=\operatorname{sgn}(a) \cdot p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{n}^{e_{n}} とする
$ vが$ \mathcal{P}に相当する
$ v:\mathbb{P} \rightarrow (\mathbb{Z} \rightarrow \mathbb{N} \cup \{0\})
$ \mathbb{P}が先に来る?
やっぱり素数ごとに考えるという方向性が多いのかな
$ v_p(a)は$ \mathrm{ord}_p(a)とも書かれる
よく使われる記号があったの/icons/知らんかった.icontakker.icon
素数$ pと有理数$ xに対して$ v_p(x)を、$ pが$ xを有理数上で割り切る最大の指数として定める
$ x = \frac{a}{b}\cdot p^n $ (a,b,p)は互いに素、$ a>0なる最大の$ n
例: $ v_2\left(\frac{4}{7}\right) = v_2\left(2^2 \cdot \frac{1}{7}\right) = 2
$ 0をこの定理に含めるのは無理
$ 0 = 0^l2^m3^n5^o\cdots\ (l\neq 0,\ m,n,o > 0)と、指数に任意性が生じてしまう
0の場合は便宜上すべての指数を無限大とするらしい
0はすべての素数で無限回割り切れると考える
うーん、好きなやり方じゃないなあtakker.icon
折角整数の範囲で閉じていたのに、無限という取り扱い注意なやばいやつが出てきてしまう
以前任意の指数にできることは変わりない
↓の性質を考えるときに(一応)整合性が取れる値ということで$ \inftyが選ばれている模様yosider.icon
実利があるのかわからんけど
性質
$ v_{p}(m \cdot n)=v_{p}(m)+v_{p}(n)
$ \logと同じ
$ \small\operatorname{sgn}(mn) \prod_{p} p^{v_{p}(mn)} = mn = \operatorname{sgn}(m) \prod_{p} p^{v_{p}(m)} \cdot \operatorname{sgn}(n) \prod_{p} p^{v_{p}(n)} = \operatorname{sgn}(mn) \prod_{p} p^{v_{p}(m) + v_p(n)}
素因数分解の一意性より$ v_{p}(mn) = v_{p}(m) + v_{p}(n)
$ v_{p}(m+n) \geq \min \left\{v_{p}(m), v_{p}(n)\right\}
例: $ v_2(4+6) = v_2(2 \cdot (2 + 3)) = 1 \geq \min\{v_2(4), v_2(6)\} = \min\{2,1\} = 1
$ v_p(m) \neq v_p(n)ならば等号成立
$ mが$ nで割り切れる$ \iff$ \forall{p \in \mathbb{P}} \quad v_p(n) \leq v_p(m)
$ x \in \mathbb{Z} \iff \forall p \in \mathbb{P} \quad v_p(x) \geq 0