二次多項式と平方剰余
はじめに
$p$を奇素数とする.整数に$a$に対してLegendre記号$\left(\dfrac{a}{p}\right)$を次のように定義する.
\begin{equation*}
\left(\dfrac{a}{p}\right)= \left\{
\begin{array}{cl}
0 & p\mid a,\\
1 & p \nmid a \ \mathrm{and}\ \exists x,p\mid x^2-a,\\
-1 & p \nmid a\ \mathrm{and} \ \forall x, p\nmid x^2-a.
\end{array}
\right.
\end{equation*}
また,$\left(\dfrac{a}{p}\right)=1$なら$\mathrm{mod}\ p$で$a$は平方剰余であるといい,$\left(\dfrac{a}{p}\right)=-1$なら$\mathrm{mod}\ p$で$a$は非平方剰余であるといいます.
二次多項式によって生成される数の平方剰余の個数はいい感じに求めることができることが知られています.
$p\nmid a$.
\begin{equation*}
\sum_{x = 0} ^ {p - 1} \left(\frac{ax^2+bx+c}{p}\right) = \left\{
\begin{array}{cl}
-\left(\dfrac{a }{p }\right) & p \nmid b^2 - 4ac,\\
(p - 1)\left(\dfrac{a }{p }\right) & p \mid b^2 -4ac.
\end{array}
\right.
\end{equation*}
(修正)二次多項式なので$p\nmid a$の時だけに限定しました.(一次や定数の時は明らかなので最初から省く.)2023/10/22
オイラーの基準:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}2} \pmod p$$
を使って頑張って計算する.
$\left(\dfrac{a}{p}\right) \ne 0$なら平方完成をして,$x^2 + c'$に帰着させることができて,あとはやるだけ.
使える問題
$a, b, c$を整数,$p$を$5$以上の奇素数とする.また,$f(x) = ax^2 + bx + c$とする.今,連続する$\frac{p + 5}{2}$個の整数$x = n, \cdots, n + \frac{p + 3}{2}$に対し$f(x)$はある整数の二乗である.このとき,$b^2-4ac$が$p$の倍数となることを示せ.
出典は こちら .
解答
$p \nmid a$であるとき,$p\nmid b^2 - 4ac$と仮定すると,定理より,任意の整数$n_0$に対して,$f(n_0), \cdots ,f(n_0 + p - 1)$には$p$に関して非平方剰余でないものは高々$\frac{p + 3}{2}$個なので簡単に矛盾が導ける.Given a prime number $p\ge 5$.Find the number of distinct remainders modulus $p$ of the product of three consecutive positive integers.
出典は こちら .
解答
以下に出てくる合同式はすべて$p$を法とする.$\#\left\{(x^3 - x を p で割った余り):x\in \mathbb{Z}\right\}$を求めればいい.$x\in \mathbb{Z}\cap [0, p)$に対して,$x^3 - x\equiv y^3 - y$をみたす$y$を考える.明らかに, $y\equiv x$は解の一つなのでそうでないときを考える.$$x^3 - x \equiv y^3 - y \Longrightarrow -3x^2 + 4\equiv (x + 2y)^2$$
だから,これの解の個数を考えることで答えは次のように計算することができる.
$$ \#\left\{(x^3 - x を p で割った余り):x\in \mathbb{Z}\right\} = p-\dfrac13\sum_{x = 0} ^ {p - 1}\left[\left(\dfrac{-3x^2 + 4}{p}\right) + 1\right] = \dfrac{2p + \left(\dfrac{-3}p\right)}{3} = \left\lfloor\dfrac{2p + 1}3\right\rfloor.$$
コメント
同様の議論によって,$a$を$p$の倍数でない整数とすると,以下も示すことができる.$$\#\left\{(x^3 + ax を p で割った余り):x\in \mathbb{Z}\right\} = \dfrac{2p + \left(\dfrac{-3}p\right)}{3} = \left\lfloor\dfrac{2p + 1}3\right\rfloor$$
おわりに
面白い事実ですが,使うことができる場面は少なそうです.
ありがとうございました.
この記事を高評価した人
この記事に送られたバッジ
投稿者
