정수론 | 유클리드 호제법, 베주 항등식

나눗셈 알고리즘(Division Algorithm)

$a \in Z,\ b \in N$이면 $a=bq+r,\ 0\le r < |b|$를 만족시키는 정수 q와 r이 유일하게 존재한다.

b가 0이 아닌 정수인 경우에도 성립하지만 0이면 a=r이고 자연수인 경우가 증명되면 음수는 부호만 바꾸면 되므로 생략한다.

이 알고리즘을 사용하기 전에 정수 q와 r이 존재하는지와 그 값들이 유일한지에 대해 증명해야 한다.

집합 S에 대해 $S={a-tb\mid t \in Z,a-tb\ge 0}$이라고 정의하자. b는 자연수이므로 $|b|\ge 1, |a|b \ge |a|$가 성립하고 $t=-|a|$를 집합 S에 대입하여 $a-(-|a|b)=a+|a|b \ge a+|a| \ge 0$이므로 $a-tb \ge 0$을 만족하는 정수 t가 하나라도 존재하므로 집합 S는 공집합이 아니다. 그리고 정의에 따라 적어도 S는 $N\cup {0}$의 부분집합임을 확인할 수 있다. 그러므로 S는 정수 0을 포함한 자연수의 집합이므로 최소원소를 가지며 그 값을 r이라고 하면 $a-qb=r$을 만족시키는 적당한 정수 q가 존재함을 알 수 있고 $r \ge 0$을 만족함이 증명된다.

$r<b$를 증명할 땐 결론을 부정하여 $r \ge b$라고 가정하자. 가정에 따라 $r-b=a-qb-b=a-(q+1)b \ge 0$이 되고 집합 S의 정의에 따라 $a-(q+1)b \in S$이다. 그런데 $r-b<r$이므로 r이 최소원소라는 앞서 확인한 내용에 모순된다. 따라서 처음 결론을 부정한 결과가 모순임이 확인되었으므로 r < b임이 확인되어 $0 \le r < b$가 성립한다.

$a=bq+r(0\le r < b)$를 만족하는 정수 q와 r이 존재함을 증명하였다. 이 정수들의 유일성을 증명하기 위해 정수 $q_1, q_2$와 $0\le r_1,r_2<b$를 만족하는 정수 $r_1,r_2$에 대해 $a=bq_1+r_1=bq_2+r_2$를 만족한다고 하자. 정수 q와 r에 대해 정리하면 $b(q_1-q_2)=r_2-r_1$이 되고 이 때 $r_2-r_1$의 범위는 $-b<r_2-r_1<b$이다. (∵ $0\le r_1,r_2<b$이기 때문)

$b(q_1-q_2)$에 대해 b는 자연수이므로 최소정리($b\ge 1$)에 따라 $-1<q_1-q_2<1$가 되고 $q_1,q_2$는 정수이므로 부등식이 성립하기 위해선 $q1-q_2=0$이어야 하며 그와 함께 $r_1=r_2$도 만족한다. 따라서, $a=bq+r(0\le r <b)$를 만족시키는 정수 q,r은 유일하게 존재한다.

유클리드 호제법(Euclidean Algorithm)

$gcd(a,b)=gcd(b,r)=\cdots=gcd(r_{n-1},r_n)=r_n$

참고정리. 정수 a, b, q, r이 $a=bq+r$를 만족한다고 하자. 그러면 $gcd(a,b)=gcd(b,r)$이 성립한다.

$d_1=gcd(a,b), d_2=gcd(b,r)$이라고 하자.

1. $d_1|a, d_1|b \implies d_1|bq+r,\ d_1|b \implies d_1|r$이므로 $d_1|d_2$

   ∵ $d_1$이 r의 약수이므로 b와 r의 공약수가되는데 b와 r의 최대공약수는 $d_2$이므로 $d_1$은 $d_2$의 약수이다.

2. $d_2|b, d_2|r \implies d_2|b,\ d_2|a-bq \implies d_2|a$이므로 $d_2|d_1$

   ∵ $d_2$가 a의 약수이므로 a와 b의 공약수가 되는데 a와 b의 최대공약수는 $d_1$이므로 $d_2$는 $d_1$의 약수이다.

