素因数分解を利用した式変形

数オリ,整数,素因数分解

3227

今回は競技数学やってる人は大体知っているけどちゃんと言語化されているか怪しい事について書きます(なのでそこまで難しくは無いはず). IMOとかには出にくい内容かも知れないけどOMCには結構出そう.
まずは素因数分解について.

算術の基本定理, 素因数分解の一意性

全ての正整数$n$は$\displaystyle\prod_p p^{v_p(n)}$($p$は全ての素数を渡る, $v_p(n)$は$p$毎に定まる非負整数で有限個を除いて$0$)の形に一意的に表示出来る.

ここでは素因数分解を利用して式変形が出来るという話をします.
次に, いろいろな数論関数の定義と基本的性質を確認します.

$n$を正整数, $x$を実数とする.

$d(n)(=\tau(n)=\sigma_0(n))$を$n$の正の約数の個数とする.
$\sigma(n)(=\sigma_1(n))$を$n$の正の約数の総和とする.
$\sigma_x(n)$を$n$の正の約数の$x$乗の総和とする.
$\varphi(n)$を$n$以下で$n$と互いに素な正整数の個数とする.
$\omega(n)$を$n$の素因数の個数とする.
$\Omega(n)$を$n$の$v_p(n)$の総和とする.
$\mu(n)$を$n$が平方因子を含まないなら$(-1)^{\omega(n)}$, 含むなら$0$として定める. (メビウス関数)

加法的関数, 乗法的関数

関数$a:\mathbb N\to\mathbb C$が任意の互いに素な正整数$m,n$に対し$a(mn)=a(m)+a(n)$を満たすとき$a$を加法的関数, $a(mn)=a(m)a(n)$を満たすなら乗法的関数という.
また任意の正整数$m,n$に対し$a(mn)=a(m)+a(n)$を満たすとき$a$を完全加法的関数, $a(mn)=a(m)a(n)$を満たすなら完全乗法的関数という.

上の関数は加法的関数か乗法的関数の例になっている. この関数のクラスは約数全体に関する操作に対してとても良く振る舞う.

加法的関数, 乗法的関数の基本性質

$a,b$を加法的関数, $c,d$を乗法的関数とし, $x,y$を複素数とする. (ただし指数の分岐等が発生する場合は考えない)

$xa(n)+yb(n)$は加法的関数, $x^{a(n)}$は乗法的関数, $c(n)^xd(n)^y$は乗法的関数, $\log_x c(n)$は加法的関数. (また完全同士の演算等で完全性は保たれる)
$a(n)=\displaystyle\sum_p a(v_p(n))$, 特に$a$が完全加法的関数なら$a(n)=\displaystyle\sum_p a(p)v_p(n)$.
$c(n)=\displaystyle\prod_p c(v_p(n))$, 特に$c$が完全乗法的関数なら$c(n)=\displaystyle\sum_p c(p)^{v_p(n)}$.
$\displaystyle\sum_{d|n}c(n)=\prod_p\sum_{i=0}^{v_p(n)}c(p^i)$, 特に$c$が完全乗法的関数なら$\displaystyle\sum_{d|n}c(n)=\prod_p\frac{c(p)^{v_p(n)+1}-1}{c(p)-1}$.($c(p)=1$のときは分数の値は$v_p(n)+1$としておく)

この定理から分かるよう, これらの関数を扱う際素数毎に考えると言うことが有効な事が多い. $\sigma_x,\varphi$が乗法的関数になっているのは組み合わせ的考察によって分かる. 他は定義から加法関数或いは乗法的関数である事は明らかだろう. あとは平方剰余記号が完全乗法的関数だったりする. あとは$\log$が加法的関数, 冪乗や恒等写像が完全乗法的関数である事に注意すれば良いだろう.

$n=\displaystyle\prod_p p^{v_p(n)}$を正整数, $x$を実数とする.

