「合同式」は数論（整数の数学）で非常に重要な概念です。以下で、基本から丁寧に解説していきます。

ある整数 $A$ と $B$、自然数 $N$ に対して、

$$ A \equiv B \pmod{N} $$

と書くとき、これは「A を N で割った余りと、B を N で割った余りが等しい」という意味です。

$$ A \equiv B \pmod{N} \quad \Longleftrightarrow \quad A % N = B % N $$

または、

$$ A - B は N の倍数である（A - B ≡ 0 mod N） $$

• $A \equiv B \pmod{N}$ は「AとBは、Nで割ったときに同じ“余り”になる」ということ。
• 普通の等号（=）と違って、“余りの世界”での等しさを表す。

$$ 19 \equiv 7 \pmod{6} $$

• なぜなら $ 19 \div 6 = 3$ 余り 1 $ 7 \div 6 = 1$ 余り 1

➡︎ 同じ余りだから、合同。

$$ 35 \equiv 3 \pmod{8} $$

• $35 % 8 = 3$
• $3 % 8 = 3$

合同式は以下のような計算のルールが成り立ちます。これはとても便利です。

$$ A \equiv B \pmod{N}, \quad C \equiv D \pmod{N} \Rightarrow A + C \equiv B + D \pmod{N} $$

$$ A \equiv B \pmod{N}, \quad C \equiv D \pmod{N} \Rightarrow A - C \equiv B - D \pmod{N} $$

$$ A \equiv B \pmod{N} \Rightarrow A \cdot k \equiv B \cdot k \pmod{N}（任意の整数 k） $$

$$ A \equiv B \pmod{N} \Rightarrow A^k \equiv B^k \pmod{N} $$

例えば、大きな数の計算や、周期的な性質を持つものの解析（暗号理論、RSA暗号など）では、合同式を使うと処理が劇的に簡単になります。

「1〜100000のうち、A ≡ x (mod N) を満たす x を出力せよ」

→ このときは、x % N == A % N となるすべての x を出力すればよいです。

もっと発展的な話（逆元, 中国剰余定理, オイラーの定理）などもありますが、まずはこの基本をしっかり理解しておくと安心です。