自然数nが√n以下のすべての素数で割り切れなければ，nは素数であることの証明
自然数nが√n以下のすべての素数で割り切れなければ，nは素数であることの証明
自然数$n$が$\sqrt{n}$以下のすべての整数で割り切れなければ，$n$は素数であることの証明メモ．
対偶
対偶をとると，
「自然数$n$が素数でない（合成数）ならば，$n$は$\sqrt{n}$以下のいずれかの素数で割り切れる．」
直観的な理解
$n = pq$とし，$p, q$を素数と仮定した場合に，$p > \sqrt{n}, q > \sqrt{n}$であると，$n > pq$となり成り立たなくなる． なので，$p < \sqrt{n}$ または $q < \sqrt{n}$となる．
証明
命題$S(p)$:「自然数$n$が素数でない（合成数）ならば，$n$は$\sqrt{n}$以下のいずれかの素数$p$で割り切れる．」
precondition: - $n$は自然数 \begin{eqnarray} n \in \mathbb{N} \end{eqnarray}
$\mathbb{P}$を素数集合とすると，
\begin{eqnarray} n = pq \ p \in \mathbb{P}\ q \in \mathbb{N} \end{eqnarray}
-
case $q \in \mathbb{P}$:
- if $p \leq \sqrt{n}$: $p | n \in S(p)$
-
if $p > \sqrt{n}$:
- if $q > \sqrt{n}$: $p \cdot q = \sqrt{n}\sqrt{n}, n \neq pq$ となり前提を満たさないので， $$ q \leq \sqrt{n} $$
- if $q \leq \sqrt{n}$: $$ q | n \in S(q) $$
-
case: $q \notin \mathbb{P}$:
$q = p_1 \cdot m, p_1 \in \mathbb{P}, m \in \mathbb{N}$
- if $p \leq \sqrt{n}$: $$ p | n \in S(p) \\ $$
- if $p > \sqrt{n}$: $q \leq \sqrt{n} \to p_1 m < \sqrt{n} \to p_1 < \sqrt{n}, m < \sqrt{n}$ $$ p_1 | n(= pp_1m) \in S(p_1) $$
$$ \therefore {p \in \mathbb{P} \mid n=pq,q \in \mathbb{N}, S(p) } $$
