선형 디오판토스 방정식

간단히 말하면 부정방정식 중 정수해만을 구하는 방정식을 말한다. 디오판토스 방정식에는 여러 형태가 있지만 유클리드 호제법과 베주 항등식에 나오는 식과 유사한 ax+by=c를 선형 디오판토스 방정식(Linear Diophantine equation)이라 부른다. c=gcd(a,b)면 베주 항등식이 된다.

정리: $a,b \in N$이라고 하자. 그러면 $gcd(a,b)=ax+by$를 만족하는 정수 $x,y\in Z$가 존재한다.

베주 항등식의 해는 유일하지 않으며 확장된 유클리드 호제법으로 구할 수 있다.

해가 존재하는 지 증명

$S={ax+by\ |\ x,y\in Z}$라 정의하고 집합 S가 다음 세개의 성질을 만족함을 증명하자.

  1. $a,b\ \in S$

    $a=a\cdot1+b\cdot0\in S,\ b=a\cdot0+b\cdot1 \in S$

  2. $u \in S \implies u\cdot t \in S,\ \forall t\in Z$

    $u\in S$이면 $\exists\ x_1,y_1 \in Z\ s.t. u=ax_1+by_1$이며 $u \cdot t=t(ax_1+by_1)=a(tx_1)+b(ty_1)\in S$

  3. $u_1,u_2 \in S \implies u_1\pm u_2 \in S$

    $u_1,u_2 \in S$라 하면 $u_1=ax_1+by_1$, $u_2=ax_2+by_2$를 만족하는 정수 $x_1,x_2,y_1,y_2$가 존재한다.

    $u_1\pm u_2=ax_1+by_1 \pm\ (ax_2+by_2) = a(x_1\pm x_2)+b(y_1\pm y_2) \in S$

따라서 $a=bq+r,\ 0\le r<b$에 대하여 $a,b \in S$이므로 $a-bq=r\in S$이다. $r=0$인 경우 gcd(a,b)=b이고 $r\ne0$이면 $b=rq_1+r_1,\ 0\le r_1<r$로 표현할 수 있고 $b,r\in S$이므로 $r_1=b-rq_1$이 되어 S의 원소가 된다. 이를 마지막까지 반복하면 $r_n=gcd(a,b)\in S$가 되어 gcd(a,b)=ax+by를 만족하는 정수 x, y가 존재하며 유클리드 알고리즘의 증명도 할 수 있다.

선형 디오판토스 방정식의 일반해

그렇다면 베주 항등식이 아니라 선형 디오판토스 방정식 $ax+by=c$에 대해 (x,y)의 해를 구해보자. 이전 포스팅과 위에서 베주 항등식 $ax+by=gcd(a,b)=d$에 대해 성립하게 만드는 x, y가 반드시 존재하고 $ax+by$로 표현되는 모든 정수는 d의 배수임을 확인하였다.

즉, 앞서 베주 항등식을 토대로 $ax+by=c$의 해가 존재 유무와 c는 $gcd(a,b)$의 배수라는 조건은 서로 필요충분조건임을 확인하였다. 선형 디오판토스 방정식의 특수해가 존재하고 우변이 a와 b의 최대공약수의 배수임을 알아냈으니 일반해를 표현해보자.

(x,y)가 임의의 해라고 가정하면 $ax_0+by_0=ax+by$이고 이를 정리하면 $a(x-x_0)=-b(y-y_0)$이다. 여기서 양변을 $gcd(a,b)=d$로 나누면 $\cfrac{a}{d}(x-x_0)=-\cfrac{b}{d}(y-y_0)$인데 $gcd(\cfrac{a}{d},\cfrac{b}{d})=1$이므로 $\cfrac{a}{d}|y-y_0$이다. 따라서 적당한 정수 $k_x$에 대해 정리하면 $\cfrac{a}{d}k_x=-(y-y_0)$이고 정리하면 $y=y_0-\cfrac{a}{d}k_x$이다. 마찬가지로 x에 대해 정리하면 $x=x_0+\cfrac{b}{d}k_y$를 얻는다. 따라서 $d=gcd(a,b)$이므로 ax+by=c의 정수해 (x,y)는 특수해 $x_0,y_0$에 대해 $[(x_0+\cfrac{b}{d}k,y_0-\cfrac{a}{d}k),k\in Z]$로 표현할 수 있다.

확장 유클리드 호제법

확장 유클리드 호제법은 유클리드 호제법을 역으로 계산하여 $ax+by=c$를 만족하는 (x,y)쌍을 구하는 알고리즘이다.

먼저 x,y의 점화식을 도출하기 위해 이전의 유클리드 호제법 과정을 다시 작성해보자.

$a=bq+r_2$

$b=r_2q_2+r_3$

$r_2=r_3q_3+r_4$

$\cdots$

$r_n=r_{n+1}q_{n+2}$와 같이 전개가 되어 결국 마지막에 남는 값이 최대공약수가 되고 이것을 참고하면 아래와 같은 조건이 생긴다.

