1.3 합동식(Congruence) 실전 예제 10선
합동식의 대수적 성질과 선형 합동방정식 $ax \equiv b \pmod m$의 해법을 다루는 10가지 예제입니다. 잉여역수(Modular Inverse)의 개념을 익히는 데 집중해 보세요.
Ex 1. 합동과 거듭제곱
문제: $a \equiv b \pmod m$ 이면 모든 양의 정수 $k$에 대해 $a^k \equiv b^k \pmod m$ 임을 증명하시오.
$a \equiv b \pmod m$ 은 $m \mid (a-b)$ 임을 의미한다.
인수분해 공식에 의해 $a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + \dots + b^{k-1})$ 이다.
$(a-b)$가 $m$의 배수이므로, $(a^k - b^k)$ 역시 $m$의 배수가 된다.
따라서 $a^k \equiv b^k \pmod m$ 이 성립한다.
Ex 2. 나머지 계산의 묘미
문제: $41^{65}$ 를 7로 나눈 나머지를 구하시오.
$41 = 7 \times 5 + 6 \equiv 6 \equiv -1 \pmod 7$ 이다.
따라서 $41^{65} \equiv (-1)^{65} \pmod 7$ 이 성립한다.
$(-1)^{65} = -1 \equiv 6 \pmod 7$
$\therefore$ 나머지는 6이다.
Ex 3. 해의 존재 여부 판별
문제: $21x \equiv 14 \pmod{35}$ 의 해의 개수를 구하시오.
$a=21, b=14, m=35$ 일 때, $d = \gcd(21, 35) = 7$ 이다.
$d=7$ 이 $b=14$ 를 나누는지 확인한다: $7 \mid 14$ (참)
따라서 이 방정식은 법 35에 대하여 7개의 서로 다른 해를 갖는다.
Ex 4. 방정식의 일반해 구하기
문제: $3x \equiv 5 \pmod 7$ 의 해를 구하시오.
법 7은 소수이므로 3의 잉여역수가 존재한다.
$3 \times 1 \equiv 3$, $3 \times 2 \equiv 6$, $3 \times 3 \equiv 9 \equiv 2$, $3 \times 4 \equiv 12 \equiv 5 \pmod 7$
따라서 $x \equiv 4 \pmod 7$ 이 해가 된다.
Ex 5. 큰 법에서의 역원
문제: $13x \equiv 1 \pmod{60}$ 을 만족하는 $x$를 구하시오.
$\gcd(13, 60)=1$ 이므로 확장 유클리드 알고리즘을 사용한다.
$60 = 4 \times 13 + 8$
$13 = 1 \times 8 + 5$
$8 = 1 \times 5 + 3$
$5 = 1 \times 3 + 2$
$3 = 1 \times 2 + 1$
역추적하면 $1 = 23 \times 13 - 5 \times 60$ 을 얻는다.
$\therefore x \equiv 23 \pmod{60}$
Ex 6. 9의 배수 판정법
문제: 어떤 정수의 각 자릿수의 합이 9의 배수이면 그 수도 9의 배수임을 증명하시오.
정수 $n = a_k 10^k + \dots + a_1 10 + a_0$ 라 하자.
$10 \equiv 1 \pmod 9$ 이므로 $10^i \equiv 1^i \equiv 1 \pmod 9$ 이다.
$n \equiv a_k(1) + \dots + a_1(1) + a_0 \pmod 9$
즉, $n \equiv \sum a_i \pmod 9$ 이므로 자릿수의 합과 원래 수는 9로 나눈 나머지가 같다.
Ex 7. 약분 규칙 (Cancellation)
문제: $10x \equiv 20 \pmod{15}$ 를 풀 때 주의할 점을 서술하시오.
양변을 10으로 단순히 나누어 $x \equiv 2 \pmod{15}$ 라고 하면 틀린다.
$\gcd(10, 15) = 5$ 이므로 법도 $15/5 = 3$ 으로 바뀌어야 한다.
$10x \equiv 20 \pmod{15} \implies 2x \equiv 4 \pmod 3 \implies x \equiv 2 \pmod 3$
법 15에서의 해는 $x \equiv 2, 5, 8, 11, 14 \pmod{15}$ 총 5개이다.
Ex 8. 제곱수의 나머지
문제: 어떤 정수의 제곱을 4로 나누면 나머지는 0 또는 1뿐임을 보이시오.
$n \equiv 0 \pmod 2 \implies n^2 \equiv 0 \pmod 4$
$n \equiv 1 \pmod 2 \implies n^2 = (2k+1)^2 = 4k^2+4k+1 \equiv 1 \pmod 4$
따라서 $n^2 \equiv 0, 1 \pmod 4$ 이며 나머지가 2, 3인 제곱수는 존재하지 않는다.
Ex 9. 날짜와 합동식
문제: 오늘이 월요일이라면 $10^{10}$ 일 후는 무슨 요일인가?
요일은 법 7의 시스템이다. (월=1, 화=2, ..., 일=0)
$10 \equiv 3 \pmod 7$
$10^2 \equiv 9 \equiv 2$, $10^3 \equiv 6 \equiv -1 \pmod 7$
$10^{10} = (10^3)^3 \times 10 \equiv (-1)^3 \times 3 = -3 \equiv 4 \pmod 7$
월요일(1)로부터 4일 후는 금요일(5)이다.
Ex 10. 부정방정식의 변환
문제: $7x + 11y = 1$ 의 정수해를 합동식을 이용해 구하시오.
법 7에 대해 방정식을 쓰면: $11y \equiv 1 \pmod 7$
$4y \equiv 1 \pmod 7$
$4 \times 2 = 8 \equiv 1$ 이므로 $y \equiv 2 \pmod 7$ 이다.
즉, $y = 7k + 2$ 이며, 이를 원래 식에 대입하면 $7x + 11(7k+2) = 1$
$7x + 77k + 22 = 1 \implies 7x = -77k - 21 \implies x = -11k - 3$
$\therefore (x, y) = (-11k-3, 7k+2)$ (단, $k$는 정수)