高校数学解説

素因数小ネタ集

素因数

474

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

まえがき

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

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

本文

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

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

記号の定義

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

記号	説明
$d(N)$	$N$の正の約数の個数
$\omega(N)$	$N$の異なる素因数の個数
$\Omega(N)$	$N$の重複も含めた素因数の個数
$\mathbb{N}$	正整数全体の集合
$\mathbb{Z}$	整数全体の集合

素因数の個数

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

性質

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

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

(実は、もう少し厳しい評価ができます。考えてみましょう)
(6) $\Omega(N) \leq \log_2N(N \in \mathbb{N})$も成立します。(証明は(4)とほぼ同じです)
(7) $\omega(a^n-b^n) \geq d(n) - 3(a,b,n \in \mathbb{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$は明らかに相異なるため、$\omega(a^n-b^n) \geq m$が成立します。
$m \geq d(n)-3$により$\omega(a^n-b^n) \geq d(n) - 3$が成立します。

素因数の形式

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

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

$a^p \equiv 1 \pmod 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 \pmod q$となってしまうので$\gcd(a,q)=1$です。
このとき、フェルマーの小定理により$a^{q-1} \equiv 1 \pmod q$です。

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

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

よって、示せました。

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

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

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

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

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

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

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

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

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

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

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

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