$d(n)=\displaystyle\prod_p(v_p(n)+1)$
$\sigma(n)=\displaystyle\prod_p \frac{p^{v_p(n)+1}-1}{p^x-1}$
$\sigma_x(n)=\displaystyle\prod_p\frac{p^{xv_p(n)+1}-1}{p-1}$
$\varphi(n)=\displaystyle\prod_{p|n}p^{v_p(n)-1}(p-1)$
$\displaystyle\sum_{d|n}\mu(d)=\begin{cases}1\ (n=1)\\0\ (n>1)\end{cases}$

少し例を見ていきましょう.まずは OMC107F .

OMC107F

正の整数$m$に対し, その正の約数すべての相加平均を$f(m)$で表します. $a$ が$m$の正の約数であるとき, $f(a)$が常に整数になるような, $1$以上$100$以下の整数$m$の総和を求めてください.

まずは$f(m)$が求まらないかと考えると$f(m)=\dfrac{\sigma(m)}{d(m)}$と書けます. これはもう素数毎に考えた方が良さそうなので$f(m)=\displaystyle\prod_p\frac{p^{v_p(m)+1}-1}{(v_p(m)+1)(p-1)}$ としちゃいます. ここで条件をよく見ると$n$の任意の約数$a$についてと$f(a)$が整数になって欲しいと書いているので$\dfrac{p^{v_p(a)+1}-1}{(v_p(a)+1)(p-1)}$は整数になってくれそう. 実際素冪の素因数を考えれば良いですね. これで完全に素数毎に考えることが出来ます.
$p$を素数, $v_p(m)$を正整数としたとき任意の正整数$i$について$\dfrac{p^{i+1}-1}{(i+1)(p-1)}$が整数になる$p,m$の条件を知ればよいです. ここで$m\leq100$なので$p,i$が大きい状況は考えなくて良く. 見通しが立ってきます.
$(i)\ i=1$のとき
$\dfrac{p+1}2\in\mathbb Z$より$p\neq2$なら条件を満たす. 以下$p$は奇素数としてよい.
$(ii)\ i=2$のとき
そもそも$p=3,5,7$だけ考えればよい. 条件は$3|p^2+p+1$だから条件を満たすのは$p=7$のときのみ.
$(iii)\ i>2$のとき
$p=7$しかあり得ないが$m$が$100$以下なので考える必要は無い.
よって条件を満たす$m$は$2,9,25$を因数として持たないもの. これは奇数全体から$9,27,45,63,81,99,25,75$を除いたものなので求める値は$50^2-9\cdot6^2-100=2076$である.

約数系の議論で素数毎に考えるモチベーションが分かっただろうか, (素数毎に考えるのは約数系の議論に限らず例えば中国の剰余定理を使う問題とかも素数毎に考えようとすると上手く行くケースが多い)

次の 2021ChinaTST test3P4 もかなり典型的な使い方である.

2021ChinaTST test3P4

$$ \sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\left\lfloor \frac{n}{k} \right\rfloor \tau (k)^2 \le \sum_{m=1}^n5^{\Omega (m)} .$$
を示せ.

かなり約数系の議論をしそうである. さらにガウス記号系の関数(床, 天井, 割った商, 余り)は総和や階差をとると約数が絡んでくる場合が多いことを知っていると考察が進むだろう. ということで今回は$\left\lfloor \dfrac{n}{k} \right\rfloor \tau (k)^2$を約数が絡んだ形で表すことを考えれば良さそうである. すると思いつくのは$\displaystyle\left\lfloor\frac{n}{k}\right\rfloor\tau(k)^2=\sum_{ki\leq n}\tau(k)^2$と見なして和を取る順序を変えた
$$\sum_{k=1}^n\left\lfloor \frac{n}{k} \right\rfloor \tau (k)^2=\sum_{m=1}^n\sum_{d|m}\tau(d)^2$$
を考えると良さそう. すると, $5^{\omega(m)}\leq\sum_{d|m}\tau(d)^2\leq5^{\Omega(m)}$っぽい気がする. これは全部乗法的関数なので素数毎に考えられそう! つまり$\displaystyle\sum_{d|m}\tau(d)^2=\prod_{p}\sum_{i=0}^{v_p(m)}\tau(p^i)=\prod_{p}\sum_{i=0}^{v_p(m)}(i+1)^2=\prod_{p}\dfrac{(v_p(m)+1)(v_p(m)+2)(2v_p(m)+3)}6$