$r_{n+2}=r_n-r_{n+1}q_{n+2},\ ax_n+by_n=r_n$

$=ax_n+by_n-(ax_{n+1}+by_{n+1})q_{n+2}$

$=a(x_n-x_{n+1}q_{n+2})+b(y_n-y_{n+1}q_{n+2})$

$\implies (x_{n+2},y_{n+2})=(x_n-x_{n+1}q_{n+2},y_n-y_{n+1}q_{n+2})$

위와 같이 점화식을 도출하였고 유클리드 호제법의 결과에 따라 $gcd(a,b)=r_{n+2}$라 하자. 그리고 점화식의 초항이 필요한데 유클리드 호제법의 전개식을 보면 a와 b에 대해서도 r과 같이 해석할 수 있으므로 $r_0=a,\ r_1=b$라 하면 $a=ax_0+by_0$에서 $(x_0,y_0)=(1,0)$이고 $b=ax_1+by_1$에서 $(x_1,y_1)=(0,1)$이다. x, y에 대해 점화식과 초항을 구하였으므로 차례대로 계산하면 된다. 아래 예시를 구해보자.

예제

두 수 710, 68의 최대공약수를 구하고 $gcd(710,68)=710x+68y$를 만족하는 정수 x, y를 구하여라.

유클리드 호제법을 사용하면 gcd(710,68)은 금방 아래와 같이 구할 수 있다.

$710=68\cdot10+30$

$68=30\cdot2+8$

$30=8\cdot3+6$

$8=6\cdot1+2$

$6=2\cdot3$으로 $gcd(710,68)=2$를 구하였다.

이제 이걸 다시 역산하면 x, y값이 아래와 같이 나온다.

$2=8-6 \qquad \Longleftarrow 2=8-6$

$=4\cdot8-30 \quad \Longleftarrow 6=30-8\cdot3$

$=68\cdot4-30\cdot9 \quad \Longleftarrow 8=68-30\cdot2$

$=710\cdot(-9)+68\cdot94 \quad \Longleftarrow 30=710-68\cdot10$

$\therefore x=-9,\ y=94$

정수해가 구해졌으므로 위의 베주항등식의 일반해에 대입하면 다른 해를 구할 수 있다. 위에서 구한 일반해에 대입하면 (x,y)는 각각 $(-9+\cfrac{68}{2}k,94-\cfrac{710}{2}k)$로 k가 어떤 정수건 다른 해를 만들 수 있다. 예를 들어 1을 대입 시 (25,-261)이 나오는데 문제에 제시된 수식에 대입하면 $710\cdot25+68\cdot(-261)=2$가 성립한다.

정리: $a,b\in N$에 대하여, $gcd(a,b)=1$과 $\exists x,y\in Z\quad s.t.\ ax+by=1$은 필요충분관계이다.

앞서 베주 항등식을 통해 증명하였으므로 생략하겠다.

정리: $ax+by=1$이면 $gcd(a,b)=gcd(a,y)=gcd(x,b)=gcd(x,y)=1$이 성립한다.

정수해를 갖는 조건이라면 베주 항등식에 따라 우변은 gcd(a,b)의 배수여야 하므로 gcd(a,b)=1이다. 그리고 a, b와 똑같은 관점으로 다른 미지수에도 적용 가능하므로 제시된 조건을 만족한다.

정리: $a,b\in N$에 대해 $gcd(a,b)=d\Rightarrow gcd(\cfrac{a}{d},\cfrac{b}{d})=1$

정리: $a,m,n\in N$라 하면, $gcd(a,mn)=1 \iff gcd(a,m)=1$이고 $gcd(a,n)=1$이다.

필요충분조건임을 증명하기 위해 제시된 명제와 그 역이 성립함을 증명하자.

$gcd(a,mn)=1$일 때 $ax+mny=1$을 만족하는 정수 x, y가 존재한다. $a(x)+m(ny)=1$로 보면 $gcd(a,m)=1$이며 $a(x)+n(my)=1$로 보면 $gcd(a,n)=1$이다.

역으로 $gcd(a,m)=gcd(a,n)=1$이라 하자. 그럼 $ax_0+my_0=1$과 $ax_1+ny_1=1$을 만족시키는 정수 $x_0,x_1,y_0,y_1$이 존재한다.

$1=ax_0+my_0(ax_1+ny_1)=ax_0+amx_1y_0+mny_0y_1$

$=a(x_0+mx_1y_0)+mn(y_0y_1)=1$

$\therefore gcd(a,mn)=1$

정리: $a,b,S\in N$이라 하자. $a|S$, $b|S$, $gcd(a,b)=1$이면 $ab|S$이다.

$a|S,\ b|S$에 따라 적당한 정수 x, y에 대해 $ax=by=S$이다. 그렇다면 $a|by$가 성립하고 gcd(a,b)=1에 따라 $a|y$이다. 그리고 적당한 정수 z가 존재하여 $az=y$이고 $S=b\cdot az=abz$가 되어 $ab|S$를 만족한다.

작성에 도움이 된 자료

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


나눗셈 알고리즘(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에 대하여 기약분수임을 보여라.

유클리드 호제법 계산 1

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

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

유클리드 호제법 계산 2

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

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

유클리드 호제법 계산 3

따라서, $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 수학경시 정수론, 장환수학, 임장환 저


자연수 $n$의 소인수 분해식을 $n=p_1^{e_1}p_2^{e2}\cdots p_k^{e_k}$이라고 하면,

양의 정수 $n$의 약수개수는 $r(n)=(e_1+1)(e_2+1)\cdots (e_k+1)$

$n$의 약수들의 총합은 $\sigma(n)=(1+p_1+\cdots+p_1^{e_1})(1+p_2+\cdots+p_2^{e_2})\cdots(1+p_k+\cdots+p_k^{e_k})$

$= (\frac{p_1^{e_1+1}-1}{p_1-1})(\frac{p_2^{e_2+1}-1}{p_2-1})\cdots (\frac{p_k^{e_k+1}-1}{p_k-1})$

예제

양의 정수 $n=2^{30}3^{15}$에 대해, $n^2$의 양의 약수 중 $n$보다 작고 $n$의 약수가 아닌 것의 개수를 구하여라.

$n$이 $2^23$이라 생각해보자.

$n^2$의 약수를 나열하면 $1,2,3,4,6,8,9,12,16,18,24,36,48,72,144$로 총 15개임을 알 수 있다. 즉, 제곱수이므로 홀수 개의 약수를 가지며 피제곱수를 중심으로 양 옆에 같은 수의 약수가 분포한다.

$n^2$의 약수 중 $n$보다 작은 약수의 개수는 $\bigr[\cfrac{61\cdot31}{2}\bigl]$이고 여기서 $n$의 약수는 $31\cdot16$이므로 $\bigr[\cfrac{61\cdot31}{2}\bigl]-(31\cdot16-1)=450$

$2^{18}+1$의 양의 약수의 총합을 $A$라고 할 떄, $\big[ \frac{A}{1000} \big]$를 구하여라.

양의 약수의 총합을 구해야 하므로 $2^{18}+1$을 소인수 분해식의 형태로 나타내야 한다. $k=2^4$라 했을 때 $(2k^2)^2+1$로 나타낼 수 있고 식을 조금 변형하여

$(2k^2)^2+2\cdot2k^2+1-2\cdot2k^2$

$=((2k^2)+1)^2-(2k)^2$

$=(2k^2+2k+1)(2k^2-2k+1)$로 나타낼 수 있다.

다시 $k$를 대입하면 $481\cdot545=13\cdot37\cdot5\cdot109$으로 $14\cdot38\cdot6\cdot110$이 약수의 총합이 되어 $\big[ \cfrac{351120}{1000} \big]=351$이 된다.

여기서 $481$이 $13\cdot37$이란 사실을 찾기 힘들 수 있다. 보통 소인수 분해 시 10이상 넘어가면 소수로 판단하기 쉽기 때문이다. (필자가 그랬음)

$k=2^6$이라 했을 떄 $k^3+1$로 나타낼 수 있고 이는 $(k+1)(k^2-k+1)$로 나타낼 수 있으므로 $k+1=65=5\cdot13$임을 알 수 있다. 위에서 545가 5의 배수이나 13의 배수임이 아닌 것을 확인하였으므로 481은 13의 배수이다.

개인적으로 $k^3+1$의 인수분해식까지 유념할 것 같진 않지만 익숙해지거나 습관이 들면 가능하겠다 싶어서 함께 작성하였다.

자연수 $n$에 대하여 $2n$은 28개의 양의 약수를 갖고, $3n$은 30개의 양의 약수를 가질 때, $6n$의 양의 약수의 개수를 구하여라.

$n=2^a3^b5^c\cdots p^k$라 하자. $n$의 양의 약수의 개수는 $(a+1)(b+1)(c+1)\cdots(k+1)$이다. 문제에서는 2와 3에 대해서만 다루고 있으므로 뒤의 $(c+1)\cdots(k+1)$를 $A$로 치환하자.

$2n$의 약수의 개수는 $(a+2)(b+1)A=28$, $3n$의 약수의 개수는 $(a+1)(b+2)A=30$이다.

둘을 서로 빼면 $A(a-b)=2$이므로 $(A,(a-b))=(1,2)or(2,1)$이다.

  1. $A$가 1이면 $a=b+2$이고 식에 대입하여 $a=5,b=3$을 얻을 수 있다.
  2. $A$가 2면 $a=b+1$이고 식에 대입하였을 때 $b^2+4b-11=0$에 따라 해가 무리수이므로 성립하지 않는다.

따라서 $6n$의 양의 약수의 개수는 $(5+2)(3+2)=35$이다.

양의 정수 $n$에 대하여 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$의 해 (x,y)의 개수를 구하여라.

양변에 $nxy$를 곱하여 정리하면 $ny+nx=xy$를 얻을 수 있고 우변으로 옮긴 후 $n^2$을 더해 정리하면 $(x-n)(y-n)=n^2$가 완성된다. $n$의 소인수 분해식이 $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$라고 했을 때, 문제의 조건에 따라 $x,y>n$이므로 $n^2$의 약수에 대해 $(x,y)$가 한쌍씩 일대일 대응으로 성립한다. 따라서, 해의 개수는 $\gamma(n^2)=(2e_1+1)(2e_2+1)\cdots(2e_k+1)$이다.

$\frac{3}{18620}=\frac{1}{a}+\frac{1}{b}$를 만족시키는 양의 정수 $a,b$의 순서쌍 $(a,b)$의 개수를 구하여라.

18620을 $A$라 하자. $\cfrac{3}{A}=\cfrac{1}{a}+\cfrac{1}{b}$ 에서 양변에 $Aab$를 곱한 후 정리하면 $3ab-A(a+b)=0$가 된다. 하지만 이 경우 두 수의 곱으로 표현할 수 없기 때문에 양변에 3을 곱하고 $A^2$을 더한 뒤 인수분해를 하면 $(3a-A)(3b-A)=A^2$의 식을 얻을 수 있다. 그리고 18620을 소인수분해하면 $2^2\cdot5\cdot7^2\cdot19$이므로 $(3a-18620)(3b-18620)=2^4 5^2 7^4 19^2$이다.

18620을 3으로 나눈 나머지는 2이므로 $3a-18620 \equiv 3b-18620 \equiv 18620^2 \equiv 1(mod\ 3)$이다. 그러므로 18620을 두 수로 분할한 값은 각각 3으로 나눈 나머지가 1이어야 한다. $2^4 5^2 7^4 19^2$를 $3a-18620$과 $3b-18620$으로 분리했을 때 3으로 나눈 나머지가 1이어야 하므로 각 인수별로 3으로 나눈 나머지가 2가 되는 경우가 있는지 검사하여야 한다. $2\equiv2^3\equiv2(mod\ 3),\ 5\equiv2(mod\ 3),\ 2^2\equiv2^4\equiv1(mod\ 3),\ 7\equiv 19\equiv5^2\equiv 1(mod\ 3)$ 이므로 $2^4 5^2$를 분할하는 경우엔 3으로 나눈 나머지가 모두 2이거나 1이 되도록 묶어줘야 한다.

$2\equiv2^3\equiv2(mod\ 3)$은 2와 8을 3으로 나눈 나머지가 2임을 의미한다. 자세한 개념은 '합동식'을 찾아보자. (나중에 포스팅으로 다룰 예정)

$2^45^2$를 분할하는 방법으로는 모두 1인 경우의 (1,4,16)(1,25)와 모두 2인 경우의 (2,8)(5)이 있으므로 $3\cdot2+2\cdot1$이 되어 8가지이다. 그리고 나머지 약수에 대해서는 모든 경우에 대해 성립하므로 $8\cdot(4+1)\cdot(2+1)=120$이다.

양의 정수 $n$을 두 개 이상의 연속한 양의 정수의 합으로 나타내는 방법을 생각하자. 예를 들어 15의 경우에는 7+8, 4+5+6, 1+2+3+4+5의 세 가지 방법이 있다. 999를 이와 같이 나타내는 방법의 수를 구하여라.

$(n+1)+(n+2)+\cdots+(n+k)=999$라 하자. 좌변을 정리하면 $nk+\frac{k(k+1)}{2}=999$가 되고 양변에 2를 곱하여 정리하면 $2nk+k^2+k=k(k+2n+1)=2\cdot999=2\cdot3^3\cdot37$이 된다. 문제에서 두 개 이상의 연속한 양의 정수의 합으로 나타낸다 했으므로 $k$의 범위는 $2\leq k < k+2n+1$이며 이 조건에 만족하지 않는 경우는 (1,999)밖에 없다.

$2\cdot999$의 약수의 개수는 $2\cdot4\cdot2=16$이고 조건에 맞지 않는 약수는 2개에 $k+2n+1$보다 작아야 하므로 나타낼 수 있는 방법의 개수는 $\frac{16-2}{2}=7$이다.

양의 정수 $k$에 대하여 $a_k=\frac{(2^k)^{30}-1}{31}$이라 하자. $S=a_1+a_2+\cdots+a_{10}$이라 할 때, S를 31로 나눈 나머지를 구하여라.

주어진 수식은 초항이 1이고 공비가 32인 등비급수의 합을 나타내는 수식으로 $a_k=\cfrac{(2^5)^{6k}-1}{32-1}$ 과 같이 변형할 수 있다. 즉 $a_k=1+2^5+\cdots+(2^5)^{6k-1}$로 표현할 수 있고 각 항을 31로 나누면 $\cfrac{a_k}{31}\equiv1+1+\cdots+1=6k(mod31)$이다. 문제에서 주어진 $S$를 대입해서 나타내면 $\frac{S}{31}\equiv6(1+2+\cdots+10)(mod\ 31)=6\cdot\cfrac{10\cdot11}{2}(mod\ 31)=20$

작성에 도움이 된 자료

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


약수와 배수

$a,d \in Z$이고, $d \neq 0$이라고 가정했을 때, $a=cd$를 만족하는 어떤 정수 $c$가 존재한다면 $d$는 $a$의 약수라 부른다. 그리고 $a$는 $d$의 배수이다. 이 경우 $a$와 $d$의 관계는 $d \mid a$로 표기한다.

참고사항

다음 관계식은 문제 해결에 자주 사용되므로 숙지할 필요가 있다.

  1. $2 \mid a(a+1)$

    $a$가 $2k \;(k \in Z)$이면 $a(a+1))=2k(2k+1)$로 성립, $a$가 $2k+1$이면 $(2k+1)(2k+2)$로 성립

  2. $3 \mid a(a+1)(a+2)$

    $a$가 $3k,3k+1,3k+2 \; (k \in Z)$이면 $a(a+1)(a+2)=3k(3k+1)(3k+2), (3k+1)(3k+2)(3k+3), (3k+2)(3k+3)(3k+4)$로 성립

  3. $6 \mid a(a+1)(a+2)$

    $2 \mid a(a+1),\; 3\mid a(a+1)(a+2)$이므로 $a(a+1)(a+2)$는 $2$와 $3$의 공배수가 되어 $6 \mid a(a+1)(a+2)$가 성립

약수의 성질 - 연산

직관적으로 알 수 있는 내용이지만 막상 문제를 해결할 땐 잘 떠오르지 않아 숙지해야 하는 몇가지 약수의 성질들을 나열하였다. $a,b,c,d \in Z$의 경우 다음을 만족한다.

  • $d \mid a, d\mid b \implies d \mid ax \pm by \quad (x,y \in Z)$

    $a=md, b=nd \quad (m,n \in Z)$에 따라 $ax \pm by = mdx \pm ndy = d(mx \pm ny)$

  • $d \mid a, d \mid ax \pm b \quad (x \in Z) \implies d \mid b$

    $a=md, (ax \pm b)=nd \quad (m,n \in Z)$에 따라 $\pm b = nd-ax=d(n-mx)$

  • $a \mid b, b \mid c \implies a \mid c$

    $b=am, c=bn \quad (m,n \in Z)$에 따라 $c=amn$

  • $d \mid 1 \implies d=\pm1$

    $d \mid 1 \implies 1=dn \quad (n \in Z)$에 따라 $\lvert 1 \rvert = \lvert dn \rvert \leq \lvert d \rvert$

위 내용들은 합동관계에 대해 설명할 때 등장하며 알고리즘 문제에서도 합동식에 관련된 문제가 꾸준히 출제되고 있어 알아두면 좋을 것 같다.

