Loading [MathJax]/jax/output/CommonHTML/jax.js

선형 디오판토스 방정식

간단히 말하면 부정방정식 중 정수해만을 구하는 방정식을 말한다. 디오판토스 방정식에는 여러 형태가 있지만 유클리드 호제법과 베주 항등식에 나오는 식과 유사한 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=9, y=94

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

정리: a,bN에 대하여, gcd(a,b)=1x,yZs.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,bN에 대해 gcd(a,b)=dgcd(ad,bd)=1

정리: a,m,nN라 하면, gcd(a,mn)=1gcd(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이라 하자. 그럼 ax0+my0=1ax1+ny1=1을 만족시키는 정수 x0,x1,y0,y1이 존재한다.

1=ax0+my0(ax1+ny1)=ax0+amx1y0+mny0y1

=a(x0+mx1y0)+mn(y0y1)=1

gcd(a,mn)=1

정리: a,b,SN이라 하자. 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=baz=abz가 되어 ab|S를 만족한다.

작성에 도움이 된 자료

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


나눗셈 알고리즘(Division Algorithm)

aZ, bN이면 a=bq+r, 0r<|b|를 만족시키는 정수 q와 r이 유일하게 존재한다.

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

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

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

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

a=bq+r(0r<b)를 만족하는 정수 q와 r이 존재함을 증명하였다. 이 정수들의 유일성을 증명하기 위해 정수 q1,q20r1,r2<b를 만족하는 정수 r1,r2에 대해 a=bq1+r1=bq2+r2를 만족한다고 하자. 정수 q와 r에 대해 정리하면 b(q1q2)=r2r1이 되고 이 때 r2r1의 범위는 b<r2r1<b이다. (∵ 0r1,r2<b이기 때문)

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

유클리드 호제법(Euclidean Algorithm)

gcd(a,b)=gcd(b,r)==gcd(rn1,rn)=rn

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

d1=gcd(a,b),d2=gcd(b,r)이라고 하자.

  1. d1|a,d1|bd1|bq+r, d1|bd1|r이므로 d1|d2

    d1이 r의 약수이므로 b와 r의 공약수가되는데 b와 r의 최대공약수는 d2이므로 d1d2의 약수이다.

  2. d2|b,d2|rd2|b, d2|abqd2|a이므로 d2|d1

    d2가 a의 약수이므로 a와 b의 공약수가 되는데 a와 b의 최대공약수는 d1이므로 d2d1의 약수이다.

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

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

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

만약 r=0이면 gcd(a,b)=b가 되고 r0이면 b=rq1+r1,(0r1<r)을 만족하는 정수 q1,r1이 유일하게 존재한다. 그리고 앞에서 말한 것과 비슷하게 r1=0이면 gcd(a,b)=gcd(b,r)=r을 만족한다.

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

r=r1q2+r2,(0r2<r1)

rn1=rnqn+1

결론적으로 gcd(a,b)=gcd(b,r)==gcd(rn1,rn)=rn이 된다.

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

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

a,b,qZ이라고 하면 다음의 성질들이 성립한다.

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

  2. gcd(a,b)=gcd(a,b±qa)

    d1=gcd(a,b), d2=gcd(a,b±qa)라 하자

    • d1|a, d1|bd1|b±qa, d1|a인데 gcd(a,b±qa)=d2이므로 d1|d2
    • d2|a, d2|b±qad2|a, d2|b인데 gcd(a,b)=d1이므로 d2|d1

    따라서 d1=d2이므로 gcd(a,b)=gcd(a,b±qa)이다.

  3. gcd(a,1)=1

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

    gcd(a,b)=d1, gcd(ac,b)=d2라 하자

    • d1|a, d1|bd1|ac, d1|b인데 gcd(ac,b)=d2이므로 d1|d2
    • d2|ac, d2|bgcd(b,c)=1이므로 d2|a, d2|b에 따라 d2|d1

    따라서 d1=d2이므로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,yZ)라 정의하면 집합 S는 자연수의 부분집합이고 S가 공집합이 아님을 확인하면 자연수의 정렬성에 따라 최소원소를 가진다.

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

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

