証明路開発支援システム(7) - 非専門的シンギュラリティー研究所

前回の

(6) 単項イデアル整域は一意分解整域となります。

の証明は

『可換環論の勘どころ (数学のかんどころ 32)』定理 2.54

を参考にしているようですが

『代数学２　環と体とガロア理論　第２版』定理 1.11.18

のような証明が一般的と思われます。

この証明をプログラミング言語のコードのような形にしたものを「モノイドの素因数分解(1) - 非専門的シンギュラリティー研究所」に書いているのですが、わかりにくいので書き直します。

プログラミング言語形式の証明

以下の C# のコードを考えます。

        private bool IsIrreducible(int number)
        {
            if (number <= 1) return false;
            for (int i = 2; i <= Math.Sqrt(number); i++)
            {
                if (number % i == 0) return false;
            }
            return true;
        }

        private (int, int) Divide(int number)
        {
            for (int i = 2; i <= Math.Sqrt(number); i++)
            {
                if (number % i == 0) return (i, number / i);
            }
            return (number, 1);
        }

        private List<int> Factorize(int number)
        {
            var factors = new List<int>();
            if (IsIrreducible(number))
            {
                factors.Add(number);
            }
            else
            {
                var (factor1, factor2) = Divide(number);
                factors.AddRange(Factorize(factor1));
                factors.AddRange(Factorize(factor2));
                factors.Sort();
            }
            return factors;
        }

IsIrreducible

既約元かどうかを調べます。

Divide

既約ではない元を二つの(1ではない)因子に分解します。

Factorize

素因数分解する部分関数です。この関数が停止すれば素因数分解できます。

IsIrreducible(number) ではない(既約ではない)とき
- number > factor1
- number > factor2

となります。よって

引数に対する
- factor1 を、引数に対する
  - factor1 を $n_{11}$
  - factor2 を $n_{12}$
- factor2 を、引数に対する
  - factor1 を $n_{21}$
  - factor2 を $n_{22}$

のように書くとすると
$n > n_{i_1} > n_{i_1 i_2} > n_{i_1 i_2 i_3} > \cdots$
( $i_j = 1, 2$ 、各 $n_{i_1 i_2 \cdots i_k}$ は既約ではない)となります。この不等式の列が無限に続くことはない( $n - 1$ 回以内で $1$ になる)ので、ある $n_{i_1 i_2 \cdots i_k}$ は既約となります。

よって Factorize は任意の正の整数の引数に対して停止し、素因数分解できます。

正の整数の場合や多項式の場合は、引数によって呼び出しの深さが決まるので停止すると言えるのですが、一般の単項イデアル整域の場合は停止する理由になることを説明する必要があるかもしれません。単項イデアル整域の場合の一般的な証明は、このプログラムと同様のことをやっているので停止すると言えるはずです。

可換環論の勘どころ (数学のかんどころ 32)

作者:後藤四郎
共立出版