合成数 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 で割り切れます
 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください