前回 mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding
p mod 8 = 5の時の平方剰余を計算しましたが、今回は、
p mod 4 = 3の時の平方剰余を計算してみましょう。
この場合も簡単に計算が可能です。
前回と同じように
の解は存在することを仮定します。つまり、
です。
と書けます。
解は、
となります。なぜなら、
オイラーの基準を使い、右辺は、
となり、式を満たします。
解をpで書くと
となります。