2.5 平方剰余の相互法則

前節では合同式の基礎を学びました。素数$p$に関し$p$を法とする合同式では四則演算が定義できること、$n,m$が互いに素のとき、

$$x \equiv a \pmod{n}$$

$$x \equiv b \pmod{m}$$

は解が$\mod{nm}$で一意的に定まることを学びました（中国剰余定理）。これは1次式に関しては$\mod n$と$\mod m$が独立しており別々の世界であることを意味しています。

本節では2次式

$$x^2 \equiv a \pmod{n}$$

$$x^2 \equiv b \pmod{m}$$

に解があるか否かを考えます。1次式では必ず解がありましたが、2次式にするとそうは行きません。2次式を考えることにより$\mod n$の世界と$\mod m$の世界との微妙で美しい世界が見えてきます。