📂정수론

정수론에서의 합동

정의 ¹

$a \equiv b \pmod{m}$ $\iff$ 정수 $a$, $b$, $m$ 에 대해 $a = b + mk$ 를 만족하는 정수 $k$ 가 존재한다.

정리

$a_{1} \equiv b_{1} \pmod{m}$ 과 $a_{2} \equiv b_{2} \pmod{m}$ 이 성립한다고 하자.

• [1] 덧셈: $a_{1} + a_{2} \equiv b_{1} + b_{2} \pmod{m}$
• [2] 뺄셈: $a_{1} - a_{2} \equiv b_{1} - b_{2} \pmod{m}$
• [3] 곱셈: $a_{1} a_{2} \equiv b_{1} b_{2} \pmod{m}$
• [4] 나눗셈: $\gcd ( c , m ) = 1$ 이면 $$ac \equiv bc \pmod{m} \implies a \equiv b \pmod{m}$$
• [5] 모듈로끼리의 곱: $\gcd ( m_{1} , m_{2} ) = 1$ 이면 $$\begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} }$$
• [6] 모듈로의 거듭제곱: $a \equiv b \pmod{m^n}$ 면 $a \equiv b \pmod{m}$
• [7] 모듈로를 포함한 약분: $ax \equiv ay \pmod{am} \iff x \equiv y \pmod{m}$

설명

수식 $a \equiv b \pmod{m}$ 을 합동식이라 부르고, 법^modulo $m$ 에서 $a$ 가 $b$ 에 합동^congruent이라 한다. 다만 법은 수식에서부터 $\pmod{}$ 가 그대로 쓰인만큼 그냥 모듈로 $m$ 이라고 발음하는 편이다.

정리 [4]에서 $\gcd(c,m) = 1$ 이라는 조건이 없으면 양변에서 $c$ 를 나눌 수 없다. 예를 들어 $8 \equiv 20 \pmod{12}$ 은 성립하지만, 양변에서 $4$ 를 나눈 $2 \equiv 5 \pmod{12}$ 는 성립하지 않는다.

보통 간단한 정수론의 문제를 다룰 땐 $m$ 을 소수를 두지만 복잡해지다보면 $m$ 을 합성수로 두게 된다. 따라서 합동방정식 전체를 크게 보고 그 성질도 알아둘 필요가 있다.

증명

[5]

$a \equiv b \pmod{m_{1}}$ 이므로 다음을 만족하는 정수 $n_{1}$ 이 존재한다. $$a = b + n_{1} m_{1}$$ $a \equiv b \pmod{m_{2}}$ 이므로 다음을 만족하는 정수 $n_{2}$ 이 존재한다. $$a = b + n_{2} m_{2}$$ $m_{1}$ 과 $m_{2}$ 는 서로소이므로 두 식이 동시에 성립하려면 $n_{1}$ 는 $m_{2}$ 의 배수고, $n_{2}$ 는 $m_{1}$ 배수여야한다. 따라서 다음을 만족하는 정수 $n_{3}$ 가 존재한다. $$a = b + n_{3} m_{1} m_{2}$$ 그러면 합동식의 정의에 따라 $$a \equiv b \pmod{ m_{1} m_{2} }$$

■

[6]

$a \equiv b \pmod{m^n}$ 이면 $$a = b + m^n k$$ 을 만족하는 정수 $k$ 가 존재한다. 여기서 $m^{n-1}$ 을 떼어내면 $$a = b + m^{n} k \cdot n = b + m \cdot (m^{n-1} k)$$ 을 만족하는 정수 $m^{n-1} k$ 가 존재하므로 $$a \equiv b \pmod{m}$$

■

[7]

어떤 정수 $k$ 에 대해서 $$\begin{align*} ax \equiv ay \pmod{am} & \iff ax = ay + amk \\ & \iff x = y + mk \\ & \iff x \equiv y \pmod{m} \end{align*}$$

■