Processing math: 9%

선형 디오판토스 방정식

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

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

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

해가 존재하는 지 증명

S=ax+by | x,yZ라 정의하고 집합 S가 다음 세개의 성질을 만족함을 증명하자.

  1. a,b S

    a=a1+b0S, b=a0+b1S

  2. uSutS, tZ

    uS이면  x1,y1Z s.t.u=ax1+by1이며 ut=t(ax1+by1)=a(tx1)+b(ty1)S

  3. u1,u2Su1±u2S

    u1,u2S라 하면 u1=ax1+by1, u2=ax2+by2를 만족하는 정수 x1,x2,y1,y2가 존재한다.

    u1±u2=ax1+by1± (ax2+by2)=a(x1±x2)+b(y1±y2)S

따라서 a=bq+r, 0r<b에 대하여 a,bS이므로 abq=rS이다. r=0인 경우 gcd(a,b)=b이고 r0이면 b=rq1+r1, 0r1<r로 표현할 수 있고 b,rS이므로 r1=brq1이 되어 S의 원소가 된다. 이를 마지막까지 반복하면 rn=gcd(a,b)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)가 임의의 해라고 가정하면 ax0+by0=ax+by이고 이를 정리하면 a(xx0)=b(yy0)이다. 여기서 양변을 gcd(a,b)=d로 나누면 ad(xx0)=bd(yy0)인데 gcd(ad,bd)=1이므로 ad|yy0이다. 따라서 적당한 정수 kx에 대해 정리하면 adkx=(yy0)이고 정리하면 y=y0adkx이다. 마찬가지로 x에 대해 정리하면 x=x0+bdky를 얻는다. 따라서 d=gcd(a,b)이므로 ax+by=c의 정수해 (x,y)는 특수해 x0,y0에 대해 [(x0+bdk,y0adk),kZ]로 표현할 수 있다.

확장 유클리드 호제법

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

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

a=bq+r2

b=r2q2+r3

r2=r3q3+r4

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

rn+2=rnrn+1qn+2, axn+byn=rn

=axn+byn(axn+1+byn+1)qn+2

=a(xnxn+1qn+2)+b(ynyn+1qn+2)

(xn+2,yn+2)=(xnxn+1qn+2,ynyn+1qn+2)

위와 같이 점화식을 도출하였고 유클리드 호제법의 결과에 따라 gcd(a,b)=rn+2라 하자. 그리고 점화식의 초항이 필요한데 유클리드 호제법의 전개식을 보면 a와 b에 대해서도 r과 같이 해석할 수 있으므로 r0=a, r1=b라 하면 a=ax0+by0에서 (x0,y0)=(1,0)이고 b=ax1+by1에서 (x1,y1)=(0,1)이다. x, y에 대해 점화식과 초항을 구하였으므로 차례대로 계산하면 된다. 아래 예시를 구해보자.

예제

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

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

710=6810+30

68=302+8

30=83+6

8=61+2

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

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

2=862=86

=48306=3083

=6843098=68302

=710(9)+689430=7106810

정수해가 구해졌으므로 위의 베주항등식의 일반해에 대입하면 다른 해를 구할 수 있다. 위에서 구한 일반해에 대입하면 (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=1ax_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_20\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_1d_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_2d_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|bgcd(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+73n^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+73n^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의 약수가 아닌 것의 개수를 구하여라.

n2^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이 된다.

여기서 48113\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^23a-186203b-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가 존재한다면 da의 약수라 부른다. 그리고 ad의 배수이다. 이 경우 ad의 관계는 d \mid a로 표기한다.

참고사항

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

  1. 2 \mid a(a+1)

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

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

    a3k,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)23의 공배수가 되어 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를 만족하면 da,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이므로 dr_1-r_2의 약수임이 확인되었는데 피제수인 r_1-r_2d보다 작다는 건 모순되므로 r_1-r_2=0가 되어 a,bd로 나누었을 때 나머지는 같다.

같은 방법으로 c,b에 대해서도 똑같이 증명이 가능하므로 b,cd로 나누었을 때의 나머지도 같음을 알 수 있다. 그리고 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,ck로 나누었을 때 나머지 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임을 증명하여라.

소수 pp \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이 아닌 소수 pp \mid a+b이고 p \mid ab이려면 p \mid a, \; p \mid b를 모두 만족해야 하기 때문이다.)

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

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

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

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+na의 배수], [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<x0<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번 조건을 만족하면 적어도 SN-\{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