合成数 N は 1 より大きく √N 以下の約数をもちます

 今回からいよいよ素数に関する定理が登場します。

素数と合成数

 まずは素数と合成数を定義しておきます。

 1 以外の自然数で、1 と 自身以外に正の約数をもたない数を 素数 (prime number)、1 でも素数でもない数を 合成数 (composite number) と定義します。

 合成数については「 1 と自分自身以外に最低でも 1 つの約数をもつ」と言いかえることもできます(後述する定理 B1 の証明でこの事実を用います)。

 素数を小さい順に並べてみます。
 
\[2,\:3,\:5,\:7,\:11,\:13,\:17,\:19\:\cdots\]
 合成数は 1 と素数以外の数なので、素数同士の間隔を埋めるように
 
\[4,\:6,\:8,\:9,\:10,\:12,\:14,\:15\:\cdots\]
となります。1 は素数でも合成数でもないので、どちらにも含まれていません。つまり自然数は 1 と素数と合成数で構成されます。
 

合成数 N は 1 より大きく √N 以下の約数をもちます

 合成数 12 の約数を全て並べてみます。
 
\[1,\:2,\:3,\:4,\:6,\:12\]
 12 の平方根は 3.464 ですが、この値より小さく、1 以外の約数 (2 と 3) が存在しています。実はどんな合成数 $N$ についても、1 より大きく $\sqrt{N}$ 以下の約数をもつことが知られています。

[定理 B1] 合成数 $N$ は $1\lt a\leq\sqrt{N}$ を満たすような約数 $a$ を 1 個以上もちます。

[定理 B1 の証明] $N$ は合成数なので、1 ではない 2 つの数 $a$ と $b$ の積に分解できるはずです。すなわち小さくないほうを $b$ として
 
\[N=a\times b\quad (1\lt a\leq b,\quad a,\:b\in\mathbb{Z})\]
と表すことができます。$1\lt a\leq b$ なので
 
\[N=a\times b\geq a\times a=a^2\]
 すなわち $a\leq\sqrt{N}$ が示されました。(証明終)
 

ガウスの和 ポアンカレの和―数論の最前線から

中古価格
¥2,250から
(2017/9/1 13:22時点)

1 より大きな整数は 1 個以上の素因数をもちます

 たとえば 100 という数を適当に分解して
 
\[100=4\times 25\]
と表したとします。さらに 4 も分解してみると
 
\[4=2\times 2\]
というように素数 2 が現れました。このように、合成数の中に積の形で含まれる素数のことを 素因数 とよびます。一般に 1 より大きな整数は、上のように積の形に分解していけば必ずどこかで素因数が現れます。あまりに自明なことではありますが、これも定理として載せておきます。

[定理 B2] 1 より大きな整数 $N$ は 1 個以上の素因数をもちます。

[定理 B2 の証明]
 $N$ が素数であれば、$N$ 自身が素因数です。$N$ が合成数であれば、
 
\[N=a_1\times b_1\quad (1\lt a_1\lt N)\]
のように積の形に分解することができます。$a_1$ が素数であれば、それが素因数です。$a_1$ が合成数であれば、
 
\[a_1=a_2\times b_2\quad (1\lt a_2\lt a_1)\]
のように積の形に分解することができます。$a_2$ が素数であれば、それが素因数です。これを繰り返していくと $a_k$ は単調減少かつ $a_k\neq 1$ なので、有限回操作で必ず素数となります。(証明終)
 

整数 ab が素数 p で割り切れるならば、a, b のいずれかは p で割り切れます

 「36 = 4 × 9 は 2 で割り切れるので、4 は素数 2 で割り切れます」というような当たり前のことを述べているのが次の定理です。

[定理 B3] 素数 $p$, 整数 $a,\:b$ について
\[p\:|\:ab\quad\Longrightarrow\quad p\:|\:a\:\:\vee \:\: p\:|\:b\]が成り立ちます。

 $\vee$ は論理和の記号、すなわち「または」を表す記号です。
 $A\vee B$ は $A$ と $B$ がともに成り立つ場合も含みます。したがって、たとえば「 108 = 9 × 12 は素数 3 で割り切れて、9 も 12 も 3 で割り切れる」というようなことも含まれています。

