스터디룸

나눗셈 알고리즘(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 수학경시 정수론, 장환수학, 임장환 저

자연수 $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 수학경시 정수론, 장환수학, 임장환 저
• 위키피디아

읽기 전..

• 향후 상기한 제목으로 작성될 게시물은 모두 Geeks for Geeks Algorithms 페이지들을 번역 및 작성자의 해석대로 정리할 예정입니다.
• 정확한 이론 베이스는 당연히 없고 학습한 내용을 정리할 목적으로 가볍게 작성하였기 때문에 오개념이 있을 수 있으니 혹시 페이지를 방문하신 분들께서는 참고바랍니다.
• 개념을 바로잡기 위한 지적은 언제나 환영이니 부탁드립니다.

Asymptotic Notations(점근적 표기법)

점근적 분석으로 도출된 알고리즘의 복잡도를 표현하기 위해 Θ(세타), Ω(오메가), $O$(빅 오) 3가지 표기법이 있다.

1. Θ Notation

   

   Theta 표기법은 분석하고자 하는 함수를 상계과 하계로 종속시킨다. 위 그래프처럼 함수 $f(n)$을 분석한다고 가정해보자.

   Theta 표기를 가장 간단히 하는 방법은 가장 높은 차수의 변수만 남기고 모두 버린 뒤 해당 변수의 계수도 1로 바꾸면 된다. 이를 테면 $f(n)=3n^3+6n^2+6000$의 Theta 표기법은 $3n^3$이하 변수를 모두 탈락시킨 뒤 계수를 모두 버린 $n^3$이 되므로 완성된 Theta 표기법은 Θ($n^3$)​이다. 가장 높은 차수만을 남기는 이유는 Θ($n^3$)이 Θ($n^2$)보다 커지는 $n_0$지점이 반드시 존재하므로 Θ($n^2$)의 계수가 얼마나 크건 상관없이 누락해도 무방하기 때문이다.

   이를 정리하면 Θ$(g(n))$은 $n_0$이후의 모든 $n$에 대해 $0 \leq c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)$를 만족시킬 수 있는 $c_1, c_2, n_0$이 존재하는 모든 함수 $f(n)$의 집합을 의미한다. 즉, $f(n)$이 Θ($g(n)$)에 속한다면 $n \geq n_0$을 만족하는 모든 $n$값에 대해 $f(n)$값은 항상 $c_1 \cdot g(n)$과 $c_2 \cdot g(n)$ 사이에 존재하기 때문에 Θ표기법은 주어진 알고리즘이 아무리 좋거나 나빠지더라도 비교하는 함수 범위 안에 있음을 의미한다.

   참고사항으로 위 정의에 따라 Theta 표기법 상 $n_0 \leq n$을 만족하는 모든 $n$에 대해 $f(n)$값은 반드시 $f(n_0)$보다 커야한다.

2. Big O Notation

   

   Big O 표기법은 알고리즘의 상계만을 다룬다. 예를 들어 Insertion 정렬의 경우 최상의 경우에 $n$만큼의 시간이 소요되고 최악의 경우 $n^2$만큼 소요되는데 이를 Big O 표기법으로 나타내면 $O(n^2)$이다. 그리고 Big O 표기법에 따라 최상의 경우($n$시간 소요)도 포함한다. 얼핏 Θ표기법과 차이점이 없어보이지만 Θ표기법은 최상의 경우[Θ($n$)]와 최악의 경우[Θ($n^2$)]를 따로 표기해야 한다.

   하계에 대해 고려할 필요가 없기 때문에 상계에 대한 정보만 가지고 있을 때 유용하게 사용할 수 있다. 그리고 많은 알고리즘들은 단순하게 상계에 대해 파악할 수 있기 때문에 일반적인 시간복잡도를 논할 땐 Big O 표기법을 사용한다.

   이를 정리하면 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq f(n) \leq c \cdot g(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 $O(g(n))$이라 표현할 수 있으므로 Big O 표기법은 주어진 알고리즘 $f(n)$이 아무리 나빠도 비교하는 함수 $c \cdot g(n)$보다는 같거나 좋음을 나타낸다.

3. Ω Notation

   Big O 표기법이 점근적 상계에 대한 정보만을 제공했다면 Ω표기법은 점근적 하계만을 다룬다. 그러나 점근적 하계는 최상의 케이스를 의미하므로 일반적으로 잘 쓰이지 않는다.

   

   Ω($g(n))$)은 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq c \cdot g(n) \leq f(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 의미하므로 Ω 표기법은 주어진 알고리즘 $f(n)$이 아무리 좋아도 비교하는 함수 $c \cdot g(n)$보다는 같거나 나쁨을 나타낸다.

   예를 들어, 위에서 기술하였듯이 Insertion Sort의 시간 복잡도는 최악의 경우 $n^2$이고 최상의 경우 $n$이므로 Ω 표기법으로 나타내면 Ω(n)이 된다. 하지만 우리는 알고리즘의 평균적인 상황이나 최악의 상황에서의 성능을 요구하기에 그닥 쓸모있는 정보를 제공하진 않는다.

알고리즘 문제를 해결하는 상황에선 보통 Big case를 주는 경우가 많기에 worst case를 고려하지 않으면 TLE(Time Limit Exceeded)문제가 발생한다. 그리고 input의 공간적 분포를 따졌을 때 대다수는 average case이므로 사용하고자 하는 알고리즘의 시간복잡도를 잘 따져봐야 한다.

반대로 Small case가 주어졌지만 수행시간도 극단적으로 짧게 제공된다면 asymptotic 관점에서는 느리지만 실제로는 더 빠른 알고리즘을 사용하는 융통성이 필요할지도 모르겠다. 주어진 input이 n_0보다 작다던지...

게시물 출처: Analysis of Algorithms | Set 3 (Asymptotic Notations)