高校数学解説

素因数小ネタ集

素因数

447

Advent Math Calendar2022 12/10の記事です。

まえがき

(飛ばして構いません)
iise2xqyzです。Twitter上の名前は頻繁に変わります。
AMC参加者の中では1番弱いと思います。
好きな漫画はギャグ漫画です。多分。

ここには高度な議論や内容は全くないです。できませんでした...
間違い、誤記等あれば、優しく教えてください。

本文

受験数学や競技数学で登場する整数問題を解くときに、さまざまな考え方を用います。
(剰余、不等式評価、素因数、 $v_{p} (n)$ 、位数、etc...)

今回は、素因数に関する話題を扱おうと思います。

記号の定義

$N$ は正整数、 $p$ は素数とします。

記号	説明
$d (N)$	$N$ の正の約数の個数
$ω (N)$	$N$ の異なる素因数の個数
$Ω (N)$	$N$ の重複も含めた素因数の個数
$N$	正整数全体の集合
$Z$	整数全体の集合

素因数の個数

正整数 $N > 1$ に対して、 $N$ の異なる素因数の個数を $ω (N)$ とします。また、 $ω (1) = 0$ とします。
例えば、 $ω (256) = ω (2^{8}) = 1, ω (30) = ω (2 \times 3 \times 5) = 3$ となります。
正整数 $N > 1$ に対して、 $N$ の重複を含めた素因数の個数を $Ω (N)$ とします。また、 $Ω (1) = 0$ とします。
例えば、 $Ω (256) = Ω (2^{8}) = 8, Ω (30) = Ω (2 \times 3 \times 5) = 3$ となります。

性質

$ω (n^{m}) = ω (n) (n, m \in N)$ となります。
$Ω (n^{m}) = m \times Ω (n) (n, m \in N)$ となります。
$ω (N)$ は加法的関数です。 $gcd (a, b) = 1$ となる任意の $a, b \in N$ に対して $ω (a b) = ω (a) + ω (b)$ が成り立ちます。
$Ω (N)$ は完全加法的関数です。任意の $a, b \in N$ に対して $Ω (a b) = Ω (a) + Ω (b)$ が成り立ちます。
$ω (N) \leq \log_{2} N (N \in N)$ が成立します。

$N = 1$ のときは、成立します。
$N (\geq 2)$ の素因数分解による表示を考えると、
$N = p_{1}^{e_{1}} p_{2}^{e_{2}} . . . p_{ω (N)}^{e_{ω (N)}} \geq p_{1} p_{2} . . . p_{ω (N)} \geq 2^{ω (N)}$ により明らかです。

(実は、もう少し厳しい評価ができます。考えてみましょう)
(6) $Ω (N) \leq \log_{2} N (N \in N)$ も成立します。(証明は(4)とほぼ同じです)
(7) $ω (a^{n} - b^{n}) \geq d (n) - 3 (a, b, n \in N, a > b)$ が成立します。

$n$ の正の約数のうち、1,2,6を除いたものを小さい順に $d_{1}, d_{2}, . . ., d_{m}$ とします。
$1 \leq k \leq m$ なる任意の正整数 $k$ に対して、Zsigmondyの定理により
・ $a^{d_{k}} - b^{d_{k}}$ は $a^{n} - b^{n}$ を割り切る
・ $a^{d_{k}} - b^{d_{k}}$ の素因数であって、 $a^{x} - b^{x} (1 \leq x \leq d_{k} - 1)$ を割り切らないものが存在する
ため、 $a^{d_{k}} - b^{d_{k}}$ の素因数であって、 $a^{x} - b^{x} (1 \leq x \leq d_{k} - 1)$ を割り切らないものを $p_{k}$ とすると、
$p_{1}, p_{2}, . . ., p_{m}$ は明らかに相異なるため、 $ω (a^{n} - b^{n}) \geq m$ が成立します。
$m \geq d (n) - 3$ により $ω (a^{n} - b^{n}) \geq d (n) - 3$ が成立します。

素因数の形式

素数 $p$ について $a^{p} - 1$ の素因数の形式が限られるというのは、そこそこ有名な話だと思います。そんな感じの話を集めました。

$a, p \in N$ について、 $a \neq 1, p$ が素数のとき、 $\frac{a^{p} - 1}{a - 1}$ の素因数 $q$ に対して $p = q$ または $q \equiv 1 (\mod p)$

$a^{p} \equiv 1 (\mod q)$ であるとします。このとき、 $\mod q$ における $a$ の位数 $r$ は1 or $p$ です。
また、 $gcd (a, q) \neq 1$ のときは $gcd (a, q) = q$ により $a$ は $q$ の倍数ですが、このとき $a^{p} \equiv 0 \equiv 1 (\mod q)$ となってしまうので $gcd (a, q) = 1$ です。
このとき、フェルマーの小定理により $a^{q - 1} \equiv 1 (\mod q)$ です。

(i) $r = 1$ の場合
$a \equiv 1 (\mod q)$ が成り立ちます。よって、
$\frac{a^{p} - 1}{a - 1} = a^{p - 1} + a^{p - 2} + . . . + a^{2} + a^{1} + 1 \equiv p (\mod q)$ により $p = q$ です。