서로 약수와 배수관계이므로 $d_1=d_2$이며 따라서 $gcd(a,b)=gcd(b,r)$이 성립한다.

참고정리를 증명하였으므로 이를 활용하여 유클리드 호제법을 증명하자.

$a,b \in Z$라 하면 나눗셈 알고리즘에 의해 $a=bq+r,(0\le r < b)$를 만족하는 정수 $q,r$이 유일하게 존재한다.

만약 $r=0$이면 gcd(a,b)=b가 되고 $r \ne 0$이면 $b=rq_1+r_1,(0 \le r_1 < r)$을 만족하는 정수 $q_1,r_1$이 유일하게 존재한다. 그리고 앞에서 말한 것과 비슷하게 $r_1=0$이면 $gcd(a,b)=gcd(b,r)=r$을 만족한다.

만약 n번째에 이를 때까지 0이 되지 않으면 밑의 식처럼 일반식으로 나타낼 수 있다.

$r=r_1q_2+r_2,(0 \le r_2 < r_1)$

$\cdots$

$r_{n-1}=r_nq_{n+1}$

결론적으로 gcd(a,b)=gcd(b,r)=$\cdots$=$gcd(r_{n-1},r_n)=r_n$이 된다.

다항식이나 큰 수의 최대공약수를 구하는데 유클리드 호제법이 자주 사용된다.

정리: 최대공약수의 연산법칙

$a,b,q \in Z$이라고 하면 다음의 성질들이 성립한다.

1. $gcd(a,b)=gcd(b,a)$

2. $gcd(a,b)=gcd(a,b \pm qa)$

   $d_1=gcd(a,b)$, $d_2=gcd(a,b\pm qa)$라 하자

   • $d_1|a,\ d_1|b \implies d_1|b\pm qa,\ d_1|a$인데 $gcd(a,b\pm qa)=d_2$이므로 $d_1|d_2$
   • $d_2|a,\ d_2|b\pm qa \implies d_2|a,\ d_2|b$인데 $gcd(a,b)=d_1$이므로 $d_2|d_1$

   따라서 $d_1=d_2$이므로 $gcd(a,b)=gcd(a,b\pm qa)$이다.

3. $gcd(a,1)=1$

4. $gcd(a,b)=gcd(ac,b)$ 단, $gcd(c,b)=1$

   $gcd(a,b)=d_1,\ gcd(ac,b)=d_2$라 하자

   • $d_1|a,\ d_1|b \implies d_1|ac,\ d_1|b$인데 $gcd(ac,b)=d_2$이므로 $d_1|d_2$
   • $d_2|ac,\ d_2|b$와 $gcd(b,c)=1$이므로 $d_2|a,\ d_2|b$에 따라 $d_2|d_1$

   따라서 $d_1=d_2$이므로$gcd(b,c)=1$일 때 $gcd(a,b)=gcd(ac,b)$가 성립한다.

