1.3 합동식 (Congruences)
가우스(Gauss)에 의해 도입된 합동식은 정수의 나눗셈 문제를 대수적인 방정식 문제로 변환해 줍니다. 이는 현대 암호학 및 컴퓨터 과학의 산술 연산에서 핵심적인 역할을 합니다.
1. 합동의 정의와 모듈러 연산
양의 정수 $m$(법, Modulus)에 대하여, 두 정수 $a, b$의 차 $a-b$가 $m$으로 나누어떨어질 때 "$a$와 $b$는 법 $m$에 대해 합동이다"라고 하며 다음과 같이 씁니다.
$$a \equiv b \pmod{m} \iff m \mid (a-b)$$
즉, $a$와 $b$를 $m$으로 나누었을 때의 나머지가 같다는 의미와 일맥상통합니다.
2. 합동식의 기본 성질
합동식은 등호($=$)와 유사하게 덧셈, 뺄셈, 곱셈에 대해 자유롭지만, 나눗셈에서는 주의가 필요합니다.
- $a \equiv b \pmod m$ 이고 $c \equiv d \pmod m$ 이면:
- $a \pm c \equiv b \pm d \pmod m$
- $ac \equiv bd \pmod m$
- $a^k \equiv b^k \pmod m$ (단, $k$는 양의 정수)
- 나눗셈(약분): $ac \equiv bc \pmod m$ 일 때, $d = \gcd(c, m)$ 이라면 $a \equiv b \pmod{m/d}$ 가 성립합니다.
3. 선형 합동방정식 (Linear Congruences)
$ax \equiv b \pmod m$ 꼴의 방정식에서 미지수 $x$를 찾는 문제입니다.
Existence of Solution
방정식 $ax \equiv b \pmod m$ 이 해를 가질 필요충분조건은 다음과 같습니다.
$$\gcd(a, m) \mid b$$
만약 $d = \gcd(a, m)$ 이 $b$를 나눈다면, 법 $m$에 대하여 서로 다른 해는 정확히 $d$개 존재합니다.
4. 잉여계 (Residue Systems)
법 $m$에 대한 모든 정수는 $m$개의 집합으로 분류될 수 있습니다.
- 완전잉여계 (Complete Residue System): $\{0, 1, 2, \dots, m-1\}$과 같이 법 $m$에 대해 서로 합동이 아닌 모든 나머지의 집합.
- 기약잉여계 (Reduced Residue System): 완전잉여계 중 법 $m$과 서로소인 원소들만의 집합. 이 집합의 원소 개수는 오일러 파이 함수 $\phi(m)$으로 정의됩니다.