二次多項式と平方剰余

207

はじめに

$p$ を奇素数とする.整数に $a$ に対してLegendre記号 $(\frac{a}{p})$ を次のように定義する.
$(\frac{a}{p}) = {\begin{array}{cl} 0 & p ∣ a, \\ 1 & p ∤ a and \exists x, p ∣ x^{2} - a, \\ - 1 & p ∤ a and \forall x, p ∤ x^{2} - a . \end{array}$
また, $(\frac{a}{p}) = 1$ なら $\mod p$ で $a$ は平方剰余であるといい, $(\frac{a}{p}) = - 1$ なら $\mod p$ で $a$ は非平方剰余であるといいます.

二次多項式によって生成される数の平方剰余の個数はいい感じに求めることができることが知られています.

$p ∤ a$ .
$\sum_{x = 0}^{p - 1} (\frac{a x^{2} + b x + c}{p}) = {\begin{array}{cl} - (\frac{a}{p}) & p ∤ b^{2} - 4 a c, \\ (p - 1) (\frac{a}{p}) & p ∣ b^{2} - 4 a c . \end{array}$

(修正)二次多項式なので $p ∤ a$ の時だけに限定しました.(一次や定数の時は明らかなので最初から省く.)2023/10/22

証明メモ1

オイラーの基準:
$(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (\mod p)$
を使って頑張って計算する.

証明メモ2

$(\frac{a}{p}) \neq 0$ なら平方完成をして, $x^{2} + c^{'}$ に帰着させることができて,あとはやるだけ.

使える問題

1991 ISL 14 (改)

$a, b, c$ を整数, $p$ を $5$ 以上の奇素数とする.また, $f (x) = a x^{2} + b x + c$ とする.今,連続する $\frac{p + 5}{2}$ 個の整数 $x = n, \dots, n + \frac{p + 3}{2}$ に対し $f (x)$ はある整数の二乗である.このとき, $b^{2} - 4 a c$ が $p$ の倍数となることを示せ.

出典はこちら .

解答

p ∤ a

であるとき,

p ∤ b^{2} - 4 a c

と仮定すると,定理より,任意の整数

n_{0}

に対して,

f (n_{0}), \dots, f (n_{0} + p - 1)

には

p

に関して非平方剰余でないものは高々

\frac{p + 3}{2}

個なので簡単に矛盾が導ける.

CGMO 2022 Day1 P4

Given a prime number $p \geq 5$ .Find the number of distinct remainders modulus $p$ of the product of three consecutive positive integers.

出典はこちら .

解答

以下に出てくる合同式はすべて

p

を法とする.

# {(x^{3} - x を p で 割 っ た 余 り) : x \in Z}

を求めればいい.

x \in Z \cap [0, p)

に対して,

x^{3} - x \equiv y^{3} - y

をみたす

y

を考える.明らかに,

y \equiv x

は解の一つなのでそうでないときを考える.

x^{3} - x \equiv y^{3} - y ⟹ - 3 x^{2} + 4 \equiv (x + 2 y)^{2}

だから,これの解の個数を考えることで答えは次のように計算することができる.

# {(x^{3} - x を p で 割 っ た 余 り) : x \in Z} = p - \frac{1}{3} \sum_{x = 0}^{p - 1} [(\frac{- 3 x^{2} + 4}{p}) + 1] = \frac{2 p + (\frac{- 3}{p})}{3} = ⌊ \frac{2 p + 1}{3} ⌋ .

同様の議論によって,

a

を

p

の倍数でない整数とすると,以下も示すことができる.

# {(x^{3} + a x を p で 割 っ た 余 り) : x \in Z} = \frac{2 p + (\frac{- 3}{p})}{3} = ⌊ \frac{2 p + 1}{3} ⌋

おわりに

面白い事実ですが,使うことができる場面は少なそうです.
ありがとうございました.

投稿日：2023年10月21日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

kk2

9221

2006年に生まれました

他の人のコメント

コメントはありません。

読み込み中

kk2

二次多項式と平方剰余

はじめに
使える問題
おわりに