奇素数pを法として平方剰余でない素数とガウス記号

まえがき

この記事は 髙見瑞乃 さんの 競技科学people 1st Advent Calendar 2025 の7日目の記事となります．(この日は私の誕生日！)

概要

この記事では，以下の等式を証明します．($n$は自然数)
$$\sum_{0< s< p, sはpを法として平方剰余} \left\lfloor \frac{n + p - s}{p} \right\rfloor = \frac12n - \frac12 \left\lfloor \frac{n}{p} \right\rfloor + \sum_{kはpを法として平方剰余である素数およびpで割り切れない} (-1)^{\Omega(k)} 2^{\omega(k) - 1}\left( \left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n}{pk} \right\rfloor \right)$$
(ここで$\omega(n)$は$n$の素因数の個数(重複は含めない)，$\Omega(n)$は$n$の素因数の個数(重複分もカウントする)です)
この等式は OMC224F の一般化になっています．
前提知識は、メビウスの反転公式とガウス記号です．

方針

$M(-;(条件)) \colon \mathbb{N} \rightarrow \{ 0,1 \}$ を，$n$が$条件$を満たすときのみ$M(n;(条件)) = 1$，そうでないとき$M(n;(条件)) = 0$である関数とします．このとき以下のような式を考えます．
$$M(n;xは\bmod p で平方剰余) = \sum_{k = 1}^{\infty} a_k M(n;xはkの倍数)$$
これが成り立つような$a_k$を求めると，なんと$k$が「$p$を法として平方剰余でない素数と$p$との積」である場合を除いて$a_k = 0$となります．ここで$n = 1, \cdots ,m$の場合を足し合わせると，
$$\sum_{0< s< p, sはpを法として平方剰余} \left\lfloor \frac{m + p - s}{p} \right\rfloor = \sum_{k = 1}^{\infty} a_k \left\lfloor \frac{m}{k} \right\rfloor$$
となります．これを整理すると求める等式が得られます．

$a_k$を求める

$$M(n;xは\bmod p で平方剰余) = \sum_{k = 1}^{\infty} a_k M(n;xはkの倍数)$$
の右辺は$\sum_{k | n} a_k$と書ける．よってメビウスの反転公式より
$$a_n = \sum_{k | n} \mu(k) M\left(\frac n k;xは\bmod p で平方剰余\right)$$
$$= \sum_{k | n,kは平方因子を持たない} \mu(k) M\left(\frac n k;xは\bmod p で平方剰余\right)$$
長くなるので，以降は$Sq(n) := M(n;xは\bmod p で平方剰余)$とする．

$n$が$\bmod p$で平方剰余である素数$q$で割り切れるとき

$$a_n = \sum_{k | n,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= \sum_{k | n,q | k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right) + \sum_{k | n,q \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= \sum_{k | n,q \not\mid k,kは平方因子を持たない} \mu(qk) Sq\left(\frac n {qk}\right) + \sum_{k | n,q \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= -\sum_{k | n,q \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right) + \sum_{k | n,q \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= 0$$

$n$が$p$で割り切れるとき

$n$が$p^2$で割り切れるとき
$$a_n = \sum_{k | n,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right) = \sum_{k | n,kは平方因子を持たない} \mu(k) \times 0 = 0$$
$n$が$p^2$では割り切れないが$p$で割り切れるとき
$$a_n = \sum_{k | n,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= \sum_{k | n,p | k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right) + \sum_{k | n,p \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= \sum_{k | n,p \not\mid k,kは平方因子を持たない} \mu(pk) Sq\left(\frac n {pk}\right) + \sum_{k | n,p \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
$$= - \sum_{k | n,p \not\mid k,kは平方因子を持たない} \mu(k) Sq\left(\frac n {pk}\right)$$
$$= -a_{n/p}$$

以上の考察から，$n$が$\bmod p$で平方剰余であるような素因子を持たず，$p$で割り切れないときを調べればよい．

$n$が$\bmod p$で平方剰余であるような素因子を持たず，$p$で割り切れないとき

$a_1 = 1$である．以降$n>1$とする．
$\omega(n):=(nの素因数の個数(重複は含めない))$，$\Omega(n) := (nの素因数の個数(重複分もカウントする))$とする．
$$a_n = \sum_{k | n,kは平方因子を持たない} \mu(k) Sq\left(\frac n k\right)$$
このとき，$\mu(k) = (-1)^{\Omega(k)}$，$Sq(n/k) = ((-1)^{\Omega(n/k)} + 1)/2$なので
$$= \sum_{k | n,kは平方因子を持たない} (-1)^{\Omega(k)} \frac{((-1)^{\Omega(n/k)} + 1)}{2}$$
$$=\frac12 \sum_{k | n,kは平方因子を持たない} (-1)^{\Omega(n)} + \frac12 \sum_{k | n,kは平方因子を持たない} (-1)^{\Omega(k)}$$
$$=(-1)^{\Omega(n)}2^{\omega(n) - 1} + 0 =(-1)^{\Omega(n)}2^{\omega(n) - 1}$$

和分

$$Sq(n) = \sum_{k = 1}^{\infty} a_k M(n;xはkの倍数)$$
を$n = 1,\cdots,m$の場合を考えて足し合わせると，$$Sq(1) + \cdots + Sq(m) = (m以下の自然数でpを法として平方剰余であるものの個数) $$
$$= \sum_{0< s< p, sはpを法として平方剰余} \left\lfloor \frac{m + p - s}{p} \right\rfloor$$
$$M(1;xはkの倍数) + \cdots + M(m;xはkの倍数) = \left\lfloor \frac{m}{k} \right\rfloor$$
より
$$\sum_{0< s< p, sはpを法として平方剰余} \left\lfloor \frac{m + p - s}{p} \right\rfloor = \sum_{k = 1}^{\infty} a_k \left\lfloor \frac{m}{k} \right\rfloor$$
$$= \frac12m - \frac12 \left\lfloor \frac{m}{p} \right\rfloor + \sum_{kはpを法として平方剰余である素数およびpで割り切れない} (-1)^{\Omega(k)} 2^{\omega(k) - 1}\left( \left\lfloor \frac{m}{k} \right\rfloor - \left\lfloor \frac{m}{pk} \right\rfloor \right)$$
よって示された．

余談

pを法として平方非剰余である素数が有限個であると仮定して，両辺を$m$で割って$m\rightarrow \infty$の極限を取ると矛盾するので，pを法として平方非剰余である素数が無限個あることが分かります．もちろんそれを示すだけならもっと簡単にできるのですが．

一般の場合の話

任意の $f:\mathbb{N} \rightarrow \mathbb{C}$ について，
$$f(n) = \sum_{k = 1}^{\infty} a_k \left\lfloor \frac{n}{k} \right\rfloor $$
なる $a_k$ が一意に存在し，同様の手順で求めることができます(が，$\sum$を含まない式で表せるかどうかはもちろん$f$によります)．$f(n) = \left\lfloor \alpha n + \beta \right\rfloor$のときの$a_k$の挙動に興味があるんですが，今回のような場合でない限り綺麗な式にはならなさそうです．「ガウス記号に関する非自明な等式を全部これ(=等式の両辺を上の式の右辺の形にして機械的に計算する)で解決したいな〜」と思っていたので、少し残念...