(ii) $r = p$ の場合
$q - 1$ は $p$ の倍数なので $q \equiv 1 (\mod p)$ です。

よって、示せました。

((1)の系です) $a, p \in N, p$ が素数のとき、 $a^{p} - 1$ の素因数 $q$ に対して $a \equiv 1 (\mod q)$ 又は $p = q$ 又は $q \equiv 1 (\mod p)$
$a, b \in N$ について、 $a^{b} - 1$ の素因数 $p$ に対して $p \equiv 0, 1 (\mod q)$ となる $b$ の素因数 $q$ が存在するか、 $a \equiv 1 (\mod p)$

明らかに $b$ が素数の場合、(2)の事実により成立します。

$b = n (n \in N)$ の場合に成立するならば、 $b = n p (p$ は素数)の場合にも成立することを示します。
(2)の事実で $a$ に $a^{n}$ を代入すると、 $a^{n p} - 1$ の素因数 $q$ について、
・ $q \equiv 0, 1 (\mod p)$
・ $q$ は $a^{n} - 1$ の素因数である

のいずれかが成り立ちます。 $q \equiv 0, 1 (\mod p)$ であれば $p$ が存在し、
$q$ が $a^{n} - 1$ の素因数であれば、仮定から $p \equiv 0, 1 (\mod r)$ となる $n$ の素因数 $r$ が存在するか、 $a \equiv 1 (\mod p)$ です。

よって、 $b = n p$ の場合に示せました。

$b = 1$ に対して、適当な素数を選んで掛ける操作を有限回繰り返すことにより、すべての正整数を表現することができるので、元の命題も示せました。

$p$ を素数とします。このとき $a^{p} - b^{p} (a > b, gcd (a, b) = 1, a, b \in N)$ の素因数 $r$ に対して
$a \equiv b (\mod r)$ 又は $r \equiv 1 (\mod p)$

$gcd (a, b) = 1$ により $a ≢ 0 (\mod r)$ なので、 $b \equiv a x (\mod r)$ となる正整数 $x$ が存在します。
よって、 $a^{p} - b^{p} \equiv a^{p} - (a x)^{p} \equiv 0 (\mod r)$ により $x^{p} \equiv 1 (\mod r)$ です。
このとき、 $\mod r$ における $x$ の位数 $d$ は1 or $p$ です。

(i) $d = 1$ のとき
$x \equiv 1 (\mod r)$ です。よって、 $a \equiv b (\mod r)$ です。

(ii) $d = p$ のとき
フェルマーの小定理により $x^{r - 1} \equiv 1 (\mod r)$ なので、 $r \equiv 1 (\mod p)$ です。

$n, m \in N$ について、 $n^{m} - 1 (\geq 2)$ は $m$ より大きい素因数を持つ。
ただし、 $(n, m) = (3, 2), (2, 6)$ の場合を除く。

$m = 1$ の場合は明らかです。以下 $m \neq 1$ とします。

(i) $m \neq 2$ の場合
$(n, m) \neq (2, 6)$ 及びZsigmondyの定理により、 $n^{m} - 1$ の素因数であって、 $n^{x} - 1 (1 \leq x \leq m - 1)$ を割り切らないものが存在するため、その素因数を $p$ とおきます。
$p \leq m$ と仮定すると、 $n^{p - 1} - 1 \equiv 0 (\mod p)$ ですが、 $1 \leq p - 1 \leq m - 1$ なので、 $n^{x} - 1 (1 \leq x \leq m - 1)$ を割り切らないという仮定に反します。
よって、 $p > m$ により示せました。

(ii) $m = 2$ の場合
$n^{2} - 1$ が2より大きい素因数を持たないとすれば、 $n^{2} - 1 = 2^{k} (k \in N)$ となります。
このとき、 $n - 1 = 2^{a}, n + 1 = 2^{b} (a, b$ は非負整数)とおけるので、 $2^{b} - 2^{a} = 2$ となります。
$\mod 4$ の議論により、 $b > a$ と併せて $a = 0, 1$ なので、それぞれ検証すると $n = 3$ のみとなります。
しかし、これは $(n, m) = (3, 2)$ の例外なので、示せました。

$n, m \in N$ について、 $n^{m} + 1$ は $2 m$ より大きい素因数を持つ。ただし、以下の場合を除く。
・ $n = 1$
・ $m = 1, n$ は2冪
・ $(n, m) = (2, 3)$

Zsigmondyの定理により、 $n^{2 m} - 1$ の素因数であって、 $n^{x} - 1 (1 \leq x \leq 2 m - 1)$ を割り切らないものが存在するので、それを $p$ とおきます。
このとき、 $n^{m} ≢ 1 (\mod p)$ により $n^{m} + 1 \equiv 0 (\mod p)$ です。
$p \leq 2 m$ であるとすれば、 $n^{p - 1} \equiv 1 (\mod p)$ と併せて $p$ の仮定に反するので、 $p > 2 m$ です。