[定理 B3 の証明] 証明には定理 A11
 
\[(a,\:b)=1,\:a\:|\:bc\quad \Longrightarrow\quad a\:|\:c\]
を用います。素数 $p$ の約数は 1 か $p$ です。$p\:|\:a$ ならば定理は成り立っています。$a$ が $p$ で割り切れないときは
\[(p,\:a)=1,\:p\:|\:ab\]
なので $p\:|\:b$ となります。(証明終)
 

ガウス 整数論への道 (双書―大数学者の数学)

中古価格
¥1,392から
(2017/9/1 13:22時点)

整数 n が素数 p, q で割り切れるならば n は pq で割り切れます

 次の定理もほぼ自明としてよいぐらいの事実です。たとえば「 20 は相異なる素数 2 と 5 で割り切れるならば、20 は 2 × 5 = 10 で割り切れる」というようなことを述べています。

[定理 B4] 素数 $p,\:q\:(p\neq q)$, 整数 $n$ について
\[p\:|\:n,\quad q\:|\:n\Longrightarrow\quad pq\:|\:n\]が成り立ちます。

[定理 B4 の証明] この定理の証明にも定理 A11
 
\[(a,\:b)=1,\:a\:|\:bc\quad \Longrightarrow\quad a\:|\:c\]
を用います。$p\:|\:n,\: q\:|\:n$ なので整数 $a,\:b$ を用いて
 
\[n=pa=qb\]
と表すことができます。$(p,\:q)=1,\:p\:|\:qb$ なので $p\:|\:b$ であり、整数 $k$ を用いて
 
\[b=pk,\quad n=pqk\]
と表せます。よって $pq\:|\:n$ となります。(証明終)
 

1 より大きな整数は有限個の素数の積で表せます

 たとえば 60 という数は
 
\[60=2^2\times 3\times 5\]
というように素数の積で表すことができます。そして素数の順序を考えなければ、この分解方法はただの一通りしかありません。これも当たり前のことではありますが、数論の根幹をなすような重要な定理です。

[定理 B5] 1 より大きい任意の整数 $n$ は有限個の素数の積で表せます。またこのとき素因数分解の順序を無視すれば、その分解の仕方は唯一通りとなります。

[定理 B5 の証明]
① 有限個の素数の積で表せることの証明
 $n$ が素数であれば、$n=n$ というように、素数 1 個の積で表せるので定理は成り立ちます。したがって $n$ が素数でない場合を考えます。証明には数学的帰納法を用います。まず最小の合成数である 4 について、4 よりも小さく 1 よりも大きな 2, 3 はどちらも素数なので素因数分解できます。次に 1 より大きく $n$ より小さい整数は全て素因数分解できるような $n$ を選びます。そのとき $n$ の 1 以外の約数のうち、最小の数は素数となります。それを $p$ とすると、正整数 $a$ を用いて
 
\[n=pa\]
と表すことができます。このとき $a\lt n$ なので仮定により
 
\[a=p_1p_2\:\cdots\:p_k\]
と表せます。よって
 
\[n=pa=pp_1p_2\:\cdots\:p_k\]
となって $n$ も素因数分解することができます。$n=4$ は素因数分解できるので、次の合成数 $n=6$ も素因数分解できて、またその次の合成数 $n=8$ も素因数分解できて ...... これを繰り返して全ての合成数 $n$ について素因数分解できます。(証明終)

② 素因数分解の仕方が一通りであることの証明
 $n$ が 2 通りに素因数分解されたと仮定します。
 
\[n=p_1p_2\:\cdots\:p_j=q_1q_2\:\cdots\:q_k\]
 $p_1,\:p_2,\:\cdots,\:p_j$, $q_1,\:q_2,\:\cdots,\:q_k$ は全て素数です。
 重複があっても構いません。ここで定理 B3

