解答例 1

まず, $a=1$ の場合を証明する. すなわち, 合同式 $$ x^{2} + by^{2} \equiv r\pmod{p} $$ が $x$, $y$ について整数解をもつことを証明する.

$p=2$ の場合. $\gcd(b, 2)=1$ より, $b\equiv 1\pmod{2}$ となる. $r\equiv 0\pmod{2}$ のとき, $(x, y)=(0, 0)$ が整数解の1つである. $r\equiv 1\pmod{2}$ のとき, $(x, y)=(1, 0)$ が整数解の1つである.

$p$ が奇素数の場合. $y^{2}$ ($0\leq y\leq (p-1)/2$) は, どの2つも $p$ を法として合同ではない. $\gcd(b, p)=1$ より, $r-by^{2}$ ($0\leq y\leq (p-1)/2$) も, どの2つも $p$ を法として合同ではない. ところが, これらの個数が $(p+1)/2$ 個であるにもかかわらず, $0$ から $p-1$ までの整数のうち, $p$ の平方非剰余であるものは $(p-1)/2$ 個しかない. ゆえに, ある整数 $y_{0}$ が存在して, $r-by_{0}^{2}$ は $p$ の平方剰余になる. すなわち, ある整数 $x_{0}$ が存在して, $r-by_{0}^{2} \equiv x_{0}^{2}\pmod{p}$. このとき, $(x, y)=(x_{0}, y_{0})$ は与えられた合同方程式の整数解である.

次に, 一般の場合について, $\gcd(a, p)=1$ より, 1次合同式 $ax\equiv b\pmod{p}$ は $x$ についての整数解 $b'$ をもつ. $\gcd(b, p)=1$ より, $\gcd(b', p)=1$ である. 同様に, 1次合同式 $ax\equiv r\pmod{p}$ は $x$ についての整数解 $r'$ をもつ. 与えられた合同方程式の両辺を $a$ で割ると, $$ x^{2} + b'y^{2} \equiv r'\pmod{p} $$ となり, $a=1$ の場合に帰着する.

最終更新日：2011年11月02日