1.6.1. 整数の合同

合同算術とは

整数の計算において、整数そのものではなくその剰余をとったものを扱う方法のこと。

合同算術は、一定の周期をもつ様々な対象に適用できる。

例えば曜日は周期をもつ。日曜日から土曜日までのそれぞれに \(0, 1, \ldots 6\) の連続する数字を割り振ると、\(n\) 日後や \(n\) 日前の曜日を次のように計算できる。

• 金曜日の3日後は月曜日である。

  • \(5 + 3 \equiv 1 \pmod 7\)

• 火曜日の10日前は土曜日である。

  • \(2 - 10 \equiv 6 \pmod 7\)

合同の定義

ある整数 \(k\) を用いて \(a - b = kn\) と表せるとき

\[a \equiv b \pmod n\]

と表現し、「\(a, b\) は法 \(n\) に関して合同である」という。

基本演算

\(a \equiv b \pmod n\) に対して加算や乗算を行うことができる。

• 加算 \(a + x \equiv b + x\)

• 減算 \(a - x \equiv b - x\)

• 乗算 \(ax \equiv bx\)

• 冪乗 \(a^{x} \equiv b^{x} \quad (x \geq 0)\)

除数 \(x\) による除算は、その逆元 \(x^{-1}\) と乗算を用いて定義される。

• 除算 \(ax^{-1} \equiv bx^{-1}\)

ただし、逆元が存在しないときは除算が定義されない。