# 합동 (Congruence)

합동(congruence)은 두 가지 뜻으로 쓰입니다. 정수론에서는 두 정수 a, b를 n으로 나눈 나머지가 같을 때, 즉 n이 a − b를 나눌 때 'a와 b는 n을 법으로 합동'이라 하고 a ≡ b (mod n)으로 씁니다. 추상대수에서는 이를 일반화해, 군·환 같은 대수 구조 위의 동치 관계 가운데 연산과 양립하는 것(동등한 원소끼리 연산하면 결과도 동등한 것)을 합동 관계라고 합니다.

## 자세히 알아보기

정수의 합동은 동치 관계(반사·대칭·추이)이면서 연산과 양립합니다. a ≡ b, c ≡ d (mod n)이면 a + c ≡ b + d, ac ≡ bd (mod n)입니다. 그래서 큰 수의 계산 중간에 언제든 나머지로 줄여도 결과가 맞습니다. 합동류(나머지가 같은 수들의 묶음)를 원소로 보면 Z/nZ가 됩니다.

일차 합동식 ax ≡ b (mod n)은 gcd(a, n)이 b를 나눌 때만 해가 있습니다. 중국인의 나머지 정리는 서로소인 법들에 대한 연립 합동식 x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)가 n₁n₂를 법으로 유일한 해를 가진다는 정리로, 큰 법의 계산을 작은 법들로 쪼개는 데 쓰입니다.

추상대수에서 합동 관계는 몫 구조를 만드는 도구입니다. 군의 합동 관계는 정규 부분군과, 환의 합동 관계는 아이디얼과 일대일로 대응합니다.

## 블록체인·암호화폐에서는

- 서명 검증: ECDSA 서명값은 s·k ≡ z + r·d (mod n)이라는 합동식으로 만들어지고(검증자는 k, d 없이 이 관계를 곡선 점 연산으로 확인합니다), 슈노어 서명(BIP-340)의 s = k + e·d mod n도 합동식입니다.
- RSA: 암호화와 복호화가 서로를 되돌리는 이유는 ed ≡ 1 (mod φ(n))이라는 합동 관계 덕분입니다. RSA 구현은 중국인의 나머지 정리로 복호화를 약 4배 빠르게 합니다.
- 스마트 컨트랙트: uint256 연산 결과는 실제 값과 2^256을 법으로 합동이므로, 오버플로가 일어나도 '합동으로는 맞는' 값이 남아 버그를 알아채기 어렵습니다.

## 쉽게 말하면

합동은 '시계 위에서 같은 자리를 가리킨다'는 관계입니다. 14시와 2시는 12를 법으로 합동입니다.

## 예시

38 ≡ 14 (mod 12)입니다. 38 − 14 = 24가 12로 나누어떨어지기 때문입니다. x ≡ 2 (mod 3), x ≡ 3 (mod 5)의 해는 x ≡ 8 (mod 15)입니다.

또 3x ≡ 4 (mod 7)은 gcd(3, 7) = 1이므로 해가 하나 있으며, 3의 역원 5를 곱하면 x ≡ 20 ≡ 6 (mod 7)입니다(3 × 6 = 18 ≡ 4).

---
출처: https://achivx.kr/glossary/congruence-%EC%9D%BC%EC%B9%98/ · ACHIVX 용어 사전 · 수정일 2026-10-20