[定理 B3] 素数 $p$, 整数 $a,\:b$ について
\[p\:|\:ab\quad\Longrightarrow\quad p\:|\:a\:\:\vee\:\:p\:|\:b\]

により、$p_1$ は $q_1,\:q_2,\:\cdots,\:q_k$ のうちどれかを割り切ることができます。
 
\[p_1\:|\:q_1q_2\:\cdots\:q_k\]
 $q$ の添え字の番号はどのように入れ替えてもかまわないので、右辺の素因数のうち、$p_1$ で割り切るものを $q_1$ に選びます。しかし $p_1,\:q_1$ はともに素数なので $p_1=q_1$ です。そこで、この数で両辺を割ると
 
\[p_2p_3\:\cdots\:p_j=q_2q_3\:\cdots\:q_k\]
となります。同じように $p_2=q_2,\:p_3=q_3$ として次々に割っていくと、仮に $j\gt k$ とした場合、
 
\[p_{k+1}\:\cdots\:p_j=1\]
となってしまいますが、これは明らかに矛盾しています。よって $j=k$, すなわち素因数分解の方法は唯の一通りであることが示されました。(証明終)
 

標準素因数分解

 ある数 $n$ を素因数分解したとき、同じ種類の素因数をまとめて

\[n=p_1^{m_1}p_1^{m_1}\cdots p_k^{m_k}\]

と書くような記述の仕方を 標準素因数分解 とよびます。たとえば 480200 を標準素因数分解すると
 
\[480200=2^3\,5^2\,7^4\]
のように表すことができます。
 

素因数分解を用いて GCD と LCM を計算します

 素因数分解を用いると最大公約数 (GCD) と最小公倍数 (LCM) を簡単に計算することができます。たとえば 126 と 600 をそれぞれ素因数分解すると
 
\[\begin{align*}126=2^1\times 3^2\times5^0\times 7^1\\[6pt]
600=2^3\times 3^1\times 5^2\times 7^0\end{align*}\]
となります。比較しやすくするために、指数部分が 0 や 1 である場合も書いてあります。最大公約数は各因数からベキ指数の小さいほう(正確に言うと大きくないほう)を選んで掛け合わせます:
 
\[(126,\:600)=2^1\times 3^1\times 5^0\times 7^0=6\]
 最小公倍数はベキ指数の大きいほう(正確に言うと小さくないほう)を選んで
 
\[\{126,\:600\}=2^3\times 3^2\times 5^2\times 7^1=12600\]
と計算できます。一般には次のように計算します。

[定理 B6] 2 つの正整数 $a,\:b$ を素因数分解して
\[\begin{align*}a=p_1^{u_1}\,p_2^{u_2}\,\cdots\,p_i^{u_i}\,\cdots\\[6pt]
b=p_1^{v_1}\,p_2^{v_2}\,\cdots\,p_i^{v_i}\,\cdots
\end{align*}\]のように表せたとします。ただし $u_i,\:v_i$ は 0 または正整数です。このとき
\[\begin{align*}\mathrm{min}(u_i,\:v_i)=s_i\\[6pt]
\mathrm{max}(u_i,\:v_i)=t_i\end{align*}\]とおくと、最大公約数と最小公倍数はそれぞれ
\[\begin{align*}(a,\:b)=p_1^{s_1}\,p_2^{s_2}\,\cdots\,p_i^{s_i}\,\cdots\\[6pt]
\{a,\:b\}=p_1^{t_1}\,p_2^{t_2}\,\cdots\,p_i^{t_i}\,\cdots\end{align*}\]と計算することができます。

 ここで $\mathrm{min}(a,\:b)$ は $a,\:b$ のうち大きくないほう、$\mathrm{max}(a,\:b)$ は$a,\:b$ のうち小さくないほうを表します。詳しくは 小さくない数と大きくない数 の記事を参照してください。


 

コメントをどうぞ

メールアドレスが公開されることはありません。