최대공약수(gcd, greatest common divisior)

$a,b \in Z$에 대해 정수 $d \ (d>0)$가 $d \mid a, d \mid b$를 만족하고 $c \mid a, c\mid b$인 정수 $c$에 대해 $c \mid d$를 만족하면 $d$를 $a,b$의 최대공약수라 부르고 $d=gcd(a,b)$로 표기한다. 만약 $d=1$이라면 $a,b$는 서로소라 부른다.

예제

$n \in Z$에 대해 $gcd(n!+1, (n+1)!+1)=1$임을 증명하라

$d=gcd(n!+1,(n+1)!+1)$라 하자. $d \mid (n+1)(n!+1)=(n+1)!+n+1$ 또한 약수의 성질에 따라 성립한다. 그리고 $d \mid (n+1)!+n+1-n!-1$이므로 $d \mid n$를 만족하여 $d \mid n!$이다.

$d \mid n!$과 $d \mid n!+1$이므로 $d \mid n!+1-n!=1$이므로 $d=1$가 되어 $gcd(n!+1,(n+1)!+1)=1$이다.

정수 $a,b,c$을 자연수 $k$로 나누었을 때, 나머지가 같을 필요충분조건은 $k \mid a-b, k \mid c-b$임을 증명하여라

$a,b,c$를 각각 $m_1d+r, \; m_2d+r, \; m_3d+r$이라고 하면 $a-b=d(m1-m2), \; c-b=d(m3-m2)$가 되어 $d \mid a-b, \; d\mid c-b$가 성립한다.

하지만, 만약 $a=m_1d+r_1,\;b=m_2d+r_2$가 되어 $a-b = d(m_1-m_2)+(r_1-r_2)$라 한다면 $d \mid a-b$이라는 전제에 따라 $d \mid (a-b)-d(m_1-m_2)=r_1-r_2$이다. $-d<r_1-r_2<d$이므로 $d$가 $r_1-r_2$의 약수임이 확인되었는데 피제수인 $r_1-r_2$가 $d$보다 작다는 건 모순되므로 $r_1-r_2=0$가 되어 $a,b$를 $d$로 나누었을 때 나머지는 같다.

