나머지 정리

나머지 정리

두 정수 $a$ ($a>0$) 에 대해, 임의의 정수 $b$ 는

$$b=qa+r,0\le r<a$$

를 만족하는 정수 $q,r$ 이 유일하게 존재한다.

증명

집합 $S=\{na-b\mid n\in \mathbb{N}\}$ 를 고려하자. $b\ge 0$ 이면, $b=0a+b$ 이므로 성립한다. $b<0$ 이면, $S$ 는 양의 정수들로 이루어진 집합이므로, 자연수의 최소 원소 정리에 의해 가장 작은 원소를 가지며 이를 $(q+1)a-b$ 라 하자.

이때, $qa-b$ 는

$$(q+1)a-b<(q+1)a-b$$

보다 작으므로 $S$ 의 원소가 아니고, 따라서

$$qa-b\le 0$$

이 성립한다. 따라서 나머지를 $r=b-qa$ 라 하면,

$$r\ge 0,r=b-(q+1)a+a<0+a=a$$

이제 존재성은 증명되었고, 유일성만 증명하면 된다.

$b=qa+r=q^{\prime }a+r^{\prime }$ 이고,

$$0\le r,r^{\prime }<a$$

라고 하면,

$$(q-q^{\prime })a=r^{\prime }-r$$

인데, $-a<r^{\prime }-r<a$ 이므로 $r^{\prime }-r$ 은 $a$ 의 배수이므로 $r^{\prime }-r=0$, 즉

$$r=r^{\prime },q=q^{\prime }$$

가 성립한다. 따라서 $q,r$ 은 유일하게 존재함이 증명되었다.

나머지 정리의 여러 가지 성질

정수의 생성 원리

$a,b\in \mathbb{Z}$ 에 대해,

$$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}(\text{단, }d\in \mathbb{Z})$$

인 $d$ 가 존재한다.

이때,

$$a\mathbb{Z}+b\mathbb{Z}=ax+by(x,y\in \mathbb{Z})$$

로 나타낼 수 있다.

• $d=ax+by$ 로 가정.
• $d$ 는 $a,b$ 의 공약수여야 함.
• $d$ 가 가장 작은 자연수라고 가정하면, 유클리드 호제법을 이용하여 $d$ 가 존재함을 증명할 수 있다.

최대공약수와 생성 원리

$$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}\Rightarrow d=(a,b)$$

즉, 두 정수의 최대공약수는 생성되는 정수의 가장 작은 양수이다.

• $d$ 는 $a,b$ 의 공약수이므로, $d$ 가 $a$ 와 $b$ 를 나눌 수 있음.
• 만약 $c$ 가 $a,b$ 의 공약수이면, $c$ 는 $ax+by$ 의 공약수이므로 $c\le d$ 이다.
• 따라서, 최대공약수는 $d$ 와 같음을 보일 수 있다.

최대공약수와 베주 정리(Bézout’s Identity)

$$(a,b)=1\iff ax+by=1\text{ 인 정수 }x,y\text{ 가 존재한다.}$$

• 두 수가 서로소일 때, 정수 계수로 1을 표현할 수 있다.
• 즉, 서로소 정수는 정수 계수의 선형 결합으로 1을 만들 수 있음을 의미한다.

최대공약수 표현식

$$\gcd (a,b)=sa+tb\text{를 만족시키는 정수 }s,t\text{ 가 존재한다.}$$

이는 확장된 유클리드 알고리즘을 통해 $s,t$ 를 찾을 수 있음을 의미한다.

예제

1. $a=4$, $b=6$ 에 대해, 생성되는 정수의 집합 $4\mathbb{Z}+6\mathbb{Z}$ 를 구하고, 이 집합이 어떤 수의 배수로 표현되는지 확인하시오.¹

2. $15$ 와 $25$의 최대공약수를 구하고, 이를 이용하여 $15\mathbb{Z}+25\mathbb{Z}$을 간단히 표현하시오.²

3. $13$ 과 $17$ 이 서로소임을 확인하고, 베주 항등식 $13x+17y=1$ 을 만족하는 정수해 $(x,y)$ 중 하나를 구하시오.³

4. $\gcd (18,30)$를 구하고, $\gcd (18,30)=sa+tb$를 만족하는 정수 $s,t$를 찾아라.⁴

Footnotes

1. 생성되는 정수의 집합은 $4\mathbb{Z}+6\mathbb{Z}=\{4m+6n\mid m,n\in \mathbb{Z}\}$이며, 이 집합은 최대공약수인 $2$ 의 배수들로 이루어진다. 즉, $4\mathbb{Z}+6\mathbb{Z}=2\mathbb{Z}$ 이다. ↩

2. 최대공약수는 $\gcd (15,25)=5$ 이므로, $15\mathbb{Z}+25\mathbb{Z}=5\mathbb{Z}$ 이다. ↩

3. $13$ 과 $17$ 의 최대공약수는 $1$ 이므로, 베주 항등식을 풀면 $13(-4)+17(3)=1$ 이다. 따라서, 한 해는 $x=-4,y=3$ 이다. ↩

4. $\gcd (18,30)=6$ 이므로, 베주 항등식을 풀면 $18(2)+30(-1)=6$ 이다. 따라서, $s=2,t=-1$ 이다. ↩