베주 항등식(Bezout's identity)

위의 최대공약수의 연산법칙 증명은 조금 부족한 느낌이 있다. 이 내용을 좀 더 엄격하게 증명해보려 찾아본 결과 베주 항등식에 대한 내용을 정리할 필요성을 찾았다.

적어도 둘 중 하나가 0이 아닌 정수 a, b가 있고 $gcd(a,b)$를 d라고 하자.

1. $d=ax+by$를 성립하게 만드는 정수 x, y가 반드시 존재한다.
2. d는 정수 x, y에 대하여 ax+by 형태로 표현할 수 있는 가장 작은 자연수이다.
3. 정수 x, y에 대하여 ax+by로 표현되는 모든 정수는 d의 배수이다.

집합 S에 대해 $S={m|m=ax+by>0,(x,y\in Z)}$라 정의하면 집합 S는 자연수의 부분집합이고 S가 공집합이 아님을 확인하면 자연수의 정렬성에 따라 최소원소를 가진다.

만약 $a\ne 0$일 때 $|a|=a(\pm1)+b\cdot0 \in S$, $a=0$이면 $b\ne0$으로 $|b| \in S$가 성립하여 집합 S는 최소한 |a|,|b| 중 하나는 원소로 가지므로 공집합이 아니기 때문에 ax+by꼴로 나타나는 값 중 최소값이 존재한다. 그 최소값을 d라 하고 $d=ak+bl$이라고 가정하자.

S의 임의의 원소 x에 대해 나눗셈 정리에 따라 $x=qd+r(0\le r<d)$가 성립함을 알 수 있다. 만약 3번을 부정하여 x가 d의 배수가 아니라고 해보자. 그러면 $r\ne0$이므로 x는 자연수이다. 그리고 x는 집합 S의 원소이기 때문에 $x=as+bt\ (s,t\in Z)$로 표현할 수 있다. 앞에서 $x=qd+r$을 r에 대해 정리하면 $r=x-qd$가 되는데 앞에서 x,d에 대해 ax+by꼴로 정했으므로 이를 대입해서 정리하면 다음과 같다.

$x-qd=as+bt-q(ak+bl)=a(s-qk)+b(t-ql) \in S$

즉, 위의 식에 따라 r도 S의 원소임을 확인하였지만 r은 x를 d로 나누었을 때의 나머지이므로 r<d이다. 그러나 d는 집합 S의 최소원소이므로 이에 모순되어 x는 d의 배수여야 한다. 그리고 x는 S의 임의의 원소라고 정의했으므로 집합 S의 모든 원소는 d의 배수이다.

문제에서 a,b 중 하나는 0이 아닌 정수일 때 |a|혹은 |b|를 원소로 갖는다고 했으므로 d는 a,b의 공약수이다. 물론 둘 중 하나가 0인 경우엔 0이 아닌 모든 수는 0의 약수이므로 모순되지 않는다. 그러나 아직 gcd(a,b)=d를 증명하지 않았다.

d가 최대공약수임을 증명하기 위해 새로운 임의의 공약수를 가정하자. 만약 e도 a,b의 공약수라고 두면 $a=a'e,\ b=b'e$라고 표현할 수 있고 앞서 $d=ak+bl=a'ek+b'el$로 표현할 수 있어 d는 e의 배수이다. 즉, 임의의 a와 b의 공약수는 모두 d의 약수이므로 $gcd(a,b)=d$가 성립한다.

베주 항등식을 이용한 최대공약수의 연산법칙 증명

1. $gcd(a,b)=gcd(a,b\pm qa)$

   $gcd(a,b)=d_1,\ gcd(a,b\pm qa)=d_2$라 하면 베주 항등식에 따라 $d_1|b\pm qa$이고 $d_2$가 최대공약수이므로 $d_1|d_2$이다. $d_2$에 대해서도 $d_2|b\pm qa \mp q\cdot a=b$이고 $gcd(a,b)=d_1$이므로 $d_1=d_2$

2. $gcd(a,b)=gcd(ac,b)$ 단, $gcd(b,c)=1$

   $gcd(a,b)=d_1,\ gcd(ac,b)=d_2$라 하고 베주 항등식에 따라 $d_1=ax_1+by_1$, $d_2=acx_2+by_2$인 정수 $x_1,y_1,x_2,y_2$가 존재한다고 하자. 그리고 $gcd(b,c)=1$에 따라 정수 x,y에 대해 cx+by=1이라고 가정한 뒤 양변에 $d_1$을 곱하여 정리하면$d_1=d_1cx+d_1by$이 된다. 우변의 x의 계수를 ac로 맞추기 위해 앞서 정의한 $d_1$을 대입하면 $(ax_1+by_1)cx+d_1by=ac(x_1x)+b(cy_1x+d_1y)=d_1$이 되어 $d_2|d_1$이 성립한다.

   마찬가지로 cx+by=1 양변에 $d_2$를 곱하면 $d_2=cd_2x+bd_2y$가 되고 앞서 했듯이 계수 ac를 만들기 위해 우변에 대입하면 $c(acx_2+by_2)x+bd_2y=d_2$이고 $d_1$의 꼴로 바꾸면 $a(c^2x_2x)+b(cxy_2+d_2y)=d_2$가 되어 $d_1|d_2$가 성립한다.

예제

$\frac{n^3+2n}{n^4+3n^2+1}$가 모든 정수 n에 대하여 기약분수임을 보여라.

$gcd(1,n)=1$이므로 $gcd(n^3+2n,n^4+3n^2+1)=1$되어 서로소이므로 모든 정수 n에 대해 기약분수이다.

두 수 12378, 3054의 최대공약수를 구하여라.

위 그림에 따라 $gcd(6,18)=6$으로 12378과 3054의 최대공약수는 6이다.

$a \in N$일 때, $gcd(a^7+1,a^3+1)=a+1$임을 증명하라.

따라서, $a^7+1=(a^4-a)(a^3+1)+(a+1)$이고 $a^3+1=(a^2-a+1)(a+1)$로 $gcd(a^7+1,a^3+1)=a+1$이다.

a=11,111,111과 b=11,111,...,111 (1이 2020개)의 최대공약수를 구하라.

예를 들어 k=1,111 ... 111,111 (1이 18개)를 a로 나눠보자. 그럼 k=$10^2\cdot a(10^0+10^{8(2-1)})+11$이 될 것이다. 즉 $18=8\cdot2+2$이고 피제수와 몫 그리고 나머지를 각각 s, q, r이라 하면 $k=10^r\cdot a(1+10^s+\cdots+10^{8(q-1)})+11\cdots11$ (1이 r개) 꼴로 나타날 것이다.

마찬가지로 $2020=8\cdot252+4$이므로 $b=10^4a(1+\cdots+10^{8\cdot251})+1111$이 되어 $gcd(a,b)=gcd(a,1111)$이다. 즉 최대공약수는 1111이다.

$n^3+7$과 $3n^2+3n+1$이 서로소가 아님을 만족하는 양의 정수 n 중 가장 작은 값을 구하여라.

$gcd(n^3+7,3n^2+3n+1)=gcd(3n^3+3n^2+n-(3n^3+21),3n^2+3n+1)$

$=gcd(3n^2+n-21,3n^2+3n+1)=gcd(3n^2+n-21,3n^2+3n+1-(3n^2+n-21))$

$=gcd(3n^2+n-21,2n+22)=gcd(3n^2+n-21-3n(n+11),n+11)$

$=gcd(-(32n+21),n+11)=gcd(32n+21,32(n+11)-(32n+21))$

$=gcd(32n+21,331)$로 정리할 수 있는데 331은 소수이므로 양의 정수 n값이 존재하지 않는다. 그렇다면 그 이전으로 넘어가서 $gcd(32n+21,n+11)$의 경우 $n+11=331$을 만족하는 양의 정수 n값이 존재한다.

따라서, $n^3+7$과 $3n^2+3n+1$이 서로소가 아님을 만족하는 가장 작은 양의 정수 n은 320이다.

$5^{2000}-24\cdot999-25$, $5^{2002}-24\cdot1000-25$, $5^{2004}-24\cdot1001-25$의 최대공약수를 구하여라.

세 수의 최대공약수를 $d$라 하면 각각에 대해 $da,\ db,\ dc$로 표현할 수 있다. 그리고 $gcd(da,db,dc)=gcd(d(c-b),d(b-a))$이므로 대입하여 정리하면 $gcd(5^{2002}(25-1)-24,5^{2000}(25-1)-24)$이므로 $24gcd(5^{2002}-1,5^{2000}-1)$을 구하면 된다.

유클리드 호제법에 따라 $gcd(5^{2002}-1-5^{2000}\cdot25+25,5^{2000}-1)=gcd(5^{2000}-1,5^2-1)$이고 두 제곱수의 차의 형태를 띠고 있으므로 좌항은 우항으로 인수분해가 된다. 따라서, $gcd(5^{2002}-1,5^{2000}-1)=24$이고 앞서 24를 따로 앞으로 옮겼기에 문제에서 제시된 세 수의 최대공약수는 $24^2=576$이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저