$\displaystyle5^{\omega(m)}=\prod_{p|m} 5, 5^{\Omega(m)}=\prod_p5^{v_p(m)}$に注意すれば($x=v_p(m)$と置き換えて)$x\geq1$のとき$5\leq\dfrac{(x+1)(x+2)(2x+3)}6\leq5^x$を示せば良い.(これは素冪の時の必要条件でもある$5^{\omega(m)}\leq\sum_{d|m}\tau(d)^2\leq5^{\Omega(m)}$と同値)ここまで来たら何やっても示せますね. (指数関数$>$多項式を示す方法は二項定理, 帰納法, 微分が主な手法としてあるが今回は階差を取ると簡単になるので階差の大小を二項定理で示して帰納法を回すのが良いと思います)

ガウス記号と約数が絡む問題を置いておきます.
サーモン杯問題1

サーモン杯P1

数列$\{ a_n \}$を次のように定めます.
$a_1=1$
$a_n=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3\rfloor}+\dots+a_{\lfloor n/n\rfloor}　(n>1)$
$a_{100}=658$です.$a_{110}$を求めてください.

ごち数のこの問題もそうですね.

Poland MO 2018 問4

$n$を正の整数とする. 平方因子をもたず, かつ$n$を$k$で割った商が奇数であるような, $n$以下の正の整数$k$は奇数個であることを示せ.

ごち数の解答では階差を考えていますが, ここでは自分が思いついた別解を紹介します.
まず, 奇数という条件が鬱陶しいです. これを解消するために何かが奇数個である事を示すならその何かに対応する奇数の値の総和が奇数である事を示せば良い. という定石を用いて$k$の総和が奇数である事を示そうとします.(丁度$k$が奇数という条件があったので) すると総和に偶数を足しても偶奇は変わらないので平方因子を持たない$k$で$n$以下のものに対する$\left\lfloor \dfrac nk\right\rfloor$の総和が奇数である事を示せば良いです. 平方因子の有無で変わるといえばメビウス関数$\mu(k)$ですね. 丁度平方因子を持たないときも偶奇を変えないので$\displaystyle\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor$が奇数である事を示せば良いということになります. ここで問題2と同じように$\displaystyle\mu(k)\left\lfloor\frac nk\right\rfloor=\sum_{ik\leq n}\mu(k)$として和の順序を交換すると$\displaystyle\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor=\sum_{m=1}^n\sum_{d|m}\mu(d)=1$(定理3)となって証明が終わります.

少しガウス記号から離れて別の問題を見ていきましょう.
2016ISLC2

2016ISLC2

正整数$n$であって全ての$n$の正の約数を長方形のマス目に以下の条件を満たすように書き込むことが出来るものを全て求めよ:

各マスには相異なる$n$の正の約数が書き込まれている.
縦の列に書かれた数の総和は全て等しい.
横の列に書かれた数の総和は全て等しい.

