9주차 1차시

개강 8주만에 정수론을 시작한다.

예제

• $n$이 음이 아닌 정수일 때, $2^{a}+3^{n}=n!$를 만족하는 음이 아닌 정수 $a,~b$를 찾으시오.

$n \ge 2$일 때 $n!$는 짝수이다. 그런데 $2^{a}$는 $a \ge 1$일 때 짝수, $3^{b}$는 모든 $b \ge 0$에 대해 홀수이므로 주어진 방정식은 $a=0$일 때만 해를 가질 수 있다(해가 있는지는 둘째치고). 따라서 $1+3^{b}=n!$을 만족시키는 $b$를 찾자. 계산해보면 $n=2$일 때 $a=b=0$의 해가 존재한다.

 

이것이 유일한 해일까? $n \ge 3$일 때 $n!$은 $3$의 배수이다. 그런데 $1+3^{b}$는 모든 음이 아닌 정수 $b$에 대해 3의 배수가 아니다. 따라서 주어진 방정식의 해는 $n=2$일 때 $a=b=0$뿐이며, $n \ne 2$일 때는 해가 존재하지 않는다.

그래서 이걸 어따 써먹을 건데?

어.. 다 써먹을 데가 있다. 사실 이걸 어디다 써먹을 수 있는지 알게 된 것도 최근의 일이다.

 

일단 용어 정의부터 하자.

용어 정의

1. $b=ca$일 때 다음이 성립한다.

 

• $a|b$
• $a$는 $b$를 나눈다. ($a$ divides $b$.)
• $a$는 $b$를 나누는 수이다. ($a$ is a divisor of $b$.)
• $b$는 $a$의 배수이다. ($b$ is a multiple of $a$.)

$a|b$임을 증명하려면 $x \times a = b$인 $x$가 존재함을 보여야 한다.

 

2. 정수 $p$에 대해 $1,~-1,~-p,~p$만이 $p$를 나눌 때, $p$를 소수(Prime)이라 한다. 보통은 소수를 생각할 때 양의 정수만을 고려하는 경우가 많으므로, $p$의 범위를 양의 정수로 제한하고 정의에서 $-1$과 $-p$를 빼도 좋다.

 

3. 다음이 성립한다.

 

• $1|a,~-1|a,~a|0$

$1|a$ 증명: $x=a$

$-1|a$ 증명: $x=-a$

$a|0$ 증명: $x=0$

 

• $a|a,~a|-a,~-a|a,~-a|-a$

$a|a$ 증명: $x=1$

$a|-a$ 증명: $x=-1$

$-a|a$ 증명: $x=-1$

$-a|-a$ 증명: $x=1$

 

• $a|b$이고 $a|c$이면, $a|(bx+cy)$

$a|b$이고 $a|c$이므로 $a \times t_{1}=b,~a \times t_{2}=c$를 만족하는 $t_{1},~t_{2}$가 존재한다. $bx+cy=at_{1}x+at_{2}y=a(t_{1}x+t_{2}y)$이므로 $a|(bx+cy)$가 성립한다.

 

• $a|b$이고 $b|c$이면, $a|c$

$a|b$이므로 $b=x_{1}a$를 만족하는 $x_{1}$이 존재하고, $b|c$이므로 $c=x_{2}b$를 만족하는 $x_{2}$가 존재한다. $b=x_{1}a$이므로 $c=x_{2}b=x_{1}x_{2}a=(x_{1}x_{2})a$이다. 따라서 $a|c$가 성립한다.

Division Theorem (정수 나눗셈)

• 0이 아닌 정수 $a$와 정수 $b$에 대해 $b=qa+r,~0 \le r < |a|$를 만족하는 정수 $a$와 $r$이 유일하게 존재한다.

즉 $b$를 $a$로 정수 나눗셈한다는 말은, 위의 식을 만족하는 $q$와 $r$을 찾는다는 말과 같다. 

증명

여기서는 $a,~b$가 양수라고 가정한다. 음수일 때도 같은 방법으로 증명할 수 있다.

 

① $q$와 $r$이 존재함

$i=1$부터 시작하여 $i$를 1씩 증가하면서 $a \times i$를 계산하다 보면 언젠가는 $ka \le b < (k+1)a$를 만족하는 자연수 $k$가 등장한다. $q=k$라고 하면 $b=qa+(b-qa)$이므로 $r=b-qa$를 얻는다. 그런데 $qa \le b$이고 $b < (q+1)a$이므로 $0 \le b-qa<a$이다. 따라서 $b=qa+r$을 만족하는 정수 $q,~r~(0 \le r < a)$이 존재한다.

 

② $q$와 $r$이 유일함

$q$와 $r$이 유일하지 않다고 가정하자. 그러면 $b=q_{1}a+r_{1},~b=q_{2}a+r_{2}$를 만족하는 서로 다른 $q_{1},~r_{1}$과 $q_{2},~r_{2}$ 쌍이 존재한다. 

 

i) $r_{1}=r_{2}$인 경우

$q_{1}a+r_{1}=q_{2}a+r_{2}$이므로 $q_{1}a+r_{1}-(q_{2}a+r_{2})=0$이다. $r_{1}=r_{2}$이므로 $q_{1}a-q_{2}a=0$이다. 그런데 0이 아닌 정수 $a$에 대해 위 식을 만족하려면 $q_{1}=q_{2}$여야 한다. 따라서 $q$와 $r$은 유일하다.

ii) $r_{1} \ne r_{2}$인 경우

 

$r_{2}>r_{1}$이라 가정하자. 위와 같은 방법으로 식을 빼면 $(q_{2}-q_{1})a+(r_{2}-r_{1})=0$이다. 이항하면 $(q_{1}-q_{2})a=r_{2}-r_{1}$이고, $a|(q_{1}-q_{2})a$이므로 $a|(r_{2}-r_{1})$이어야 한다. 그런데 $0 \ge r_{1},~r_{2} <a$에서 $0 < r_{2}-r_{1}<a$이므로 $r_{2}-r_{1}=ax$를 만족하는 양의 정수 $x$를 찾을 수 없다. 증명 과정에 모순이 있으므로 $q$와 $r$이 유일하지 않다는 가정이 잘못되었다. $r_{2} < r_{1}$인 경우에도 같은 방법으로 보일 수 있다.

 

i), ii)에 의해 $q$와 $r$은 유일하게 존재한다.

다음 시간

다음 시간에는 최대공약수에 대해 이야기한다.