xqd=as+btq(ak+bl)=a(sqk)+b(tql)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=ae, b=be라고 표현할 수 있고 앞서 d=ak+bl=aek+bel로 표현할 수 있어 d는 e의 배수이다. 즉, 임의의 a와 b의 공약수는 모두 d의 약수이므로 gcd(a,b)=d가 성립한다.

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

  1. gcd(a,b)=gcd(a,b±qa)

    gcd(a,b)=d1, gcd(a,b±qa)=d2라 하면 베주 항등식에 따라 d1|b±qa이고 d2가 최대공약수이므로 d1|d2이다. d2에 대해서도 d2|b±qaqa=b이고 gcd(a,b)=d1이므로 d1=d2

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

    gcd(a,b)=d1, gcd(ac,b)=d2라 하고 베주 항등식에 따라 d1=ax1+by1, d2=acx2+by2인 정수 x1,y1,x2,y2가 존재한다고 하자. 그리고 gcd(b,c)=1에 따라 정수 x,y에 대해 cx+by=1이라고 가정한 뒤 양변에 d1을 곱하여 정리하면d1=d1cx+d1by이 된다. 우변의 x의 계수를 ac로 맞추기 위해 앞서 정의한 d1을 대입하면 (ax1+by1)cx+d1by=ac(x1x)+b(cy1x+d1y)=d1이 되어 d2|d1이 성립한다.

    마찬가지로 cx+by=1 양변에 d2를 곱하면 d2=cd2x+bd2y가 되고 앞서 했듯이 계수 ac를 만들기 위해 우변에 대입하면 c(acx2+by2)x+bd2y=d2이고 d1의 꼴로 바꾸면 a(c2x2x)+b(cxy2+d2y)=d2가 되어 d1|d2가 성립한다.

예제

n3+2nn4+3n2+1가 모든 정수 n에 대하여 기약분수임을 보여라.

유클리드 호제법 계산 1

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

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

유클리드 호제법 계산 2

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

aN일 때, gcd(a7+1,a3+1)=a+1임을 증명하라.

유클리드 호제법 계산 3

따라서, a7+1=(a4a)(a3+1)+(a+1)이고 a3+1=(a2a+1)(a+1)gcd(a7+1,a3+1)=a+1이다.

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

예를 들어 k=1,111 ... 111,111 (1이 18개)를 a로 나눠보자. 그럼 k=102a(100+108(21))+11이 될 것이다. 즉 18=82+2이고 피제수와 몫 그리고 나머지를 각각 s, q, r이라 하면 k=10ra(1+10s++108(q1))+1111 (1이 r개) 꼴로 나타날 것이다.

마찬가지로 2020=8252+4이므로 b=104a(1++108251)+1111이 되어 gcd(a,b)=gcd(a,1111)이다. 즉 최대공약수는 1111이다.

n3+73n2+3n+1이 서로소가 아님을 만족하는 양의 정수 n 중 가장 작은 값을 구하여라.

gcd(n3+7,3n2+3n+1)=gcd(3n3+3n2+n(3n3+21),3n2+3n+1)

=gcd(3n2+n21,3n2+3n+1)=gcd(3n2+n21,3n2+3n+1(3n2+n21))