ちょっと実験すれば$n=1$以外はダメそうという気分になります. とりあえず状況設定として長方形のマス目の縦を$a$行, 横を$b$列とすると, $ab=d(n)$となります. ここから上手く行かなさそうという感覚を言語化していきます. まずマス目に条件を満たす書き込み方が存在すると仮定すると, $n$の約数の大きさはある程度均等にばらけている事が必要です.(というのもどの行(または列)で書かれている数の和が等しいので行ごとにある程度大きい値が必要) 一方$n$の約数は小さい値は多くて大きい値は少ないです. これはまずそう, だから約数の大きさ系の不等式評価をすれば良いですね. 不等式評価なので$a,b$の大小関係も決めておいた方が良くて$a\leq b$とすると$ab=d(n)$だから$a\leq\sqrt{d(n)}\leq b$となります. さらに$n$がどこかのマスに書き込まれているので各列に書かれている数の総和は$n$以上なので鳩ノ巣原理を考えると各列に$\dfrac nb$以上の元が書かれています. ここから先は全体に注目するか部分に注目するかで二通りの方法があります.
$(i)$全体に注目する方法
約数の総和は$bn$より大きいので$\sqrt{d(n)}n\leq\sigma(n)$が成り立つはずです.これは素数毎に考えられそうな式なのでそのような変形をすると$\displaystyle\prod_p\dfrac{p^{v_p(n)+1}-1}{p^{v_p(n)}\sqrt{v_p(n)+1}(p-1)}>1$となります.
ということで$v_p(n)=x$として$\dfrac{p^{x+1}-1}{p^x\sqrt{x+1}(p-1)}$を考察する. $\dfrac{p^{x+1}-1}{p^x\sqrt{x+1}(p-1)}\leq\dfrac1{\sqrt2}\left(1+\dfrac{p^x-1}{p^x(p-1)}\right)<\dfrac1{\sqrt2}\left(1+\dfrac{5p^x}{4p^{x+1}}\right)\leq\dfrac{5}{4\sqrt2}<1$($p\geq5$のとき)
より$p=2,3$を考える. $p=3$のとき$\dfrac{3-3^{-x}}{2\sqrt{x+1}}$の評価をすれば良い. $x>1$のときは明らかにこれは$\dfrac{\sqrt3}{2}<1$未満. $x=1$のときは$\dfrac{4}{3\sqrt2}<1$となる.
$p=2$のとき, $\dfrac{2^{x+1}-1}{2^x\sqrt{x+1}}$の評価である. $x\geq3$のときは$\dfrac{2^{x+1}-1}{2^x\sqrt{x+1}}\leq\dfrac{2^{x+1}-1}{2^{x+1}}<1$と簡単に議論できる. $x=1$のとき値は$\dfrac{3}{2\sqrt2}>1$, $x=2$のとき値は$\dfrac{7}{4\sqrt3}>1$となる. $1$を越えているのが少し厄介だが他の素因数が$1$未満なのでなんとか出来そう.
実際求まった上界達を小さい順に並べると$\dfrac{\sqrt3}{2}<\dfrac{5}{4\sqrt2}<\dfrac{4}{3\sqrt2}<\dfrac{7}{4\sqrt3}<\dfrac{3}{2\sqrt2}$となっているので素因数が二つあるときあり得る最大の値は$1$であるので$n=2,4,6$のときのみ考えれば良い. これらは明らかに上手く行かない. よって求める値は$n=1$のみ.

この方法は偶然上手く行った感のある解答である. 大きい約数が沢山あるという違和感を全部総和をとるという方法で表現していますが少し燃費が良くなさそうです. また, あまり約数を並べるという乗法を消化し切れた感じがしない. なので$\displaystyle\prod_p\dfrac{p^{v_p(n)+1}-1}{p^{v_p(n)}\sqrt{v_p(n)+1}(p-1)}>1$を作ってみるまで上手く行くかどうかは五分五分な気分でした. またコーナーケースもあって面倒だったですね. もっとモチベーションにしていた大小関係の違和感をもっと直接的に扱ってみましょう.

$(ii)$もう少し部分に注目する方法
大きい約数が沢山あるのがまずかったのでした. $\dfrac{n}b$以上の約数が$a$個以上あるんですよね. 大きいと扱いにくいので小さくしたくて, これは約数$d$を$\dfrac nd$に置き換えれば達成出来ます. これによって$b$以下の約数が$a$個以上ある事になります... これだとダメそうだけど$a,b$入れ替えても議論は成立するので入れ替えてみると$a$以下の約数が$b$個以上ある事になります...これはヤバい. このまま$a=b$を言い, $n$が$1$から$a$まで約数持つから矛盾でも良いのですが, 以下が未満に変えれればそれで勝ちです. ($n>1$なので)各行$b(>1)$個の元があるので総和は$n$より大きくなります. だから鳩ノ巣原理より$\dfrac{n}a$より大きい約数が$b$個以上あって, これは$a$未満の約数が$b$個以上ある事になって矛盾. めでたしめでたし.

本当は$(i)$を書きたかったけど$(ii)$の方が明らかに筋が良いんですよね()

次, ISL2016N2 .

ISL2016N2

正整数$n$の正の約数のうち$3$で割って$1$余るものの個数を$\tau_1(n)$で表す.
$\dfrac{\tau(10n)}{\tau_1(10n)}$ が取りうる正整数を全て求めよ.

