モジュロ計算におけるバイナリ法の根源要素 自分雑記メモ

とある数aがあったとする。
その世界はPを法とする世界である。

その中で、a≡b（mod P）が成り立つ時、Pを法とする世界の中では、
元の数aの二乗が、modした後のPを法とする世界でのbの二乗と合同である。

これがバイナリ法の根源の考え方で、これを展開・応用するとバイナリ法になる。

これを式で書く。

a ≡ b (mod P) ならば a^2 ≡ b^2 (mod P)

a ≡ b (mod P) の場合、a-b は P の倍数であり、a - b = kP と表すことができる（ここで k は整数）。したがって、a^2 - b^2 = (a - b)(a + b) は P の倍数となり、a^2 ≡ b^2 (mod P) が成り立つ。

もう少し丁寧に書けば、a ≡ b (mod P)と言うのは、
aと言うものは、a`+k1P、
bと言うものは、b`+k2P
となっていたと仮定する時、Pで割った時のそれぞれの余りa`とb`が同じだよ〜んと言っている（合同）。

上記とは別に２乗した時のことを考える。
なんで、突如としてa^2 - b^2が出てきたのかというと、
２つの数の差がPで割り切れる時、a^2とb^2は同じ剰余を結果的に持っている、と言うことだからだ。

で、a^2-b^2 を分解すると (a - b)(a + b) になって、a≡b(mod P) の場合、a-bはPの倍数であり、a-b = kP と表すことができる（ここで k は整数）。

つまりa^2-b^2は、いくつの整数がかかっているかは分からんが、Pの倍数となっている＝Pで割り切れるなので、Pを法とする世界での割り算において同じ余りを持っている＝合同であるになるのである。