정수론(Number Theory)

정수론은 수학의 여러 분야 중에서도 가장 오랜 역사를 지닌 분야로, 최근에는 정보과학, 암호론, 통신이론 등에서 널리 활용되며 주목받고 있습니다. 천재적인 수학자 카를 프리드리히 가우스(Karl Friedrich Gauss)는 “수학은 모든 과학의 여왕이며, 정수론은 수학의 여왕이다.”라고 말한 바 있습니다. 이처럼 정수론에는 수학적 사고력을 키울 수 있는 유용한 개념과 기법이 풍부하게 담겨 있습니다.

정수론에서 다루는 문제들이 직관적으로 이해하기 쉽고 간단한 설명으로 제시될 수 있기 때문입니다. 실제로 많은 정수론 문제들은 수학을 전공하지 않은 사람들이 고안했으며, 이러한 점이 정수론의 접근성을 높이는 데 기여했습니다.

정수론의 주요 학습 주제

• 소수(Prime Numbers)
• 약수(divisor)와 배수(multiple)
• 최대공약수와 최소공배수
• 나머지 정리
• 유클리드 호제법(Euclidean Algorithm)
• 합동식
• 수학적 귀납법
• 양의 약수의 성질
• 오일러 함수와 오일러 정리

예제

1. 빨간색 카드가 $7$장, 파란색 카드가 $10$강, 노란색 카드가 $15$장 있다. 빨간색 카드에는 $1,2,\cdots ,7$, 파란색 카드에는 $1,2,\cdots ,10$, 노란색 카드에는 $1,2,\cdots ,15$ 중 하나의 숫자가 적혀 있고, 같은 색 카드에 적혀 있는 숫자는 서로 다르다. 빨간색, 파란 색, 노란색의 카드를 각각 한 장씩 고를 때 세장의 카드에 적혀 있는 수의 합이 $11$의 배수가 되도록 하는 방법의 수를 구하여라. ¹

2. 양의 정수 $n$을 100으로 나눈 몫을 $q$, 나머지를 $r$이라 하자. $q^2+r+1$을 $74$로 나눈 몫이 $r+1$이고, 나머지는 $q$일 때, $n$을 $1000$으로 나눈 나머지를 구하여라. ²

3. $\frac{23}{9}=a+\frac{1}{b+\frac{1}{c+\frac{1}{d}}}$ 를 만족하는 자연수 $a,b,c,d$를 구하여라. ³

4. 양의 정수 $a,b$가 $a^2+b^2+\gcd (a,b)=582$와 $ab+\text{lcm}(a,b)=432$을 만족할 때, $a+b$의 값을 구하여라. ⁴

예제 1.49 (KMO, 2018)

풀이:

조건 (i)는

조건 (ii)는

따라서 각 경우를 따져보면,

따라서 유일하게 조건을 만족하는 경우는 이다. $\square$

다른 예제도 원하시면 인라인 수식 형태로 계속 정리해드릴 수 있습니다.

Footnotes

1. (2011 KMO) 빨간색, 파란색, 노란색에 적혀있는 수를 각각 $r$, $6$, $y$ 라 하면, $1\le r\le 7$, $1\le b\le 10$, $1\le y\le 15$ 이다. $3\le r+b+y\le 32$ 이므로 $r+b+y=11$ 또는 $22$ 이다. $r+b+3=11$ 일 경우, $r=1,2,3,4,5,6,7$ 에 대하여, 각각 $9$개, $8$개, $7$개, $6$개, $5$개, $4$개, $3$개의 경우가 나오므로, 모두 $42$개이다. $r+b+3=22$ 일 경우, $r=1,2,3,4,5,6,7$ 에 대하여, 각각 $5$개, $6$개, $7$개, $8$개, $9$개, $10$개, $10$개의 경우가 나오므로, 모두 $55$개이다. 따라서 모두 $97$개이다. ↩

2. (2016 KMO)조건에 따라 식을 정리하면 $q^2+r+1=74(r+1)+q$, $(0\le q<74)$ 즉, $q(q-1)=73(r+1)$이 된다. 좌변은 $73$의 배수이고, $q-1<73$이므로 $q=73$이다. 이를 위 식에 대입하면 $r=71$이다. 따라서 $n=100\times 73+71=7371$이므로 $n$을 $1000$으로 나눈 나머지는 $371$이다. ↩

3. $23=2\cdot 9+5\Rightarrow a=2$, $9=1\cdot 5+4\Rightarrow b=1$, $5=1\cdot 4+1\Rightarrow c=1$, $4=4\cdot 1\Rightarrow d=4$이므로 $a=2,b=1,c=1,d=4$이다. 유클리드 호제법과 비교해보자. ↩

4. 편의상 $a<b$라 가정하고, $\gcd (a,b)=d$라 하면 $a=dx,b=dy$, $\gcd (x,y)=1$인 양의 정수 $x,y$가 존재한다. $a^2+b^2+\gcd (a,b)=d^2{x}^2+d^2{y}^2+d=d(d{x}^2+d{y}^2+1)=582$, $ab+\text{lcm}(a,b)=d^{2}xy+dxy=dxy(d+1)=432$ 이므로 $d$는 $\gcd (582,432)=6$의 약수이다. $d=2$일 때만, $xy=72$, $x=8,y=9$이면 $a=16,b=18$을 만족한다. 따라서 $a+b=16+18=34$ ↩