1.1 정수와 나눗셈: 실전 예제 10선
나눗셈 알고리즘부터 베주 항등식까지, 정수론의 기초를 다지는 10가지 핵심 예제입니다. 각 풀이는 논리적 증명과 계산 과정을 상세히 담고 있습니다.
Ex 1. 음수의 나눗셈
문제: $a = -45, b = 8$일 때, 나눗셈 알고리즘 $a = bq + r$을 만족하는 $q, r$을 구하시오.
나머지 $r$은 반드시 $0 \le r < 8$이어야 한다.
$-45 = 8 \times (-5) - 5$ (부적합: $r < 0$)
$-45 = 8 \times (-6) + 3$ (적합: $0 \le 3 < 8$)
$\therefore q = -6, r = 3$
Ex 2. GCD 계산
문제: 유클리드 알고리즘을 사용하여 $\gcd(484, 418)$을 구하시오.
$484 = 1 \times 418 + 66$
$418 = 6 \times 66 + 22$
$66 = 3 \times 22 + 0$
마지막 0이 아닌 나머지인 22가 최대공약수이다. $\therefore \gcd(484, 418) = 22$
Ex 3. 베주 계수 구하기
문제: $\gcd(17, 5) = 17x + 5y$를 만족하는 정수 $x, y$를 구하시오.
유클리드: $17 = 3 \times 5 + 2$, $5 = 2 \times 2 + 1$
역추적: $1 = 5 - 2 \times 2$
$1 = 5 - 2 \times (17 - 3 \times 5) = 5 - 2(17) + 6(5) = 7(5) - 2(17)$
$\therefore x = -2, y = 7$
Ex 4. 증명 - 연속 정수의 곱
문제: 임의의 정수 $n$에 대하여 $n(n+1)(n+2)$가 6의 배수임을 증명하시오.
1. 연속한 두 정수 중 하나는 짝수이므로 2의 배수이다.
2. 연속한 세 정수 중 하나는 반드시 3의 배수이다. (나머지 $0, 1, 2$ 케이스 분류)
3. 2와 3은 서로소이므로, 그 곱인 6의 배수가 된다.
Ex 5. GCD 성질 응용
문제: $\gcd(a, b) = 1$이면 $\gcd(a+b, a-b)$가 될 수 있는 값은 무엇인가?
$d = \gcd(a+b, a-b)$라 하면, $d \mid (a+b) + (a-b) = 2a$ 이고 $d \mid (a+b) - (a-b) = 2b$ 이다.
따라서 $d \mid \gcd(2a, 2b) = 2\gcd(a, b) = 2(1) = 2$ 이다.
$\therefore d$는 1 또는 2만 가능하다.
Ex 6. 큰 수의 베주 항등식
문제: $124x + 52y = \gcd(124, 52)$의 정수해 하나를 구하시오.
$124 = 2(52) + 20$
$52 = 2(20) + 12$
$20 = 1(12) + 8$
$12 = 1(8) + 4$
$8 = 2(4) + 0 \implies \gcd = 4$
역추적: $4 = 12 - 8 = 12 - (20-12) = 2(12) - 20 = 2(52-2 \times 20) - 20 = 2(52) - 5(20)$
$4 = 2(52) - 5(124 - 2 \times 52) = 12(52) - 5(124)$
$\therefore x = -5, y = 12$
Ex 7. 나눗셈 알고리즘과 제곱수
문제: 모든 정수의 제곱은 4로 나누었을 때 나머지가 0 또는 1임을 보이시오.
모든 정수 $n$은 $2k$ 또는 $2k+1$ 꼴이다.
1. $n = 2k \implies n^2 = 4k^2 = 4(k^2) + 0$
2. $n = 2k+1 \implies n^2 = 4k^2+4k+1 = 4(k^2+k) + 1$
따라서 나머지는 항상 0 또는 1이다.
Ex 8. 다항식 형태의 GCD
문제: 임의의 $n$에 대해 $\gcd(n, n+1)$의 값을 구하시오.
나눗셈 알고리즘에 의해 $(n+1) = 1 \times n + 1$이다.
$\gcd(n+1, n) = \gcd(n, 1) = 1$
따라서 연속한 두 정수는 항상 서로소이다.
Ex 9. 해의 존재 여부
문제: 방정식 $6x + 9y = 10$이 정수해를 갖지 않음을 설명하시오.
좌변 $6x + 9y = 3(2x + 3y)$는 항상 3의 배수이다.
우변 10은 3의 배수가 아니다.
따라서 이를 만족하는 정수 $x, y$는 존재할 수 없다. (참고: $\gcd(6, 9)=3 \nmid 10$)
Ex 10. 최소공배수(LCM)
문제: $ab = 600, \gcd(a, b) = 10$일 때, $LCM(a, b)$를 구하시오.
정리: $\gcd(a, b) \times LCM(a, b) = |ab|$
$10 \times LCM(a, b) = 600$
$\therefore LCM(a, b) = 60$