合同式の方程式について合同式シリーズの前の記事では、合同式の方程式が解けるための条件を考えました。k)$を満たす整数$x$について考えてきたわけです。詳しくはこちらの記事を参照ください。前回、時計の文字盤と同じ考え方で、合同式の世界を理解した。次に、合同式の世界における四則演算について確認した。逆元という考え方が本質的に隠れています。逆元について深めていきましょう。逆元とは?ある数$a$に対して、$a・b=1$となる数$b$が存在するとき、$b$は$a$の逆元である、といいます。実数の世界では、例えば$2×\dfrac{1}{2}=1$なので、$2$の逆元は$\dfrac{1}{2}$です。実数の世界では、$0$以外の数には必ず逆元が存在します。(これは結構すごい事実です)ここで、合同式の世界で同じようなことを考えてみましょう。$a$に対して、$a・b=1$となる$b$を探します。順に処理していきましょう。5)$なので、1の逆元は1自身です。5)$なので、2の逆元は3になります。同様に、3の逆元は2です。5)$なので、4の逆元は4自身です。すべてに逆元が存在しました!他の例も考えてみましょう。4)$より、1の逆元は1自身です。これは先ほどと同じですね。4$の世界では逆元が存在しない数があります。これはよくよく考えてみると当たり前のことです。合同式の世界では、そもそも割り算は互いに素という条件がなければできませんでした。詳しくはこちらの記事をご覧ください。大学入試の整数問題でもたまに活躍する考え方。今回は合同式について学んでいきます。4$の世界では、4と互いに素である1と3しか逆元は持たないのです。互いに素な奴らがどの程度いるかということがとても重要な情報になります。そこで登場するのがオイラー関数です。