これはとりあえず$\tau_1(n)$を考察してみたくなります.
$\displaystyle n=3^{v_3(n)}\prod_{p\equiv1\pmod3}p^{v_p(n)}\prod_{p\equiv2\pmod3}p^{v_p(n)}$と素因数分解します. $p=3$のとき$3$を素因数に持つ約数を$3$で割った余りは$1$にはならないので$3$の因数は$\tau_1$に関与しません. 次に$p\equiv1\pmod3$のとき$d\equiv p^kd\pmod3$だから$3$で割って$1$余るかどうかは$d$に依存し, $1$余るならそれに対して$k+1$通りの$p$の指数の取り方が出来ます. なので結局因数$v_p(n)+1$を持つことになります. 最後に$\displaystyle \tau_1\left(\prod_{p\equiv2\pmod3}p^{v_p(n)}\right)$を考えます. さてこれをどう求めるか. 色々やり方はあると思いますが自分はOMCにありそうな母関数っぽいあれをやりました. 次の問題はみんな$(1+1)^n,(1-1)^n$の二項定理を使うと思います. それの類似です.

よくある二項係数の問題

$\displaystyle\sum_{k=0}^{2n}{}_{2n}\mathrm{C}_{2k}$を簡単にせよ.

今回は$\tau(n)$と$3$で割って$1$余る約数の個数から$3$で割って$2$余る約数の個数を引く$\tau_0(n)$を考えます. すると嬉しいことに$\displaystyle \tau_0\left(\prod_{p\equiv2\pmod3}p^{v_p(n)}\right)=\prod_{p\equiv2\pmod3}\sum_{k=0}^{v_p(n)}(-1)^k$この値は$v_p(n)$が全て偶数なら$1$でそうでないなら$0$です. だから$n$の全ての素因数を$3$で割った余りが$2$のとき$\tau_1(n)=\left\lfloor\dfrac{\tau(n)}2\right\rfloor$が分かりました.
結局$10n=3^cab$(ただし$a$の素因数を$3$で割った余りは$1$, $b$の素因数を$3$で割った余りは$2$)とすると$\dfrac{\tau(10n)}{\tau_1(10n)}=\dfrac{(c+1)\tau(b)}{\left\lfloor\dfrac{\tau(b)}2\right\rfloor}$となります. $b$が平方数でないならこの値は$2(c+1)$となるため全ての偶数は条件を満たします. $b$が平方数の時を考えれば良いのですこのときは$\tau(b),\left\lfloor\dfrac{\tau(b)}2\right\rfloor$は互いに素なので$c=k\left\lfloor\dfrac{\tau(b)}2\right\rfloor$となり, もとの分数は$k\tau(b)$となります. これは$10|b$だから奇数の合成数と$2\times$奇数の合成数全体を動くから, 求める答えは$2$と全ての合成数となる.
$\tau_1$が分かってしまえば場合分けとかは分かりやすいと思います.

後は練習問題を置いておきます. 問題提供とかあるとうれしいかも?
ISL2004N2 ISL2009N5 ABC212G OMC042D ELMOSLP2010N1

ゼータ関数のオイラー積

自分がこれを意識したのはゼータ関数のオイラー積について勉強したときなので少しだけ書きます.
ゼータ関数は$\zeta(s)=\displaystyle\sum_{n=1}^\infty\frac{1}{n^s}$と表される関数ですが, これのオイラー積表示はまさにこの式変形を使っています. $\displaystyle\zeta(s)=\lim_{n\to\infty}\sigma_{-s}(n!)=\prod_p\frac1{1-p^{-s}}$という感じですね. (厳密には収束性や微分可能性についての議論がいりますが割愛)ということはゼータ関数の和の分子に乗法的関数を乗っけても上手くオイラー積が作れそう... 例えばルジャンドル記号を用いた場合はディリクレの$L$関数とか名前が付いてたり, より一般にも$L$関数という関数のクラスが沢山あり, 代数体の様々な性質を調べるために用いられているそうです.
この辺の記事あたりを読んでみると面白いかも知れないです.