같은 방법으로 $c,b$에 대해서도 똑같이 증명이 가능하므로 $b,c$를 $d$로 나누었을 때의 나머지도 같음을 알 수 있다. 그리고 $d \mid a-b, d \mid c-b$를 활용하여 $d \mid (a-b)-(c-b) = a-c$이므로 위의 방법에 의해 $a,c$ 또한 $d$로 나누었을 떄의 나머지도 같다.

∴ $k \mid a-b, \; k \mid c-b$를 만족해야 $a,b,c$를 $k$로 나누었을 때 나머지 $r$이 같고 그 역 또한 성립한다.

유클리드의 보조정리(Euclid's Lemma)

$p$, $q$는 서로 다른 소수이고 $a$, $b$는 정수라 하자. 이 경우 $p \mid ab$이면 $p \mid a$ 또는 $p \mid b$이다.

  • $p \mid a^k$이면 $p \mid a$이다.
  • $p \mid a$, $q \mid a$이면 $pq \mid a$이다.

예제

$a,b \in N$이고 $gcd(a,b) = 1$이라 하자. 만약 $d \neq 1$이고 $d \mid ab$이면 다음 조건을 만족하는 소수 $p$가 존재한다.

  1. $p \mid ab$
  2. [$p \nmid a$ 이고 $p \mid b$] 또는 [$p \mid a$이고 $p \nmid b$]이다.

$d > 1$이라 했으므로 집합 S를 1보다 큰 $d$의 약수집합이라 하자. $d \in S$이므로 S는 공집합이 아니며 자연수의 순서정리에 따라 집합 S는 최소원소 $p$를 갖는다. 이 때 $p$는 소수이고 $d$의 약수이므로 $p \mid ab$를 만족하는 소수 $p$가 존재한다.

$p$가 소수이고 $gcd(a,b)=1$이며 $p \mid ab$가 성립하므로 [$p \nmid a$ 이고 $p \mid b$] 또는 [$p \mid a$이고 $p \nmid b$]가 성립한다.

$a,b \in N$이고 $gcd(a,b)=1$라 하자. 그러면 $gcd(a+b,ab)=1$임을 증명하여라.

소수 $p$가 $p \mid ab$이고 $p \mid a+b$라 하자. 만약 $p \mid a$라 하면, $p \mid b$이므로 $gcd(a, b)=1$에 모순된다. 반대의 경우에도 동일하기 떄문에 $p \mid ab$이고 $p \mid a+b$를 동시에 만족하는 소수 $p$는 존재하지 않는다.

(∵ 1이 아닌 소수 $p$가 $p \mid a+b$이고 $p \mid ab$이려면 $p \mid a, \; p \mid b$를 모두 만족해야 하기 때문이다.)

  • 참고. 합동관계 관련 내용에도 속한다. (이후에 다룰 예정)

양의 정수 $d$에 대하여, $d$가 $4a^2+9b^2$과 $ab$의 최대공약수가 되도록 하는 서로소인 양의 정수 $a,b$가 존재한다고 한다. 이러한 $d$의 개수를 구하여라.

문제의 조건에 따라 $gcd(a,b)=1$이고 $d \mid ab$이므로 $d=AB$라 할 수 있다. ($A$는 $a$만의 약수, $B$는 $b$만의 약수)

$A \mid a, \; A \nmid b$에서 $A \mid 4a^2+9b^2$로부터 $A \mid 9b^2$여야 하므로 $A \mid 9$

$B \mid b, \; B \nmid b$에서 $B \mid 4a^2+9b^2$로부터 $B \mid 4a^2$여야 하므로 $B \mid 4$

즉, $d$가 AB=36의 약수여야 $d=gcd(4a^2+9b^2, ab)$를 만족하기 떄문에 $d$의 개수는 9개이다.

양의 정수 $a,m,n \; (101 \leq a \leq 199)$이 [$m+n$은 $a$의 배수], [$mn=a(a+1)$] 두 조건을 만족할 때 $m+n$의 값을 구하여라.

$m+n=d(m'+n')=ak, \; mn=d^2m'n'=a(a+1)$이 되는데 $gcd(a,a+1)=1, \; gcd(m',n')=1, \; gcd(m'+n',m'n')=1$이므로 $a$는 완전제곱수이다.

$a|m+n,\ mn=a(a+1)$에서 a의 인수 중 $p|m\ or\ p|n$을 만족하는 p가 존재한다. 한쪽의 경우로 예를 들어 만약 $p|m$일 때, $p|a$이고 $a|m+n$이므로 $p|n$이 된다. 그리고 $gcd(a,a+1)=1$이므로 mn의 인수 중 앞에서 작성하였듯이 p를 제외한 a에 속하는 모든 인수 q도 m과 n에 공통으로 속하므로 a는 완전제곱수가 된다.

주어진 범위를 만족하는 완전제곱수는 $11^2,12^2,13^2,14^2$가 있다.

  • $a$가 121일 때

    $m=11m_1,\ n=11n_1$이라고 하면, $m_1n_1=(11^2+1),\ 11|m_1+n_1$

    $11^2+1=122=2 \cdot 61$이므로 $(m_1,n_1)=(1,122), \; (2,61)$에 따라 $m_1+n_1 = 123 \; or \; 63$ 중 11의 배수는 없다.

  • $a$가 144일 때

    $m=12m_1,\; n=12n_1$이라고 하면, $m_1n_1=(12^2+1), \; 12|m_1+n_1$

    $12^2+1=145=5 \cdot 29$이므로 $(m_1,n_1)=(1,145), \; (5,29)$에 따라 $m_1+n_1 = 146 \; or \; 34$ 중 12의 배수는 없다

  • $a$가 169일 때

    $m=13m_1,\; n=13n_1$이라고 하면, $m_1n_1=(13^2+1), \; 13|m_1+n_1$

    $13^2+1=170=10 \cdot 17$이므로 $(m_1,n_1)=(1,170), \; (2,85), \; (5,34), \; (10,17)$에 따라 $m_1+n_1 = 171, \; 87, \; 39, \; 27$ 중 39가 13의 배수이므로 $m+n=13(39)=507$

  • $a$가 196일 때

    $m=14m_1,\; n=14n_1$이라고 하면, $m_1n_1=(14^2+1), \; 14|m_1+n_1$

    $14^2+1=197=1 \cdot 197$이므로 $(m_1,n_1)=(1,197)$에 따라 $m_1+n_1 = 198$은 14의 배수가 아니다.

따라서, $m+n$은 507이다.

양의 정수 $m$과 홀수 $n$이 방정식 $m+\frac{1}{m}=6(\frac{n}{8}+\frac{8}{n})$을 만족할 때, $mn$의 값을 구하시오.

$m,n$이 0이 아니므로 양변에 $4mn$을 곱하여 주어진 수식을 보기좋게 변형하면 $4n(m^2+1)=3m(n^2+8^2)$이 된다.

$4 \mid 3m(n^2+8^2)$이고 $n$이 홀수이므로 $n^2+8^2$도 홀수가 되어 $4 \mid m$이다.

$3 \mid 4n(m^2+1)$이고 $3 \nmid m^2+1$이므로 $3 \mid n$이다.

  • m=3k일 때 $3 \nmid (3k)^2+1$
  • m=3k+1일 때 $3 \nmid (3k)^2 +2 \cdot 3k + 1$
  • m=3k+2일 때 $3 \nmid (3k)^2+2 \cdot 6k + 4$

$m=4m', n=3n'$ ($n'$은 홀수) 하여 변형된 수식에 적용 후 정리하면 $n'(16m'^2+1)=m'(9n'^2+8^2)$이다. 양변 모두 홀수이므로 $m',n'$모두 홀수에 따라 $m'=2a+1, \; n'=2b+1$로 표현할 수 있다. 그러나 두 값을 위 공식에 대입하면 정리되지 않으므로 $m',n'$가 모두 홀수라는 사실만 가져간다.

다른 방법으로 $gcd(m',n')=d$라 할 때, $m'=da, \; n'=db \quad gcd(a,b)=1$로 표현할 수 있으며 $n'(16m'^2+1)=m'(9n'^2+8^2)$에 대입하여 정리하면 $b(16d^2a^2+1)=a(9d^2b^2+8^2)$이고 $a,b$는 서로소이므로 $a \mid 16d^2b^2+1, \; b \mid 9d^2b^2+64$를 만족한다.

위 결과에 따라 $a \mid 16d^2b^2+1$이므로 1이 $a$의 배수가 되어야 한다.

$b \mid 9d^2b^2+64$이므로 64 $b$의 배수여야 하는데 $n'$이 홀수임에 따라 $b$도 홀수가 되어 $b=1$

$b(16d^2a^2+1)=a(9d^2b^2+8^2)$에 $a,b$를 대입하여 정리하면 $7d^2=63$으로 $d=3$

$m'=3, n'=3$이므로 $m=4m', n=3n'$에 대입하여 $m=12,n=9$임을 알 수 있다.

$mn=12 \cdot 9 = 108$

작성에 도움이 된 자료

  • KMO 수학경시 정수론, 장환수학, 임장환 저
  • 진산수학서당, 네이버 블로그


읽기 전

  • 작성자가 공부하고 있는 교재와 해석에 따라 보완될 여지가 있습니다.
  • 어디까지나 복습을 위해 정리하는 글이니 오개념이 있을 수 있으며 이를 바로잡기 위한 지적은 매우 감사히 받겠습니다.
  • 공부하고 있는 교재에 따라 정리할 지 난이도에 따라 정리할 지 고민 중입니다. ;ㅅ;
  • 수학 블로그가 아니기 때문에 다루는 내용의 카테고리가 일치하지 않을 수 있습니다.

자연수의 정렬원리(Well-ordering Principle)

자연수 정렬성의 증명은 현재 다루고 있는 초등해석학 수준에선 어렵기 때문에 공리로써 받아들이려 한다.

자연수 집합 $N$의 부분집합 $S$가(공집합(∅) 제외) 주어지면 그 집합 안에서 항상 최소원소를 찾을 수 있다. 즉, $S \subset N$이고 공집합이 아니면 집합 S는 최소값을 가진다.

$$
\exists \;a\in S \;\ s.t \;\ a\le b,\;\ \forall\ b \in S
$$

아르키메디안 성질 증명

  • 임의의 자연수 $a,b$가 있으면 $na \ge b$를 만족하는 자연수 n이 존재한다

위 개념이 아르키메디안 성질이다. 자연수의 정렬성을 활용한 아르키메디안 성질 증명과정은 다음과 같다.

우선 위의 정의가 성립하지 않는다고 가정하자. 어떤 자연수 $a,b$가 존재하여 모든 자연수 $n$에 대해 $na < b$를 만족한다고 할 때 모든 자연수 $n$에 대하여 $0<b-na$이므로 $b-na$는 자연수가 된다. 따라서 자연수 $b-na$를 원소로 갖는 공집합이 아닌 집합 S가 존재하게 된다.
$$
S = {b-na \;\ | \;\ n \in N }
$$
$S \subset N$이므로 자연수의 정렬원리에 따라 집합 $S$에는 최소원소가 존재한다. 그리고 그 최소원소를 $b-ma$라 가정하자. 그런데 집합 $S$의 정의에 따라 $b-(m+1)a \in S$또한 성립하는데 앞서 $b-ma$가 최소원소라고 가정했음에도 $b-(m+1)a < b-ma$인 관계 또한 성립되므로 모순이 된다. 그러므로 집합 $S$는 자연수의 부분집합임에도 최소원소가 존재하지 않음을 의미하고 자연수의 정렬성에 위배된다. 아르키메디안 성질을 부정했을 때 부정할 수 없음이 증명되었음을 확인할 수 있다.

수학적 귀납법

수학적 귀납법은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법 중 하나로 그 바탕에는 자연수의 정렬원리가 있다. 수학적 귀납법을 표현하면 아래와 같다.
$$
S \subset N인\;집합\;S가\;다음\;두\;조건을\;만족하면\;S=N이다.\\
1)\; 1 \in S\qquad 2)\;k \in S \implies k+1 \in S
$$
위 전제를 증명하기 위해 1,2번 조건은 충족하지만 결론이 $S \neq N$라고 가정한 뒤 공집합이 아닌 $N-S$를 집합 $T$라고 두자. 자연수의 정렬원리에 따라 집합 $T$는 자연수인 최소원소 $x$를 가져야 하고 1번 조건에 따라 $1<x$와 $0<x-1<x$가 성립한다. 앞에서 $x$가 집합 $T$의 최소원소임을 확인했으므로 자연수 $x-1$은 집합 $S$의 원소여야 한다. 그런데 2번 조건에 따라 $x-1 \in S$일 때 $x \in S$이므로 $x \in T, x \in S$가 됨에 따라 $S \ne N$이라는 가정에 모순되므로 $S=N$이 성립한다.