=gcd(3n2+n21,2n+22)=gcd(3n2+n213n(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값이 존재한다.

따라서, n3+73n2+3n+1이 서로소가 아님을 만족하는 가장 작은 양의 정수 n은 320이다.

520002499925, 5200224100025, 5200424100125의 최대공약수를 구하여라.

세 수의 최대공약수를 d라 하면 각각에 대해 da, db, dc로 표현할 수 있다. 그리고 gcd(da,db,dc)=gcd(d(cb),d(ba))이므로 대입하여 정리하면 gcd(52002(251)24,52000(251)24)이므로 24gcd(520021,520001)을 구하면 된다.

유클리드 호제법에 따라 gcd(5200215200025+25,520001)=gcd(520001,521)이고 두 제곱수의 차의 형태를 띠고 있으므로 좌항은 우항으로 인수분해가 된다. 따라서, gcd(520021,520001)=24이고 앞서 24를 따로 앞으로 옮겼기에 문제에서 제시된 세 수의 최대공약수는 242=576이다.

작성에 도움이 된 자료

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


자연수 n의 소인수 분해식을 n=pe11pe22pekk이라고 하면,

양의 정수 n의 약수개수는 r(n)=(e1+1)(e2+1)(ek+1)

n의 약수들의 총합은 σ(n)=(1+p1++pe11)(1+p2++pe22)(1+pk++pekk)

=(pe1+111p11)(pe2+121p21)(pek+1k1pk1)

예제

양의 정수 n=230315에 대해, n2의 양의 약수 중 n보다 작고 n의 약수가 아닌 것의 개수를 구하여라.

n223이라 생각해보자.

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

n2의 약수 중 n보다 작은 약수의 개수는 [61312]이고 여기서 n의 약수는 3116이므로 [61312](31161)=450

218+1의 양의 약수의 총합을 A라고 할 떄, [A1000]를 구하여라.

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

(2k2)2+22k2+122k2

=((2k2)+1)2(2k)2

=(2k2+2k+1)(2k22k+1)로 나타낼 수 있다.

다시 k를 대입하면 481545=13375109으로 14386110이 약수의 총합이 되어 [3511201000]=351이 된다.

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

k=26이라 했을 떄 k3+1로 나타낼 수 있고 이는 (k+1)(k2k+1)로 나타낼 수 있으므로 k+1=65=513임을 알 수 있다. 위에서 545가 5의 배수이나 13의 배수임이 아닌 것을 확인하였으므로 481은 13의 배수이다.

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

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

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

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

둘을 서로 빼면 A(ab)=2이므로 (A,(ab))=(1,2)or(2,1)이다.

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

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

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

양변에 nxy를 곱하여 정리하면 ny+nx=xy를 얻을 수 있고 우변으로 옮긴 후 n2을 더해 정리하면 (xn)(yn)=n2가 완성된다. n의 소인수 분해식이 n=pe11pe22pekk라고 했을 때, 문제의 조건에 따라 x,y>n이므로 n2의 약수에 대해 (x,y)가 한쌍씩 일대일 대응으로 성립한다. 따라서, 해의 개수는 γ(n2)=(2e1+1)(2e2+1)(2ek+1)이다.

318620=1a+1b를 만족시키는 양의 정수 a,b의 순서쌍 (a,b)의 개수를 구하여라.

18620을 A라 하자. 3A=1a+1b 에서 양변에 Aab를 곱한 후 정리하면 3abA(a+b)=0가 된다. 하지만 이 경우 두 수의 곱으로 표현할 수 없기 때문에 양변에 3을 곱하고 A2을 더한 뒤 인수분해를 하면 (3aA)(3bA)=A2의 식을 얻을 수 있다. 그리고 18620을 소인수분해하면 2257219이므로 (3a18620)(3b18620)=245274192이다.

18620을 3으로 나눈 나머지는 2이므로 3a186203b186201862021(mod 3)이다. 그러므로 18620을 두 수로 분할한 값은 각각 3으로 나눈 나머지가 1이어야 한다. 2452741923a186203b18620으로 분리했을 때 3으로 나눈 나머지가 1이어야 하므로 각 인수별로 3으로 나눈 나머지가 2가 되는 경우가 있는지 검사하여야 한다. 2232(mod 3), 52(mod 3), 22241(mod 3), 719521(mod 3) 이므로 2452를 분할하는 경우엔 3으로 나눈 나머지가 모두 2이거나 1이 되도록 묶어줘야 한다.

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

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

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

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

2999의 약수의 개수는 242=16이고 조건에 맞지 않는 약수는 2개에 k+2n+1보다 작아야 하므로 나타낼 수 있는 방법의 개수는 1622=7이다.

양의 정수 k에 대하여 ak=(2k)30131이라 하자. S=a1+a2++a10이라 할 때, S를 31로 나눈 나머지를 구하여라.

주어진 수식은 초항이 1이고 공비가 32인 등비급수의 합을 나타내는 수식으로 ak=(25)6k1321 과 같이 변형할 수 있다. 즉 ak=1+25++(25)6k1로 표현할 수 있고 각 항을 31로 나누면 ak311+1++1=6k(mod31)이다. 문제에서 주어진 S를 대입해서 나타내면 S316(1+2++10)(mod 31)=610112(mod 31)=20

작성에 도움이 된 자료

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


약수와 배수

a,dZ이고, d0이라고 가정했을 때, a=cd를 만족하는 어떤 정수 c가 존재한다면 da의 약수라 부른다. 그리고 ad의 배수이다. 이 경우 ad의 관계는 da로 표기한다.

참고사항

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

  1. 2a(a+1)

    a2k(kZ)이면 a(a+1))=2k(2k+1)로 성립, a2k+1이면 (2k+1)(2k+2)로 성립

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

    a3k,3k+1,3k+2(kZ)이면 a(a+1)(a+2)=3k(3k+1)(3k+2),(3k+1)(3k+2)(3k+3),(3k+2)(3k+3)(3k+4)로 성립

  3. 6a(a+1)(a+2)

    2a(a+1),3a(a+1)(a+2)이므로 a(a+1)(a+2)23의 공배수가 되어 6a(a+1)(a+2)가 성립

약수의 성질 - 연산

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

  • da,dbdax±by(x,yZ)

    a=md,b=nd(m,nZ)에 따라 ax±by=mdx±ndy=d(mx±ny)

  • da,dax±b(xZ)db

    a=md,(ax±b)=nd(m,nZ)에 따라 ±b=ndax=d(nmx)

  • ab,bcac

    b=am,c=bn(m,nZ)에 따라 c=amn

  • d1d=±1

    d11=dn(nZ)에 따라 |1|=|dn||d|

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

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

a,bZ에 대해 정수 d (d>0)da,db를 만족하고 ca,cb인 정수 c에 대해 cd를 만족하면 da,b의 최대공약수라 부르고 d=gcd(a,b)로 표기한다. 만약 d=1이라면 a,b는 서로소라 부른다.

예제

nZ에 대해 gcd(n!+1,(n+1)!+1)=1임을 증명하라

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

dn!dn!+1이므로 dn!+1n!=1이므로 d=1가 되어 gcd(n!+1,(n+1)!+1)=1이다.

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

a,b,c를 각각 m1d+r,m2d+r,m3d+r이라고 하면 ab=d(m1m2),cb=d(m3m2)가 되어 dab,dcb가 성립한다.

하지만, 만약 a=m1d+r1,b=m2d+r2가 되어 ab=d(m1m2)+(r1r2)라 한다면 dab이라는 전제에 따라 d(ab)d(m1m2)=r1r2이다. d<r1r2<d이므로 dr1r2의 약수임이 확인되었는데 피제수인 r1r2d보다 작다는 건 모순되므로 r1r2=0가 되어 a,bd로 나누었을 때 나머지는 같다.

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

kab,kcb를 만족해야 a,b,ck로 나누었을 때 나머지 r이 같고 그 역 또한 성립한다.

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

p, q는 서로 다른 소수이고 a, b는 정수라 하자. 이 경우 pab이면 pa 또는 pb이다.

  • pak이면 pa이다.
  • pa, qa이면 pqa이다.

예제

a,bN이고 gcd(a,b)=1이라 하자. 만약 d1이고 dab이면 다음 조건을 만족하는 소수 p가 존재한다.

  1. pab
  2. [pa 이고 pb] 또는 [pa이고 pb]이다.

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

p가 소수이고 gcd(a,b)=1이며 pab가 성립하므로 [pa 이고 pb] 또는 [pa이고 pb]가 성립한다.

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

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

(∵ 1이 아닌 소수 ppa+b이고 pab이려면 pa,pb를 모두 만족해야 하기 때문이다.)

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

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

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

Aa,Ab에서 A4a2+9b2로부터 A9b2여야 하므로 A9

Bb,Bb에서 B4a2+9b2로부터 B4a2여야 하므로 B4

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

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

m+n=d(m+n)=ak,mn=d2mn=a(a+1)이 되는데 gcd(a,a+1)=1,gcd(m,n)=1,gcd(m+n,mn)=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는 완전제곱수가 된다.

주어진 범위를 만족하는 완전제곱수는 112,122,132,142가 있다.

  • a가 121일 때

    m=11m1, n=11n1이라고 하면, m1n1=(112+1), 11|m1+n1

    112+1=122=261이므로 (m1,n1)=(1,122),(2,61)에 따라 m1+n1=123or63 중 11의 배수는 없다.

  • a가 144일 때

    m=12m1,n=12n1이라고 하면, m1n1=(122+1),12|m1+n1

    122+1=145=529이므로 (m1,n1)=(1,145),(5,29)에 따라 m1+n1=146or34 중 12의 배수는 없다

  • a가 169일 때

    m=13m1,n=13n1이라고 하면, m1n1=(132+1),13|m1+n1

    132+1=170=1017이므로 (m1,n1)=(1,170),(2,85),(5,34),(10,17)에 따라 m1+n1=171,87,39,27 중 39가 13의 배수이므로 m+n=13(39)=507

  • a가 196일 때

    m=14m1,n=14n1이라고 하면, m1n1=(142+1),14|m1+n1

    142+1=197=1197이므로 (m1,n1)=(1,197)에 따라 m1+n1=198은 14의 배수가 아니다.

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

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

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

43m(n2+82)이고 n이 홀수이므로 n2+82도 홀수가 되어 4m이다.

34n(m2+1)이고 3m2+1이므로 3n이다.

  • m=3k일 때 3(3k)2+1
  • m=3k+1일 때 3(3k)2+23k+1
  • m=3k+2일 때 3(3k)2+26k+4

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

다른 방법으로 gcd(m,n)=d라 할 때, m=da,n=dbgcd(a,b)=1로 표현할 수 있으며 n(16m2+1)=m(9n2+82)에 대입하여 정리하면 b(16d2a2+1)=a(9d2b2+82)이고 a,b는 서로소이므로 a16d2b2+1,b9d2b2+64를 만족한다.

위 결과에 따라 a16d2b2+1이므로 1이 a의 배수가 되어야 한다.

b9d2b2+64이므로 64 b의 배수여야 하는데 n이 홀수임에 따라 b도 홀수가 되어 b=1

b(16d2a2+1)=a(9d2b2+82)a,b를 대입하여 정리하면 7d2=63으로 d=3

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

mn=129=108

작성에 도움이 된 자료

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


읽기 전

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

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

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

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

aS s.t ab,  bS

아르키메디안 성질 증명

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

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

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

수학적 귀납법

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

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

예제

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

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

    1. n=1이면 151=0으로 5의 배수다.

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

      (k+1)5(k+1)=(k5+5k4+10k3+10k2+5k+1)(k+1)

      =(k5k)+5(k4+2k3+2k2+k)가 되어 5의 배수이다.

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

자연수의 거듭제곱의 합

기호 의 정의

nk=1ak=a1+a2++an

기호 의 성질

  1. nk=1(ak±bk)=nk=1ak±nk=1bk
  2. nk=1cak=cnk=1ak
  3. nk=1c=cn

자연수의 거듭제곱의 합

  1. nk=1k=1+2++n=n(n+1)2
  2. nk=1k2=12+22++n2=n(n+1)(2n+1)6
  3. nk=1k3=13+23++n3={n(n+1)2}2

작성에 도움이 된 자료

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


+ Recent posts