コンピュータで負の数を表そうとすると2の補数表現という方法を良く使います。
たとえば、8bit型の変数に-60という値を入れたいとき、
196という値を代わりに入れて計算します。
この196という値は256-60という計算で出します。
256は8bitでぎりぎり表せない数値です。
数学では、合同式というもので表現します。
先ほどの、-60と196を数式にすると以下になります。
-60 ≡ 196 (mod 256)
256で割った余りの世界では、-60と196は同じという意味です。
=ではなく合同を意味する≡を使います。
-60と196が同じなのか、足し算で検証します。
90-60 ≡ 90+196 ≡ 286 ≡ 256+30 ≡ 30 (mod 256)
合同式の面白い所は、分数を整数で表わすことが出来る点です。
2/3 ≡ 258/3 ≡ 86 (mod 256)
∵ 2 ≡ 258 (mod 256)
ということで、2/3と86が同じという意味になりました。
ちょっと計算してみましょう
60×(2/3) ≡ 60×86 ≡ 5160 ≡ 256×20+40 ≡ 40 (mod 256)
2/3の代わりに86を使っても同じ40という答えになりました。
これで256の余りの世界では、2/3と86が同じという事がわかると思います。
1/3を整数に直すときは、1の代わりに257を入れても割りきれません。
そこで、次の513を入れて171という整数にできます。
1/3 ≡ 513/3 ≡ 171 (mod 256)
しかし、1/2は整数にすることができません。
1/2 ≡ 257/2 ≡ 513/2 (mod 256)
このように、必ずしもすべての分数が整数に変換できるわけではありません。
1/2のパターンを見れば、整数に出来る分数と出来ない分数の条件が
おぼろげながらわかる気がしますね。
さらに、四則演算だけでなく、階乗についても面白い性質があります。
以下の表を見てください。
右は3乗、左は7乗して11で割った余りです。
それぞれ、お互いの逆関数になっていることに気づくでしょうか。
例えば、n=3のとき、3乗すると5です。
そして、5を7乗すると3になっています。
11の余りの世界では、立法根(3乗根)と7乗した値が同じなのです。
こうやって、n乗根をm乗に変換できるのも合同式の性質です。
この3と7の値を求めるには、こんな式があります。
a×b ≡ 1 (mod (p - 1)) 但し、pは素数
今回、a=3, b=7,p=11です。
当てはめてみましょう
3×7 ≡ 21 ≡ 1 (mod 10)
この式に当てはまれば、別の数でも成り立ちます。
これも分数と同様、すべてのn乗根が変換できるわけではありません。
このように、合同式にはいろいろ面白い世界があります。
その面白い世界を近いうちに紹介します。