위의 증명을 응용하면 $S$의 원소인 임의의 자연수 $a$에 대해 2번 조건을 만족하면 적어도 $S$는 $N-\{1,2,\;\dots,\;a-1\}$임을 알 수 있다.

예제

  • 모든 자연수 $n$에 대해 $n^5-n$이 5의 배수임을 증명하여라.

    $n^5-n$이 5의 배수가 되는 자연수 $n$의 집합을 $S$라 가정하자.

    1. $n=1$이면 $1^5-1=0$으로 5의 배수다.

    2. $n=k$일 때 성립한다고 가정하여 $(k^5-k) \; mod\ 5 = 0$이라고 하면

      $(k+1)^5-(k+1)=(k^5+5k^4+10k^3+10k^2+5k+1)-(k+1)$

      ​ $= (k^5-k)+5(k^4+2k^3+2k^2+k)$가 되어 5의 배수이다.

    (1), (2)번에 의해 수학적 귀납법으로 증명되었음을 확인할 수 있다.

자연수의 거듭제곱의 합

기호 $\sum$의 정의

$\sum_{k=1}^n a_k=a_1+a_2+\dots+a_n$

기호 $\sum$의 성질

  1. $\sum_{k=1}^n(a_k \pm b_k)=\sum_{k=1}^n a_k \pm \sum_{k=1}^n b_k$
  2. $\sum_{k=1}^n ca_k = c\sum_{k=1}^n a_k$
  3. $\sum_{k=1}^n c = cn$

자연수의 거듭제곱의 합

  1. $\sum_{k=1}^n k = 1+2+\dots+n=\dfrac{n(n+1)}{2}$
  2. $\sum_{k=1}^n k^2=1^2+2^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}$
  3. $\sum_{k=1}^n k^3 = 1^3+2^3+\dots+n^3 = \{\dfrac{n(n+1)}{2}\}^2$

작성에 도움이 된 자료

  • KMO 수학경시 정수론, 장환수학, 임장환 저
  • 위키피디아


+ Recent posts