はしくれエンジニアもどきのメモ

情報系技術・哲学・デザインなどの勉強メモ・備忘録です。

自然数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}

  • $n$は合成数で,少なくとも1つの素数$p$をもち,pで割ったときに商$q$をもつ.

$\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) } $$