素因数小ネタ集
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$です。
あとがき
今回のAMC、面白そうと思い、衝動的に参加しました。が、
書く内容がありません。一応テーマだけは決めているのですが、どうしても話が膨らみませんでした。どうしましょうか。
なぜ話が膨らまないか、
それはテーマの範囲が狭いことにありました。そこで、
素因数の個数のおはなし→素因数の種類のおはなし→素因数小ネタ集
というようにテーマを勝手に変更したところ、そこそこの分量の記事が書けそうなので、嬉しくなりました。
さて、私はこのような執筆活動はおそらく初めてなので、
- 記事の適切な分量
- 書いていいこと悪いこと
等、一切分かりません。
つまり、必然的に前日までの記事を参考にすることとなるのですが、例えば、分量については、Twitter上の情報や記事を見て、3000～4000文字程度あれば問題はないだろうと判断しました。
12/8,9の記事を見て、言い方は悪いかもしれませんが、こんな緩い内容でも大丈夫ということがわかり、
きっと自分のようなクソ記事でも大丈夫だろうという自信が持てました。本当にありがとうございます。
(是非見てください！！！)
12/8 :
(AMCday8)OMCでの登場人物ランキング+他
12/9 :
やっと競プロに手を付けたお話(AMC2022 Day 9)
ところで、前日になっても記事が完成しません。締め切りに追われております。やばいですね。
当日になっても記事が完成しません！本当にやばい
証明を水増し増やして、完成まで漕ぎ着けました！
正直、もう少し後の日にしてもよかったのかもな〜と後悔しています。