머리말 KAIST 수학문제연구회는한국수학올림피아드가처음탄생할무렵인 988년부터지금까지다양한영재교육프로그램을운영하거나적극적으로기여해왔습니다. 한국수학올림피아드통신강좌와계절학교등의교육프로그램, 대전 충남지역중학생영재수학교실, KAIST Cyber영재교육등이그예들입니다. 이

Transcription

1 hkmo 차시험대비 i 엠제곱 (M ) 실전수학올림피아드 80 고등학생중 / 고급풀이편 고봉균 KAIST 수학문제연구회

2 머리말 KAIST 수학문제연구회는한국수학올림피아드가처음탄생할무렵인 988년부터지금까지다양한영재교육프로그램을운영하거나적극적으로기여해왔습니다. 한국수학올림피아드통신강좌와계절학교등의교육프로그램, 대전 충남지역중학생영재수학교실, KAIST Cyber영재교육등이그예들입니다. 이런활동의결과들을수학잡지 MathLetter를통해담아내어왔으며, 수학경시준비를위한교재를따로만들어달라는요청에부응하여 003년에엠제곱 (M ) 수학올림피아드셈본중학생초급 / 중급 / 고급을펴내었습니다. 그후셈이의문제해결기법, 셈본고등학생초급,BalticWay 팀경시대회등출판활동이꾸준히이어졌고, 수학올림피아드기본학습을마쳤으나보다다양한실전문제들로 KMO 차시험을준비하는학생들을위해몇달전에중학생실전수학올림피아드문제집을만들어낸데이어이번에는고등학생들을위한실전문제집을펴내게되었습니다. 이책에는수론 / 대수 / 기하 / 조합의네분야별로, 또중급 / 고급의난이도로나뉘어, 총 80문항에이르는매우방대한분량의문제가마련되어있습니다. 각분야의중급은 KMO 고등부 차시험에서장려상이나동상정도를, 그리고각분야의고급은은상이나금상을목표로하는난이도로볼수있습니다. 많은문제를스스로풀어보며접하여본학생일수록안정적인실력을갖추게되고또한응용력도성장하게됩니다. 끈기있게도전하여힘든여정을겪으면서자신의능력에차차자신감을갖게될것입니다. 그러나, 모든문제를다풀고넘어가겠다고하는것은시간이아까운면이있으니, 어떤수준의문제가 70% 정도가풀리고있다면그수준은그것으로끝내고다음단계의수준으로넘어갈것을권합니다. 모든문제에는최대한원래의출전을밝히려고노력하였습니다. 원래의출전대신에그것을인용한중간출전을적어둔경우도있습니다. 이책에는문제의풀이와해답이실려있지않습니다. 책이지나치게두꺼워질것을우려하여과감히생략하였고, 대신에 xmo 까페 ( 의 `실전MO 풀이 ' 게시판에문제의풀이를게시하고있으니, 거기서찾아보시기바랍니다. 기본학습단계가아닌실전단계에서는, 몇몇문제가잘풀리지않더라도, 가능하면풀이를참고하지않고스스로풀어내겠다고마음먹고승부욕을불태우는것이꼭필요하다고생각합니다. 게시판에올려진풀이보다더멋진여러분만의풀이를찾아내어까페에서함께논의하기를기대해봅니다. 008 년 0 월, 책임편집자고봉균

3 차례 수론 5. 수론중급문제 수론고급문제 대수 89. 대수중급문제 대수고급문제 기하 기하중급문제 기하고급문제 조합 조합중급문제 조합고급문제 종합문제 종합중급문제 종합고급문제...446

4 4 차례 문제의풀이는 xmo 까페 ( 의 ` 실전 MO 풀이 ' 게시판에게시하고있습니다. xmo 까페로오시면그밖에도많은학습자료를찾을수있고, 여러회원들과온라인에서만나수학문제에대한의견 교환및질의응답도할수있습니다.

5 제 장 수론. 수론중급문제 은정수가아님을보여라.(n ) n + 증명 3 k 중 k 가최대인것을찾아서분모를통분하면분자는 3 의배수가아니게됨.. 3 n+ j 3n + 임을보여라. 증명귀납법. n =0일때3j3 성립. n일때성립가정하자. 3 n+ +=( 3n ) 3 + = ( 3n + )(( 3n ) 3n +) 임에서 3 j ( 3n ) 3n + 임만보이면 n + 일때도성립하게된다. (mod 3) 이므로 홀 (mod3). 따라서,( 3n ) 3n + ( ) ( ) + 0(mod3). 3. 모든자연수 n 에대하여 n = X djn Á(d) 임을보여라. (Euler's totient) 풀이 n = X djn Á(d) 임을보이자. k n 이라하자. 우선 c j n 인 c 에대하여 gcd(k; n) =c 인것 들의개수를알아보자.gcd(k; n) =c 이면 k c 와 n c 이서로소이고, 역으로 k가 c의배수이고 k c 와 n c 이서로소이면 gcd(k; n) =c 이다. k c n c 이므로 gcd(k; n) =c 인 k의개수는정확히 Á( n c ) 이된다. 한편각각의k에대하여 gcd(k; n) =c 라고하면 c j n 이다. 그러므로 n은각각의약수 c에대하여 Á( n c ) 을모두합한것과같게된다. 따라서 n = X Á( n c ) 이고 n c 을 d로치환하면 n = X Á(d) 이다. } cjn djn 4. X n n= s = Y p 풀이 µ p s 임을보여라 ( 단, s> 인실수 ). Y p X n n= s = + s + + () 3s µ µ n s = + s + µ + + s 3 s + + µ+ 5 3s s + () () 과 () 는각각절대수렴하며, 자연수 n은유일하게소인수분해되므로 () 의우변의괄호에서각각하나씩뽑는순열을생각해볼때하나의순열이존재해서그곱이 이다. 반대로 () 의우변의서로다 ns

6 6 수론 른모든순열에대해서그곱은서로다르며 (* 곱이같다면소인수분해의유일성에의해, 두순열은같은순열이된다.) 꼴이므로결국 () = () 이다. } ns 5. d =gcd(a; m) j b 일때, 방정식 ax b (mod m) 은정확히 d 개의 (mod m 에대하여 ) 서로다른해를가짐을보여라. 증명 a = da, m = dm, b = db 라하면, 위의잉여방정식은 Ax B (mod M) 과동치. A와 M은서로소이므로 mod M에대한A의잉여역수A 0 이존재하고, 양변에이것을곱하면 x A 0 B (mod M) 과동치가됨. 따라서, x는 mod M으로유일한해를갖고, 그럼 mod m으로는정확히 d개의서로다른해를가짐. 6. a, b, n 은자연수들이고, b 는 a n 의배수이다.(a +) b 이 a n+ 의배수임을증명하여라. ( 헝가리 93-) 증명 (a +) b 은 (a +) an 의인수를가지므로 b = a n 일때만보이면충분하다. n에대한귀납법으로풀자. 우선 n =0일때는 (a +) =a는 a 의배수이므로성립. n일때성립함을가정하고 n +일때를보자.(a +) an+ =((a +) an ) a =(m )(m a + + m +) 로인수분해되는데 (m := (a +) an ), m 은 a n 의배수이고 m (moda) 임에서 m a + + m =a 0(moda) 이므로확임되었다. 7. a, b, c, d 는정수들이다. 임의의두정수 m, n 에대해, ax + by = m 과 cx + dy = n 을만족하는두정수 x, y 를항상찾을수있다고한다. ad bc = 임을증명하여라. ( 헝가리 94-) 증명 ( 신한솔 ) m =일때 (a; b) =임을알수있다. a = b =0이면 0=m 이므로모순. 따라서 a =0이면 b 6= 0이다. m = a, n = c +일때ax + by = a, cx + dy = c +을만족하는 x, y가존재해야한다. a 6= 0일때ax + by = a 에서 a j by 이고 (a; b) =이므로 a j y 이다. 따라서 y = ak 라하면 x = bk 이고 cx + dy = c + 에대입하면 c cbk + adk = c +, k(ad bc) =이므로증명끝. a =0일때b6= 0이므로 y =0이고 cx + dy = c + 에서 cx = c +이므로 c j 이다. m =을대입하면 b j 이므로 jbj ==jcj, 즉 jbcj =이다. 따라서증명끝 8. 서로다른정수 a, b, c, d 에대해, 방정식 (x a)(x b)(x c)(x d) 4=0 이정수해 r 을갖는다고한다.4r = a + b + c + d 임을보여라. (Putnam 947-B5) 증명 (r a)(r b)(r c)(r d) =4이고 x, a, b, c, d 모두정수이므로 (r a); (r b); (r c); (r d) 는모두정수이고, a, b, c, d가서로다르므로이넷도서로다른정수이다. 곱하는순서를제외하면 4개의서로다른정수의곱으로표현하는방법은 4= ( ) () ( ) 가유일하다. 따라서 r a =,r b =, r c =,r d = 이고이를모두더하면 4r = a + b + c + d로우리가원하는결과를얻는다. 9. T =,T n+ = Tn T n +(n>0) 으로주어진수열이있다. n 6= m 이면항상 T n 과 T m 이서로소임을증명하여라. (Putnam 956-B6) 증명 m>n 이라고가정하자. 이제먼저수학적귀납법에의해서다음명제를증명하자. m>n 이면항상어떤수 A 에대해서 T m = A T n + 이다. T n+ = T n T n +=(T n )Tn+ 이므로 m = n + 일때성립한다. m = n + k 일때명제가성립한다고가정하면 T n+k = A T n + 이고 T n+k+ = T n+k (T n+k ) + = (A T n + )T n+k + = (A T n+k ) T n + 이므로준명제는수학적귀납법에의해항상성립한다. 이때 m, n 이어떻게주어져도 T m = AT n + 이므로 (T n ;T m )=(T n ;T m AT n )=(T n ; ) = 이되어 T n, T m 은항상서로소이다.

7 . 수론중급문제 7 0. 자연수 m 에대해,3 k 이 m 의약수인 k 의최대값을 f(m) 으로나타내기로하자. 임의의 n> 개의자연수의집합 M, 그원소 a; b M 에대해, f(a b) 의값은많아야 n 종류임을증명하여라. ( 스웨덴 968-4) 증명 M 에 mod 3 m 으로서로다른두원소가존재하는최소의 m 0 을생각. 거기서귀납법.. 정수계수의다항식이서로다른세정수점에서 또는 의값을가지면, 이다항식은정수근을가질수없음을보여라. ( 폴란드 차 -) 증명 f(x) =0,jf(a)j = 일때 jx aj jjf(x) f(a)j = 이므로 jx aj = jx bj = jx cj =. 즉, x a; x b; x c f ; g 이므로비둘기집의원리에의해 a, b, c 중어느둘은같고그럼모순.. n! 이하의자연수는 n 개이하의서로다른 n! 의약수의합으로나타낼수있음을보여라. ( 소련 968-9) 증명귀납법. n =일때는자명하고, n 일때잘성립한다고가정하면, m n! 일때m을 n으로나눗셈을하여 m = nq + r 라하면q (n )! 이므로 (n )! 의서로다른약수의합q = d + + d k 로나타낼수있고 (k n ), 그럼 m = nd + + nd k + r 도 r(< n) nd i 이므로 n! 의서로다른약수의합으로나타낸것이된다 (k + n). 3. n 을자연수라하자. n + 이 4 의배수일때 n 의모든양의약수들의합이 4 로나누어짐을보여라. (Putnam 969-B) 풀이 ( 서울과학고 3 년박정근 ) n = ab 라할때 ab + 0 (mod 4); ab (mod 4); a 가 의배수이거나 3 의배수이면 ab + 이 4 로나누어질수없다 (). ) a (mod ); a =k +; a =4k (k +)+; ) a (mod 8); 또 3 으로나누어지지않으므로 a (mod3); ) a (mod 4): 또 () 에서, 3 이소수이므로 a 와 4 가서로소임을알수있다. a (a + b) a + ab 0 (mod 4): a 와 4 가서로소이므로 a + b 0 (mod 4); 여기에서 a 6= b 이다. 왜냐하면 a = b 이면 a a + a + + (mod4) 이므로모순이다. 따라서, ab = n 이되는서로다른두약수 a, b 에대해서 a + b 가 4 의배수이므로 n 의모든양의약수의합도 4 의배수이다. } 4. 정수계수다항식 f(x) =x n + a x n + a x n + + a n x + a n 이서로다른네정수a, b, c, d에대해 f(a) =f(b) =f(c) =f(d) =5 를만족한다. 이때, f(k) =8을만족시키는정수 k는존재하지않음을보여라. ( 캐나다 970-0)

8 8 수론 증명 g(x) =f(x) 5 라하자. 그럼 g(a) =g(b) =g(c) =g(d) =0 이고, 이때 g(k) =3 인정수 k 가없음을보이면된다. 인수정리에의해 g(x) =(x a)(x b)(x c)(x d)q(x) 이고, g(x) 가정계수다항식이므로 q(x) 도정계수다항식이다. 만일 g(k) =3 이라면 (k a)(k b)(k c)(k d)q(k) =3 3 은소수이므로좌변의다섯인수중에절대값이 3 인것이하나, 나머지넷은모두절대값이 이다. 즉, (k a), (k b), (k c), (k d) 중적어도셋은 이고, 그럼그중둘은함께 이거나함께 로같다. 이것은 a, b, c, d 가모두다르다는데에모순. 따라서, 이런 k 는없다. 5. 보다큰정수 n 이소수일필요충분조건은 k n 을만족하는모든 k 에대해이항계수 n k 가 n 으로나누어지는것임을증명하여라. ( 폴란드 차 -3) 증명 n이소수일때이것이성립함은쉬움. n이합성수일때는, n j n (n )! k 는 k!(n k)! 이정수라는의미임에서 k를 n의한소인수로택하로택하면끝. 6. 에서 까지의수들을임의의순서로이어썼다. 이렇게얻어진 자리의수가 k 꼴의수가될수없음을보여라. ( 소련 970-3) 증명 mod 9. 자릿수가 i인것을9 i로바꾼것과서로짝지으면 ( 단,9와0은그대로냅두고 ), 짝이없는수들은 9와 0만으로된수들이니까뭐. 7. 자연수 x, y, z, n 이방정식 x n + y n = z n 을만족할때,min(x; y) n 임을증명하여라. ( 폴란드 97 3 차 -4) 증명 WLOG x y(< z). x n = z n y n =(z y)(z n + +y n ) >x n + +x n = nx n 8. r +3 n 을만족하는임의의자연수 n, r에대하여이항계수 n r ; n r+ ; n r+ ; n r+3 은등차수열의연속된네항이될수없음을증명하여라. ( 폴란드 974 3차-5) 증명네항을 a, b, c, d 라할때 d c = c b = b a 를그냥열심히풀면됨. 9. (a) 다음부등식을증명하여라. [5x]+[5y] [3x + y]+[3y + x] 단, x; y 0 이고,[u] 는 u 이하의가장큰정수를나타낸다 ( 예 :[ p ]=). (b) 임의의자연수 m과 n에대해 (5m)!(5n)! m! n!(3m + n)! (3n + m)! 증명 a 5 이정수임을증명하여라.(a) 를이용해도좋고이용하지않아도된다. ( 미국 975-) () 0 x y<일때만확인해도된다.[5x] =a, [5y] =b 라하자 (0 a b<5). 그럼 b+ y< 5. x< a+ 5, b 5 3a + b +3 우변 + 5 a +3b +3 0 a b 4 일때 f(a; b) 와 a + b 의값을표로구해비교해보자. 5 [ 표 ] 좀노가다 = f(a; b)

9 . 수론중급문제 9 어느경우에나항상 a + b쪽이더크거나같음을확인할수있다. () 임의의소인수 p에대해, p가분자에같거나더많이들어있음을보이면된다. 즉, 다음을보이면된다. X 5m i= p i + 5n p i X 3m + n i= p i + m +3n 이것은 () 에의해각각의 i 에대해좌변이더크므로성립한다. 0. 다음을만족하는양수 a, b 가존재하는지각각답하여라. () a; b = Q 이고 a b Q. () a; b; a b = Q. (3) a Q 이고 b; a b = Q. ( 유고슬라비아 979 고4-) 풀이 p p 가유리수일때, 무리수일때로나누어각각조금씩흔들거나하면됨. () 의예로는 ( p ) logp 3 같은것도있음. } p i. 다음방정식이무한히많은자연수해 (x; y; z) 를가짐을보여라. ( 폴란드 차 -) x + y + z =3xyz 증명 ( 박경태 ) 위의방정식을 x 3yzx+y +z =0와같이이차방정식으로바꿀수있다. 그러면어떤자연수해 x에대해서이는이차방정식이므로다른근 x 0 를가진다. x + x 0 =3yz이므로 x 0 =3yz x. 따라서 x y z라고할때,3yz x>z이므로 (x; y; z) 가이방정식의자연수해이면 (y; z; 3yz x) 도자연수해이다 (Vieta's jumping). 이러한방식으로 (x; y; z) =(; ; ) 부터시작하면무한히많은자연수해를가진다.. f n 은 f = f =,f n = f n + f n (n>) 로정의된피보나치수열이다. 모든자연수 n에대해 f n anb n 이 m으로나누어떨어지고 0 <a<m,0<b<m인정수들a, b, m은유일하게존재함을보여라. ( 영국 983-) 풀이 ( 고봉균 ) 조건을만족하는 a; b; m이존재한다고가정하면 n =; ; 3일때 m j ab; m j ab ;mj 3ab 3 () 이고, 우선 ab (modm) 이므로 (a; m) =; (b; m) = 이다. 또, m j ( ab) ( ab )=ab(b ) 이므로 m j b 이다. 이제 m j ( ab)+(b ) = b( a) 이므로 m j a 이고,0<a<m 이므로 ) a =; 그리고 () 은다음과같이쓸수있다. m j b; m j 4b ;mj 6b 3 () m 은홀수 b 를나누므로역시홀수이고, m j 6b 3 에서 m j 3b 3 이된다. 이제 m j ( 4b ) ( 3b 3 )=b (3b 4), 즉 m j 3b 4 이고, 또 m j (3b 4) 3( b) =5 이다.0<a<m 이므로 m =5 이고,0<b<m 과 m j b 에서 b =3 이다. 그러면, a =;b=3;m=5 이면조건이만족되는지보자. n =; 일때성립하고, n 3 일때는 5 j f n (n ) 3 n (3) 5 j f n (n ) 3 n (4) 5 j 3 n (5n +5) (5) (3) + (4) (5) 에서 5 j f n n 3 n ) a =;b=3;m=5일때유일하게존재. }

10 0 수론 3. p(p +)+q(q +)=n(n +) 을만족하는자연수순서쌍 (p; q; n) 을모두찾아라. 단, p와 q는소수여야한다. ( 오폴 983-) 풀이먼저 n p + q 일때는우변이커서해없음. n p + q 일때만보자. q(q +) 을우변으로넘겨인수분해하면 p(p +) =(n q)(n + q +). n q<p이므로 p j n + q +. 마찬가지로 q j n + p +. 즉, p; q j n + p + q + 이므로 p 6= q 라면 pq j n + p + q + p +q. 즉, pq p +q 이고 (p )(q ) 4. WLOG p<q라하고가능한경우를좀따져주면 p =일때q =,n =3 과 p =3일때q =5,n =6이해의전부. p = q 일때는p(p +)=n(n +) 임에서 n과 n +중에 p의배수가있고 n>p이므로 n p 인데그럼우변이커서해없음. } 별해 WLOG p q 라하고p(p +) 을우변으로넘기면 q(q +)=(n p)(n + p +). q j n p 이면 q n p, q +<n+ p +이므로우변이커서모순. 즉 q j n + p +. n + p +=qk 라하면 k =일때는좌변이크고 k 4 이면우변이크게되어 k =또는 3. k =일때 :3q 3=4p 이되어 p =3,q =5,n =6. k =3일때 :4q =3p +가되어p =,q =,n =3. } ny 4. 모든자연수 n에대해,( n+ )! 은 ( n+ i ) i 의배수임을증명하여라. ( 오폴 983-8a) i=0 증명 n =일때는3j3! 로자명. 귀납법으로, n일때성립가정. n+ n+ 은정수이므로 ( n+ ny )! j ( n+ )!. 따라서, 가정에의해 ( n+ i ) i+ j ( n+ )!. j = i +로치환하면좌 i=0 n+ Y 변은 ( n+ j ) j 가되고여기에j =0일때인 n+ 을양변에곱해주면증명끝. j= 5. 임의의소수 p 에대해, n n 이 p 의배수가되는자연수 n 이무한히많음을보여라. ( 캐나다 983-4) 증명우선 p =일때는n이짝수이면된다. p가홀수인소수일때를생각하자. 페르마의작은정리에서 p (modp) 이므로 n 은 mod p로주기p 을갖고, n는 mod p로주기p를갖는다. 즉, 두주기의공배수인 T = p(p ) 에대해 n+t (n + T ) n n (mod p) 이므로 f(n) = n n 은 mod p 로주기 T 를갖는다. (p ) (p ) =0 (modp) 이므로 f(n) 0(modp) 인 n 이있다. 그럼 mod p 로주기함수이므로 f(n) 0(modp) 인 n 이무한히많다. 6. 다음을만족하는자연수쌍 (n; k) 를모두구하여라. ( 호주 983-4) (n +) k =n! 풀이 n =; ; 3; 4 일때각각체크해보면 (n; k) =(; ); (; ); (4; ) 일때가능. n 5 일때를살펴보자. 우변이짝수이므로좌변도짝수가되려면 n은짝수, 즉 n =m, m 3. n! 에는, m, m이모두곱해져있으므로 n j n!. 즉, 좌변에서도 n j (n +) k 이어야한다. 이항정리로전개하여 차이하의항만살펴보면 n j kn 임을알수있으므로njk. 그럼 (n +) k (n +) n >n n >n! 로문제의방정식이성립할수없다. 답 (,), (,), (4,) } 7. 두홀수인합성수의합으로나타낼수없는가장큰짝수는무엇인가? (AIME 984-4) 풀이 6n +=9+(6n +3), 6n +38=35+(6n +3), 6n +8=5+(6n +3). (n ). 답 38 }

11 . 수론중급문제 8. 어떤자연수가 () 0인자리수를갖지않고 () 자리수의합의배수가된다면 이수가 ` 자리수로나누어진다 ' 고한다. 예를들어,3 는자리수로나누어진다. 자리수로나누어지는자연수는무한히많이있음을보여라. ( 캐나다 984-3) 증명 {z } 가모두자리수로나누어지는양의정수들이된다. 이수의자리수의합이 3 n 이므로, 3 n 개 이수가3 n 의배수임을수학적귀납법으로보이자. 우선 n =일때는3j 로쉽다. n = k 일때성립한다고가정하면 = {z } {z } 3 k+ 개 3 k 개 로 3 j 이므로이것은 3 k+ 의배수, 즉 n = k + 일때도성립한다. 따라서, 임의의양의정수 n 에대해이런수들이하나씩존재하므로, 자리수로나누어지는양의정수는무한히많다. 9. n 이 k 꼴일때에만 n 이 n! 를나눔을증명하여라. ( 캐나다 985-4) 증명 n! 을소인수분해했을때 p 의지수는다음과같다. f(n; p) = ¹ º ¹ º ¹ º n n n + p p + p 3 + 이문제는 f(n; ) n 이될동치조건이 n = k 꼴이라는것을증명하라는것과같다. 우선 n = k 꼴이면 f(n; ) = k + ++= k =n 로성립한다. n = k 꼴이아니면 k <n< k 인양의정수k가존재하고, 그럼수가아니므로 j n k j n k j n k j n k f(n; ) = k < n + n + n n k = n n <n k n k 이모두정 이된다. 즉, 문제가성립하고, n = k 꼴일때특히 n k n! 임을알수있다. nx 30. 자연수 n과 k에대해, F (n; k) = r k 로둔다. F (n; ) 이 F (n; k) 를나눔을증명하여라. r= ( 캐나다 986-4) 증명 F (n; ) = n = n(n+) 이므로 n(n +)j F (n; k) 임을보이면된다. F (n; k) =( k + n k )+( k +(n ) k )+ +(n k + k ) 에서각항 i k +(n i +) k 은 k 이홀수이므로 i +(n i +)=n + 로나누어떨어진다. 따라서,(n +)j F (n; k). F (n; k) =(+(n ) k )+( k +(n ) k )+ +((n ) k +)+n k 으로정리할수도있으므로, 같은방법으로 n j i k +(n i) k, n j n k 로 n j F (n; k). n + 과 n 은서로소이므로 n(n +)j F (n; k) 임이확인되었다.

12 수론 3. 자연수 m, n, r 이다음식을만족하면 m 은완전제곱수임을증명하여라. ( 남미 987-3) ( + p 3) r =+m + n p 3 증명 b 0 =, b =,b n+ =4b n b n 이라할때, m r = b r. 3. 이차식 x + p x + q =0과 x + p x + q =0의계수가정수이다. 이두식은정수가아닌공통해를가진다. p = p 이고, q = q 임을보여라. ( 통신강좌 988-B3) 풀이 x + p x + q =0:::() x + p x + q =0:::() 일반적으로 x + ax + b =0 의해는 x = a p a 4b 만약여기서 p a 4b = m (m은유리수 ) 라놓으면 a 4b = m 에서 a가짝수면m도짝수, a가홀수면m도홀수이므로 x = a m 에서 x는정수가된다. 즉, 유리수근을가지려면꼭정수가되어야한다. 그런데이방정식 (), () 는정수가아닌즉유리수가아닌공통근을가지므로이공통근은무리수나허수밖에되지않는다. 이공통근을 라놓으면 (p p )+q q =0에서 p = p, q = q. } 33. x 3 y 3 =xy +8 의모든정수해 (x; y) 를구하여라. ( 통신강좌 988-B4) 풀이 x 3 y 3 =(x y)(x + xy + y )=xy +8인데문제로부터 x 6= y이고 x y (mod ) 임을알수있으므로 jx yj 이다. 즉 jx + xy + y j jxy +4j이된다. x + xy + y xy +4와 x + xy + y xy 4로부터얻을수있는해는 (; 0); (0; ) 이다. } 34. x, y, z 는유리수이고 t = 3p 일때 x + yt + zt 으로표현되는수들을생각하자. 만약 x + yt + zt 6=0 이면다음식을만족하는유리수 u, v, w 가존재함을증명하여라. (x + yt + zt )(u + vt + wt )= ( 남미 988-5) 증명유리수 a, b, c에대해a + bt + ct =0이면 a = b = c =0임을먼저증명하고. 그담엔준식을 t에대한이차식으로전개한후연립방정식. 35. x ;:::;x n 은 n 개의정수이고 p 는 n 보다작은자연수이다. S = x + x + + x p T = x p+ + x p+ + + x n S = x + x x p+ T = x p+ + x p x n + x. S n = x n + x + x + + x n T n = x p + x p+ + + x n 이라하자. a; b f0; ; ; 3g 에대해, S i a (mod 4), T i b (mod 4) 인 i ( i n) 의개수를 m(a; b) 라하자. m(; 3) m(3; ) (mod 4) 일때, 또그때만 m(; ) 가짝수임을보여라. ( 아일랜드 988-B, 호주 988-6)

13 . 수론중급문제 3 증명 S i + T i 는 x i 를전부합한것이므로일정하고, N = x + x + + x n 이라할때4-N 이면 m(; 3) = m(3; ) = m(; ) = 0 이되어서문제없음. 4 j N 이면 S + S + + S n = pn 0 m() m(3) + m() (mod 4) 이므로, m() m(3) (mod 4) 와 m() 0(mod4) 가동치임이금방확인된다. 36. 연속한네정수의곱에 988 을더한것이완전제곱수일수없음을증명하여라. ( 오스트리아 988) 증명 mod 5 로끝. 37. m 이자연수일때 (m) 을 m 의 ( 양의 ) 약수의개수라하자. 조건 ( n ) >n 을만족하는자연수 n 이무한히많이있음을보여라. ( 통신강좌 989-C3) 풀이 ( ) = 4 >. ( b ) >b이면 ( b ) = (( b + )( b )) ( b ) > b 이므로 ( b +과 b 은차가 인홀수이므로서로소이고, 그럼 b 의약수들이 ( b ) 개, 또그약수들에 b +을각각곱한것이 ( b ) 개있고이들은모두서로다르다 ) b가만족하면 b도만족. 따라서, 무한히많은 n이조건을만족한다. } 38. n 이자연수일때, 어떤자연수 m 이존재하여 ( p +) n = p m + p m 을만족시킴을보여라. (IMO-LL 989, 홍콩출제 ) 풀이다음을만족하는자연수 an ; b n 이존재한다. ( + p ) n = p a n+ + b n+ = p a n + b n p n p (+ ) (an + b n ) = (a n +b n)+(a n + b p n) ) a n+ = a n +b n ; b n+ = a n + b n a n+ b n+ = (a n +b n ) (a n + b n ) ) a n b n =( ) n = a n +b n n 이짝수이면 n 이홀수이면 q q a n + a n = q q b n + b n = q q a n + b n = a n + b n p =(+ p ) n q q b n + a n = b n p +an =(+ p ) n } 39. n 을 0 진법으로나타낸자연수라한다. n 의각자리수들의곱이 n 0n 인모든 n 을구하여라. ( 한국 989-5) 풀이 (i) n이한자리수라하면 n 0n = n ) n n = 0 n = p 33 이므로정수해는없다.

14 4 수론 (ii) n이세자리이상의수라하고 n = a 0 +0a +0 a +0 3 a k a k (k = ; 0 5 a k 5 9) 라하면 a 0 a a k = n 0n = n(n ) 좌변은 a 0 a a k 5 9 k+ < 0 k+ 이고우변은 k +자리수이상이므로이식을만족하는자연수는없다. (iii) n을두자리수라하고 n = a +0b 5 a; b 5 9 라하면 (a +0b) 0(a +0b) = ab 00b(b ) + 0ab a(0 a) =ab + 00b(b ) + 9ab = a(0 a)+ a(0 a) =5 (a +5) < 5 이므로 b = 이때 9a =0a a + ) a +9a = 0 (a )(a +)=0 ) a = 구하는수는 n = 답 n = } 40. P (0) =, P (3) = 8 이고모든근이정수인정수계수의다항식 P 를모두찾아라. ( 북유럽 989-) 4. 풀이 P (x) =a(x b )(x b ) (x b n) 으로둘수있고, P (0) = ( ) n ab b b n =. 따라서 jaj = jb i j =. P (3) = a(3 b )(3 b ) (3 b n )= 7 에서 3 b i =or4이므로모두양수이고 a =. b i 들중인것이u개, 인것이v개라하면 u +v =7을만족하는음이아닌정수u, v에대해 P (x) =(x ) u (x +) v. 답 (x )(x +) 3,(x ) 3 (x +),(x ) 5 (x +), (x ) 7 } p 3 n + p n ++ 3p n p n + 이자연수인것과적당한자연수 m에대해n = m(m +3) 꼴인것이동치임을보여라. ( 아일랜드 989-9) 증명 ()) a = 3p n + p n +, b = 3p n p n + 라하면 a 3 + b 3 =n, ab =. 따라서, n = a 3 + b 3 =(a + b)((a + b) 3ab) =(a + b)((a + b) +3) 이고, 문제에서 m := a + b 가자연수라고했으므로 n = m(m +3) 꼴. (() 역시위와같이 a, b 를정의하면 m(m +3)=(a + b)((a + b) +3) 이됨. m 3 +3m 은단조증가하므로 a + b 일수밖에없음. 4. x, y, z 가 x 3 +3y 3 +9z 3 9xyz =0 를만족시키는유리수일때, x = y = z =0 임을보여라. ( 통신강좌 990-E7) 풀이 x, y, z의분모의최소공배수를식의양변에곱해도상관없으므로우리는 x, y, z를모두정수라고생각해도된다. x, y, z 을, 모두가 0은아닌주어진식의정수해라면, x, y, z 의최대공약수 d로각각의수를나눈, x = x d, y = y d, z = z 도역시이식의해가되며, 이때이들의최대공약수 d 는 이된다. x 3 =9xyz 3y 3 9z 3 이므로 x는 3의배수이다. x =3u로치환하면, 식은, 다시 y 는 3 의배수이다. y =3v 로치환하면, 9u 3 + y 3 +3z 3 9uyz =0 3u 3 +9v 3 + z 3 9uvz =0 이때z는 3으로나뉜다. 이는 x, y, z의최대공약수가 이라는가정에모순이므로, x = y = z =0이유일한해이다. }

15 . 수론중급문제 n 이홀수이고 5 의배수가아닌자연수일때, n 의배수중에는모든자리수가 인것들이무한히많이있음을증명하여라. ( 통신강좌 ) 44. 풀이 n이홀수이고 5의배수가아니므로 gcd(0;n)=이다. 또한 gcd(0; 9) = 이므로 gcd(0; 9n) = 이다.Euler정리에의하면 0 Á(9n) (mod9n) 이다. Á(9n) =r 이라고놓자. r 6= 0임은자명하다. 모든양의정수 m에대하여 0 rm (mod9n) 이므로 0 rm 은 9n의배수들이고 0rm 9 는 n의배수들이다. 한편 0rm 은모든자리수가 이다. } 9 X k n gcd(k;n)= 풀이 k = n Á(n) 임을증명하여라. ( 통신강좌 990--) X k n gcd(k;n)= 을간단히 P 로표시하자. k n 인정수 k 에대하여 gcd(k; n) = 이면 gcd(n k; n) = 이고, 그역도성립함을쉽게알수있다. 그러므로 P fk +(n k)g = P n = ná(n) 이다. 그런데 P = P (n k) 임이자명하므로 P k = ná(n) 이다. } 45. ny k 가 nx k 로나누어지는 n을구하여라.( 단, Q 는곱의기호이다.) ( 한국 990-) k= k= 풀이 ny m = k ± X n k = n! n(n+) 가정수가되는자연수 n을구하면된다. k= k= (i) n가홀수일때 : n =k 이라하면 m = n! (n )! (n )! = 이고, k =일때m =; k > 이면 k<n 이므로은정수이다. nk k k (ii) n이짝수일때 : n =k라하면 (n )! m = n + : n +>n 이므로 n +이소수이면 m은정수가아니다. n +이합성수 이면이의약수는모두 n 보다작다. p를소수라하고 n +=ap m 이면 (n )! = (ap m )! 에는인수 p를 ap m 개포함하고, ap m m 이다. 따라서 (n )! 은 p m 로나누어진다. 이것은 n +의임의의소인수에대해 (n )! 서성립하므로 n +이합성수이면 n + 은정수이다. ( n 답이홀수일때 n이짝수이고 n +이합성수일때 } 46. k 90 인자연수 k 에대하여 f(k) = ( k ( k 45 일때 ) k 9 (46 k 90 일때 ) 으로정의하면 f : f; ;:::;90g!f; ;:::;90g 은전단사함수가된다. 이때 f 를 n 번합성한함수 f n 이항등함수가되는최소의자연수 n 을구하여라. ( 한국 990-4) 풀이 ¼ = µ 라하고, 단위원주를 (,0) 으로부터 9등분한점들을점 (,0) 을제외하고각각 µ; µ; ; 90µ 9 라한다. 5 k 5 90의각k에점kµ 를대응시키면 f(k) 는점kµ 에대응된다. 즉단위원주상에서각을 배로하는사상이다. 따라서 f n (k) 는 n kµ 에대응되고이것이항등사상이면 n kµ = kµ +9mµ(m은자연수 ) 인자연수 m이존재하면된다. ( n )k =9m 5 k 5 90이므로 n 이 9로나누어지는최소의자연수 n을구하면된다. 9 = 7 3이고 6 =63=7 9 = 4095 = 35 = 이므로최소의 n은 이다. 답 n = }

16 6 수론 주 p 가소수이면 p (modp) 이다. 이정리를이용하면 6 은 7 의배수이므로 = ( 6 )( 6 +) 도 7 의배수이고 은 3 의배수이므로 은 3 의최소공배수 9 의배수이다. 47. 음이아닌정수 n 에대해함수 f(n) 이다음과같이정의되어있다 : f(0) = 0, f() =, 그리고 m(m ) < n m(m+), m 인정수에대해 µ f(n) =f n µ m(m ) m(m +) f n f(n) =5 가되는최소의정수 n 을찾아라. ( 통신강좌 ) 풀이 f (n) =f (a) f (b) 라면, a + b = m (a ; b 0) 이고 n = m (m ) + a = (a + b)(a + b ) 이므로 a, b 가증가하면 n 도증가한다. 우선 f (0) = 0, f() =, f() = 0 이고 n 3 에서 n>a;b;m 이며, 또한 n 에대해 a, b, m 이유일하게결정되므로문제의정의는 f 를유일하게결정하는점화식이다. f (n) =i 를만족하는최소의 n 을 n i 라하자. 이 n i 를찾기위해서는최소의 a, b 를구해야하므로결국이 n i 들에대해서만생각하면된다. 먼저 n = 을쉽게얻고, f (n )= =0 =f() f() 이므로 n =5, 또 f (n )== ( ) = f (n ) f (n )=f() f (5), f (n )=f (n ) f() 으로 n =6,n =0 이다. 같이하여 n 3 =,n 3 =5,n 4 =646,n 4 = 650 을구할수있고, 5=4 ( ) = 3 ( ) = ( 3) = ( 4) 에서최소인것으로 n 5 = 658 이얻어진다. } + a 48. a, b, c 는서로다른자연수이고, a + b, a + c, b + c 는모두제곱수이다. a + b + c 의최소값을구하여라. (IMTS R4-) 풀이일반성을잃지않고 a<b<c라하고, a + b = x, a + c = y, b + c = z 이라하면 x<y<z 이고 x +y >z (). x +y +z =(a+b+c) 이므로 x, y, z는모두짝수이거나홀수가 개 (). () 과 () 를고려하며약간노동하여경우를따져보면 (x; y; z) =(5; 6; 7) 일때a + b + c =6+9+30=55 로최소. } 49. 각 A 는각 B 의두배이고각 C 는둔각이며, 세변의길이가모두정수인삼각형 ABC 가있다. 이삼각형의둘레의길이는최소얼마인가? ( 미국 99-) 풀이 sin 법칙과 cos 제법칙등을이용해 a = b(b + c) 임을먼저얻어내고,gcd(a; b; c) =일때만보면되는데그럼 b와 b + c가서로소이고각각제곱수 b = m, b + c = n, a = mn, c = n m. c >a + b 과 c<a+ b 에서 m p 3 <n<m. 여기서 m =; ; 3 일때는해가없고, m =4,n =7 일때a + b + c = mn + n =77이최소. 답 77 = } 50. 방정식 x pqx + p + q =0 이정수해를갖도록하는자연수 p, q 를모두구하여라. ( 러시아 99 4 차 -y0-) 풀이두근을a, b라하면a + b = pq, ab = p + q. 합과곱이둘다양이므로 a, b는둘다양수. 두식을빼면 (a )(b )+(p )(q ) =. 즉,(p )(q ). p, q가둘다3 이상이면부등식에위배되어해가없고, 둘중에하나가이나 일때를조사해보면 ( 좀노동 )(p; q) =(; ); (; 3); (3; ); (; 5); (5; ) 답 } 5. x 0 =0,x =, 그리고 n 0 에대해 x n+ =3x n+ x n 으로정의된수열에서, x n +n+ 은항상어떤홀수의완전제곱이됨을증명하여라. ( 오스트리아 ) 증명점화식을풀면 xn = n 임. 즉, x n +n+ =( n +). 5. a 0 =9,a k+ =3a 4 k +4a3 k (k 0) 으로주어진수열 a n이있다. a 0 을 0진법으로썼을때 000개보다많은 9를가짐을증명하여라. (Towns 99가을 JA4)

17 . 수론중급문제 7 증명 0 n j a n 임을보이자. 우선 n =0일때0 j a 0 + = 0 성립. n = k 일때성립하면, a k+ +=(a k +) (3a k ak +) 이므로 (0 k ) j a k+ + 로 k +일때도역시성립. 따라서, 0 04 j a 0 +이고 a 0 은마지막에 04개이상의9로끝난다. 53. 다음과같은조건을만족시키는자연수 p, q, n 을모두구하여라 :99 p 3 n+ 이고, q n + 은 p 의약수이다. ( 통신강좌 99-4-) 풀이 99 3 n+ 이고,3 6 =79,3 7 =87이므로 n 6이다. 또, q n + p 3 n+ 에서 3 n+ q n +>q n, 즉 (n +)log3> n log q이다. n 6에서 n + n > log q log 3 인데 q 이면우변이좌변보다커지게되어모순이므로 q =이다. q n + = j p에서 p =k꼴이고, 답은 (p; q; n) =(k; ;n) 이다. 단, n 6은임의의자연수이고, k는 996 k 3n+ 인자연수이다. } 54. 임의의자연수 n 에대해다음합을구하여라. ( 통신강좌 ) X n + k k+ = k=0 n + + n 풀이 자연수 n 의이진전개를 n = a m a a 0 () = mx a j j j=0 라하면 X n + k k+ k=0 = X k=0 n k+ + 3 mx a j j X j=0 = 6 k=0 4 k = k 3 X a j j X mx a 6 j j (k+) + a k + + j=0 k=0 4 k+ 7 j=k+ 5 = = 0 X a j j (k+) ak + + A k=0 j=k+ X mx X a j j (k+) + a k k=0 j=k+ k=0 = = = mx j X mx a j j (k+) + a j j= k=0 j=0 0 mx j X a k +A + a 0 j= k=0 mx mx a j ( j +)+a 0 = a j j = n j= j=0 이다. }

18 8 수론 55. 주어진 n 개의정수중임의의 n 개의곱과나머지한수의차가항상 n 으로나누어진다. 이때 n 개정수의제곱의합이 n 으로나누어짐을보여라. ( 통신강좌 ) 풀이 주어진 n 개의정수를 a,, a n 이라하자. 그러면 Q ai a j a j 0 (mod n) ) Y a i a j (mod n) 이므로 P a j n Q a i 0(modn) 이된다. } 56. x 4 + y 4 + z 4 =y z +x y +z x 3 을만족하는모든자연수근을구하여라. ( 통신강좌 ) 풀이 준식을변형하여 x 4 + y 4 + z 4 y z z x +x y = 4x y 3; (x + y z ) = 4x y 3; (x + y z ) (xy) = 3; (x + y + z)(x + y z)(x y + z)(x y z) = 3 를얻는데,(x + y + z) j 3이고 x + y + z 3이므로 x = y = z =이다. } 57. 정수수열 fu ng 이다음의조건을만족시킨다. u =; u 3n =0; u 3n = u n ; u 3n+ = u n + (n ) () u 99 를구하여라. () n이자연수이고 m =(3 n +) 3 일때, u m 을구하여라. (3) n 3 M (M은자연수 ) 인 n에대하여, u n =0인 n의개수를구하여라. ( 한국 99-3) 풀이 () u 99 = u = u 664 = u 3 + = u + = u =0+= () m =(3 n +) 3 =3 n+ f3 n +3 n +g + =3 n+ f3 n (3 n +)+g + 이므로 u m = u 3 n (3 n +)+ +=u 3 n + ++ = u 3n +++ 에서 n =이면 u 3 n + = u = u 3 =0이므로 u m = n = 이면 u 3 n = u =이므로 u m =4 즉 n =일때 u m =; n = 일때u m =4 (3) u 3n = u n ;u 3n =0이므로 u 3 k (3n ) =0 (k 0; n ) 인경우뿐이다. 3 k (3n ) 3 M 에서 k =0; ; ; ;M 이고이때 3n 3 M k ) 3n 3 M k + n 3 M k 이므로 k에대해서 n은 3 M k 개가있다. 따라서구하는가짓수는 M X k=0 M X 3 M k = k=0 3 k = 3M 3 = (3M ) } 주 u n 은 n 을 3 진법으로썼을때, 뒤에서부터찾아 가나타나기전까지의자릿수의합이다.

19 . 수론중급문제 ( + p 3) 5 를넘지않는최대의정수를구하여라. ( 한국 99-8) 풀이 ( + p 3) 5 +( p 3) 5 = 5X k=0 = f 5 + ³ 5 k 5 k ( p 3) k + 5X k=0 ³ 5 ³ g = ( ) = 74 ³ 5 k 5 k ( p 3) k 0 < p 3= + p 3 < 이므로 0 < ( p 3) 5 < 따라서 73 < ( + p h 3) 5 < 74 ) ( + p 3) 5i =73 } 59. (n 7 7) 이 9 의배수가되도록하는자연수 n 의최소값을구하여라. ( 한국 99-9) 풀이 n 7 7(mod9) 인최소의 n 을구하는문제이다.7 3 =343=9 8 + 이므로 7 3 (mod 9). 따라서 (n 7 ) 3 = n 7 3 (mod9).9 는소수이므로 n 9 = n 8 (mod9) ) n = n 3 n 8 n 3 (mod9) ) n 6 (mod9) 따라서 n 7 = n 6 n n 7 (mod 9). n =9m +7 인꼴이고최소값은 n =7 } 60. a ;a ;:::;a n 은서로다른자연수들이다 (n ). 다항식 f(x) =(x a )(x a ) (x a n) 이정수범위에서더이상인수분해되지않음을보여라. ( 북유럽 99-) 증명 f(x) =p(x)q(x) 로인수분해된다고하고 x = a i 들을대입하면 p(x i )q(x i )=. 즉 p(x i )+ q(x i )=0. 따라서, p(x)+q(x) 는 n 개의서로다른실근을갖는데, 이것은 n 차이하의식이므로모순. 6. 유리수좌표의두꼭지점을갖는삼각형이있다. 이삼각형의나머지한꼭지점도유리수좌표일동치조건은이삼각형의각내각의 tangent 값이유리수이거나직각일때임을증명하여라. ( 아일랜드 99-5) 증명 ()) 각변이 x- 축으로부터기울어진각은 tangent 값이유리수이거나직각. 그럼 tan(a b) = tan a tan b +tana tan b 의차각공식에의해두변이이루는각도 tangent 값이유리수이거나직각.(90± 가끼었을때조금조심스럽게서술해줄필요가있음 ) (() 두점 A, B 가유리수좌표이므로 AB 와 x- 축이이루는각의 tangent 값은유리수 ( 또는무한 ). 모든내각의 tangent 값이유리수 ( 또는무한 ) 이므로위에서처럼합각 / 차각공식에의해다른변도 x- 축과이루는각의 tangent 값은유리수 ( 또는무한 ). 유리수좌표의점으로부터유리수기울기를가지는두직선의교점이므로역시사칙연산에의해서만구할수있어서좌표는유리수.( 역시 90 ± 가끼었을때는조금조심스럽게서술해줄필요가있음 ) 6. n 3 이면 n! =d + d + + d n 을만족하는 n! 의서로다른 n 개의약수 d ;d ;:::;d n 이존재함을증명하여라. ( 이탈리아 99-3) 증명귀납법. 항상 d = 로하기로하고 (n +)d = d + nd 으로만분할해주면됨 a, b는자연수이다. p a + 3p b 가유리수면, a, b가모두세제곱수임을증명하여라. ( 이탈리아 99-6) 증명 3p a 3p ab + 3p b 도유리수이고, 그럼 3p 3p ab도유리수. a b, a + 3p ab + 3p b 이유리수이므로 3p a 3p b 도유리수. 그럼 3p 3p a, b 각각이유리수. 유리수의세제곱이정수이므로사실은정수의세제곱. 64. m +3 n 이완전제곱수가되는정수들의순서쌍 (m; n) 을모두찾아라. ( 인도 99-8)

20 0 수론 풀이 m, n이짝수임을 mod 3, mod 4로보이고그럼넘겨서인수분해하면두항의차이가 또는 가되어 또는 3 꼴이되는... } 65. n + 이홀수인소수가아니면, 또그때에만, 최초의 n 개의자연수의곱이최초의 n 개의자연수의합의배수가됨을증명하여라. ( 캐나다 99-) 증명 ( n) j n! 일필요충분조건이 n + 이홀수인소수가아님을보이라는문제이다. ( n) j n! () n(n +)j n! () n +j (n )! 이므로, n + 이홀수인소수이면이것은성립하지않는다. 이제 n + 이홀수인소수가아니면항상성립함을보이면된다. 우선 n +=k 로짝수이면 k n 이므로성립한다. 다음합성수중에서 보다큰서로다른두수의곱 n +=ab 로표현되는경우에는 a; b f; ;:::;n g 이므로역시성립한다. 합성수중에서이런곱으로표현할수없는것은 p 꼴 (p 는소수 ) 뿐이므로, 이제이런수들에대해서만보면된다. 홀수만보면되므로 p 3 이고, 그럼 p; p f; ;:::;n g 이므로역시성립한다. 그러므로, 모든양의정수 n 에대해문제가증명되었다. 66. 자연수 x, y, z 에대하여 f(x; y; z)=++3+ +(x + y ) z 라한다. f(a; b; c) =f(c; b; a) = 993 을만족시키는자연수 a, b, c, d 의모든짝을구하여라. ( 한국 993-7) (x + y )(x + y ) 풀이 f(x; y; z) = z f(a; b; c) =f(c; d; a) 에서 (a + b )(a + b ) c = (c + d )(c + d ) ) (a + b )(a + b ) + a = (c + d )(c + d ) + c ) (a + b ) +(a b +) = (c + d ) +(c d +) ) (a + b ) (c + d ) = (c d +) (a b +) ) (a + b + c + d )(a + b c d) = (c d a + b) (a c)(a + b + c + d ) = (d b)(a + b + c + d 3) M = a + b + c + d 라하면M = 4이고 (a c)(m ) = (d b)(m 3) b = d라가정하자.(b <d라가정해도되고, 이때 a>c) (M ) (M 3) = 이므로 M 과 M 3의최대공약수를 m라하면m =또는 m =이다. m =이면 d b 는 M 의배수이고, d b<m 이므로모순 m =이면 d b 는 M 의배수이고, a c 는 M 3 의배수이므로 4(a c)(d b) 는 (M )(M 3) 의배수이다. (M )(M 3) 4(a c)(d b) =(a + c b d) +4fa(b ) + b(a ) + c(d ) + d(c )g +3> 0 이므로모순따라서 b = d 이다. 이때 a = c 를얻는다. (a + b )(a + b ) a =993에서 (a + b )(a + b ) = a =3969< 3986 이므로 a + b =63이라하면 a = = 46 ) a =3;b=4 a + b =64이면 a = = 74 ) a =87;b<0 이므로버림 답 ½ a = c =3 b = d =4 a }

21 . 수론중급문제 67. 수열 x; x +; x+; x+3; ::: 에서등비수열을이루는서로다른세항을골라낼수있다는것과 x 가유리수라는것이필요충분임을보여라. ( 캐나다 993-) 증명 () 의증명 ) x + a, x + b, x + c 가등비수열을이룬다고하자. 그럼 (x + a)(x + c) =(x + b), 즉 (a + c b)x = b ac ( ) 산술-기하평균부등식에서 (x + a)+(x + c) (x + b) 이므로 a + c b 0 인데, 서로다른항들이므로등호가성립하지않고, 따라서 a + c b >0 이다. 즉,( ) 의계수가 0이아니므로 x = b ac a+c b 로유리수이다. (( 의증명 ) x가음수이면 x +, x +, ::: 로증가하다보면언젠가양수가되므로, x가양수일때에만증명해도충분하다. 유리수이므로 x = q p 라하자. ( + (p + p )) = ( + p) 의항등식에서양변에 x x를곱하면 x (x +(q + pq)) = (x + q) 즉, x, x + q, x +(p + pq) 가등비수열을이룬다. 68. 방정식 x n +(+x) n +( x) n =0 이정수해를가질수있는모든양의정수 n 을구하여라. (APMO 993-4) 풀이 (O±cial) y = x n +(+x) n +( x) n 이라하자. () n 이짝수일때, x 가정수이면 x n ; ( + x) n ; ( x) n 은모두음이아닌정수이므로 y =0 이되려면이들은모두동시에영이되어야한다. 이는불가능하므로이경우는정수해가없다. () n 이 n 3 인홀수일때, y 는 x n 의계수가 인 n 차다항식이고, 상수항은 n+ 이며모든항의계수는양수이므로 y =0 이정수해를갖는것은 x = t (0 t n +) 인경우뿐이다. t =0 일때 : x = 이고, y =( ) n + n +3 n = 3 n 6=0. t = 일때 : x = 이고, y =( ) n +0+4 n =4 n n 6=0. 따라서, t. t = p + 이라하면, p 이고 y =( p+ ) n +( p+ ) n +(+ p+ ) n = n f pn +( p ) n +(+ p ) n g = n [ pn +f+( n )p +( n 4 )4p + g] 이므로 n 3 일때위식의우변의 [] 안은 [] (mod4) 이므로 y 6= 0 이다. 따라서 n 이 n 3 인홀수일때도정수해는없다. 남은경우는 n = 일때뿐이다. 이때 x +(+x)+( x) =0 에서 x = 4. 이상을종합하면 n = 일때만정수해를갖는다. } 69. 방정식 x + y 3 = z 의자연수해는유한개인가아니면무한개인가? (Towns 993 가을 SO) 풀이 y 3 = z x =(z + x)(z x) 이므로 z + x = y, z x = y 인것만생각해보면, z = y(y+), x = y(y ) 로무한히많은해가있음. } 70. n 번째소수를 p n 이라할때다음을보여라. ( 통신강좌 ) p n < n

22 수론 풀이수학적귀납법을쓴다. n =일때, p =이므로자명하다. k n인모든자연수 k에대해성립한다가정하자. N = p p p n +이라하면, p,, p n 은 N을나누지않는다. 그러므로, m>n인자연수 m이존재하여, p m 이 N을나누어야한다. 즉, p m N 그런데, p n+ p m 이므로, p n+ N이다. 한편, 수학적귀납법에의해 N = p p p n +< + = + + n + = n+ + n+ ) p n+ < n+ 이다. } 7. 자연수의수열 fa n g 이다음과같이정의된다 : a n+3 = a n+ (a n+ + a n ); n =; ; 3;::: a 6 =44 일때 a 7 을구하여라. ( 통신강좌 ) 풀이 a = x, a = y, a 3 = z 라하면 a 4 = z(y + x), a 5 = z(y + x)(z + y), a 6 = z(y + x)(z + y)[z(y + x)+z] =z (z + y)(y + x)(y + x +) 이다. y + x 와 y + x + 이인접정수임에유의하면서 44 = 4 3 의약수들을쓰면,,,3,4,6,8,9,, 6, 8, 4, 36, 7, 44 이고 (,3), (3,4), (8,9) 가후보이다. (, 3) 인경우는 x = y = 이고 44 = z (z +) 3 즉,4=z (z +) 이나정수해가없다. (3, 4) 인경우는 44 = z (z +y)3 4 에서 = z (z +y) 이고 z =,y = 만이해이다. 그러므로 x = 이고 a 7 = a 6 (a 5 + a 4 ) = 44[ ] = 44 4 = 3456 이다. (8, 9) 의경우 44 = z (z + y)8 9 에서 =z (z + y) 이고 z =,y =,x =7(* x + y =8) 이고 a 7 = 44(6 + 8) = 3456 이다. [ 답 ] a 7 = 3456 } 7. a <a < <a n < 은음이아닌정수열로서모든자연수 n 에대해 a n = a n + n 을만족한다. 그리고 n 이소수일때만 a n 도소수가되는성질을갖고있다. a 994 를구하여라. ( 통신강좌 ) 풀이 a k <a k+ <a k+ <:::<a k = a k + k 이므로 a k+ = a k +;k 을얻을수있다. 즉, a n = a +(n );n 이다. a =0 이면 a =;a 3 =;a 4 =3 이므로모순. a 이라고하자. 이때 p 를 (a +)!+(a +) 보다큰소수라고하자. 그리고, n = p (a ) 로잡자. a n = p 이므로가정에의해 n 도소수이어야한다. 그런데, n>(a +)!+ 이고 (a +)!+k; k f;::: ;a +g 은모두소수가아니므로 n p 가되어 n = p (a ) 에모순. 즉, a = 이어야하고 a 994 = 994. } 73. 모든정수 x 에대해, 다음의수가정수임을증명하여라. ( 호주 994-) 5 x5 + 3 x x 증명 통분하고 mod 3, mod 5 에의한단순잉여 증명 x 5 + x 3 을빼고더하여페르마소정리

23 . 수론중급문제 3 증명 3 귀납법 74. 여섯정수의 6제곱의합빼기 하면이여섯수의곱의여섯배가된다. 이여섯수중에하나만 이고나머지는모두 0임을증명하여라. (Towns 994가을 JA6) 증명산술-기하로 6abcdef = a 6 + b 6 + c 6 + d 6 + e 6 + f 6 3a b c +3d e f, 즉 3(abc def) 얻을수있음. 즉, abc = def 일수밖에없고, 임의의세항의곱은나머지세항의곱과항상일치. 0이없다면둘씩교환하다보면모두같아야해서문제의조건이 만큼맞지않음. 즉, 0이있고, 그럼 6제곱의합이 이므로원하던결론이나옴. 75. x, m, n 이모두 보다클때다음식이해를가지지않음을증명하여라. n x m = ( 통신강좌 ) 증명 ( 부산과학고허석문 ) x 는홀수이므로 x =k + 이라고두자. n 이 보다크므로, n = x m +=(k +) m + 0(mod4). 이항전개에의해 (k +) m + ) m; k 는홀수 m 이홀수이므로 x m + 을인수분해하면 ³³ m k + + (mk +) 0 (mod 4) x m +=(x +)(x m x m + x m 3 +)= n x 는홀수이므로 x m x m + x m 3 + (mod) ) x += n, x m x m + x m 3 += n = x m +=x +) m =) m 이 보다크다는것에모순 ) n x m = 을만족하는해는없다. 76. 다음수열의항중최소인것을구하여라. ( 통신강좌 ) a = < a n+ = 3 a n (3 j a n 일때 ) : a n +3 (3- a n 일때 ) 풀이일단최소값은 4보다작음을증명한다. 만일 am 이최소값이고 4이상이라고가정해보자. (i) a m =3k +(k : 자연수 ) 라면 a m+ = k +4<a m 이므로모순. (ii) a m =3k + (k : 자연수 ) 라면 a m+ =3k +4 a m+ = k +8<a m 이므로모순. (iii) a m =3k +3(k : 자연수 ) 라면 a m+ =3k +6 a m+ =3k +39 a m+3 = k +3<a m 이므로모순. 따라서최소값은 3이하이다. 이제최소값을구하기위해 mod3으로관찰을해보자. ( 9a n (3 j a n 일때 ) a n+ = a n (3 - a n 일때 ) 한편, a = (mod 3) 오일러정리에의하면 6 (mod3).

24 4 수론 한편 (mod) 이므로, a 6 3 8(mod3). a n 이취할수있는값을다음그림으로살펴보자.? 9 8 7? 9? 9 따라서 a n 8, 7, 이다. 그러므로최소값은 8이나 7, 이다. 만일 a m =8이라면 a m+ = a m+ =7 만일 a m =이라면 a m+ =4 a m+ =8 a m+3 = a m+4 =7 즉, 최소값은 7이다. } 77. 방정식 x y = 의정수해가무한히많이존재함을보여라. ( 한국 995-) 증명 ( 과기원 95 학번허충길 ) ( + p ) n = a n + b n p (n 0 인정수 ) 이라정의하면명백히다음과같은성질을얻을수있다. ( p ) n = a n b n p (n 0 인정수 ) 그러면 a n b n =(a n + b n p )(an b n p ) = ( + p ) n ( p ) n =( ) n = 따라서, x = a n, y = b n 은 x y = 의해이고, a n 은단조증가하므로무한히많음도알수있다. 78. 복소수계수의방정식 x 3 +ax +bx+c =0 의모든복소근이절대값이 이면, 방정식 x 3 +jajx +jbjx+jcj = 0 의모든복소근도마찬가지로절대값이 임을증명하여라. ( 아일랜드 995-7) 증명세근과그켤레를이용하면 jaj = jbj 이고 jcj =임을알수있음. 그럼우선 을한근으로갖고, 나머지두근 ( 서로켤레 ) 의곱이이니까두근모두절대값이 임. 79. 서로다른네소수의곱으로임의의자연수 n 에대해,=d <d < <d 5 <d 6 = n 을 n 의약수들이라하자. n<995 이면 d 9 d 8 6= 임을증명하여라. ( 아일랜드 995-0) 증명약수들의대칭성에의해 n = d d 6 = d d 5 = = d 8 d 9. n을구성하는네소수를 p<q< r<s, 즉 n = pqrs 라하자. 귀류법으로, d 9 d 8 =라하자. d 9 와 d 8 은홀짝이같다. 둘다짝수이면 n = d 8 d 9 는 의배수이므로 n이서로다른네소수의곱임에모순. 따라서, d 9 와 d 8 은둘다홀수이고, n도홀수, 즉 p 3 이다.(p; q; r) =(3; 5; 7) 이아니면n > = 995 가되어모순. 즉,(p; q; r) =(3; 5; 7) 이고, s<9 이다. s =; 3; 7 일때각각d 9 d 8 을구해보면모두성립하지않음 ( 혹은 d 8 ;d 9 모두둘이상의소수의곱이므로딱두소수의곱이고대충약수들의차례를생각하면 fd 8 ;d 9 g = f3s; 5 7g뿐인듯.3p 35 = 를풀면p =9)( 또혹은, d +d n =0이정수해를가져야하므로판별식 + n 이제곱수라야하는데 s =; 3; 7 일때n을대입해보면제곱수인것이없음 ).

25 . 수론중급문제 n 은고정된자연수이다. k 가음이아닌정수이면, x i 와 y 에대한부정방정식 x 3 + x x 3 n = y 3k+ 이무한히많은자연수해를가짐을보여라. ( 캐나다 995-4) 증명 x = x = = x n = x 로두어보자. nx 3 = y 3k+ x = n a, y = n b 으로두면 3a + = 3kb +b 을만족하면된다.b (mod3) 이어야하므로 b =3t + 로하면되고, 이때 a =3kt +k +t + 이된다. 즉, 임의의음이아닌정수 t 에대해, (x; y) =(n 3kt+k+t+ ;n 3t+ ) 가모두해가된다. 8. a0 09 꼴 (0 은 개이상, a ) 의수는완전제곱수일수없음을보여라. (Towns 995 봄 SO4) 증명 a 0 n =(m +3)(m 3) 의두인수m +3 과 m 3 이둘다5의배수일수없으므로어느한쪽이 5 n 을다가짐. 따라서, m +3 5 n. 그럼 m 3 a n 9 n. 이둘에서 5 n 6 9 n 인데이것은 n 이면성립하지않음. 8. 자연수들로된무한수열 fa ng 과 fb ng 이있다. fa ng 은공차가 r (> ) 인등차수열이고 fb ng 은공비가 q (> ) 인등비수열이다. 그리고 r 과 q 는서로소이다. 이두수열에같은항이있다면, 같은항이무한히많이있음을증명하여라. ( 폴란드 995/996 차 -6) 증명 q c (modr) 인자연수c가존재. a i = b j 이면 a i <q kc b j b j = a i (mod r) 로같은항이또있음. 83. 어떤정수계수의다항식을 x x + 로나누었더니나머지가 990x 889 가나왔다. 이다항식은정수근을갖지않음을보여라. ( 폴란드 995/996 차 -9) 증명 P (x) =(x )((x )Q(x) + 990) + 0 = 0 이면 x = ; 0. x =0; ; 00; 0 를각각대입해보면각각모순. 84. 다음방정식의모든자연수해 (x; y) 를구하여라. ( 통신강좌 ) x 3 y =7 풀이 mod 3 으로생각하면 x =x 0. 다시 mod 4 로생각하면 y =y 0 이된다. 그럼준식은 ( x0 +3 y0 )( x0 3 y0 )=7 이고, 그럼 7 =7 이되는경우뿐이다. 즉,( x0 ; 3 y0 )=(4; 3) 뿐이고,(x 0 ;y 0 )=(; ), (x; y) =(4; ) 가유일한해가된다. } 85. p 는소수이고 a 와 n 은 p +3 p = a n 을만족하는자연수이다. n = 임을증명하여라. ( 아일랜드 996-8) 증명귀류법으로, n 라가정. p =일때 +3 =3로성립하지않음. p> 이면 5 j p +3 p, 즉 5 j p +3 p. p 3 p =( 3) p p (mod 5) 임에서 p (mod5). 따라서,5jp, 즉 p =5. 그런데 =75도성립하지않음. 86. 다음식의모든정수해를구하여라. ( 폴란드 996 차 -5) x (y ) + y (x ) = 풀이 x =또는 y =일때따로풀고, x; y 6= 일때는y (modx ) 이므로 jx j jy j, 마찬가지로 jy j jx j. 여기서좀따져보면아마... }

26 6 수론 별해 x 에대한내림차순으로정리하면 (y )x + y x (y +) =0. 판별식 D = y 4 +4(y )(y +)=y 4 +4y 3 4y +4y 4 가제곱수가되어야함을부등식법으로좀해보면... } 87. 정수 n 이합성수일때, 또그때만, 두관계식 a + b = n 과 x a + y =을만족시키는자연수 a, b, b x, y가존재함을증명하여라. ( 폴란드 996/997 차-4) 증명 ()) n = ad 일때b = a(d ), x =,y =(a )(d ) 로두면됨.(() n이소수이면 ( 귀류법 ) 정리하면 n(a x) =a(a x + y). 모든항이양이고 n과 a는서로소이므로 n j a x + y. a x<a 이므로우변이항상큼. 88. gcd((n +) m n; (n +) m+3 n) > 을만족하는자연수 m; n 의모든쌍을구하여라. ( 통신강좌 ) 풀이 ( 과기원수학과 96 학번허석문 ) n, m 을문제의조건을만족하는자연수라하고, 이라하면, d =gcd((n +) m n; (n +) m+3 n) (n +) m+3 (n +) m =(n +) m ((n +) 3 ) = n(n +) m (n +3n +3) 이 d 의배수이고 d 는 n, (n +) 과서로소이므로 (n +3) 3 (mod d); n +3n +3 0 (mod d) d 의정의에의해,(n +) m n (mod d) 임을상기하자. (i) m =3k + 일때, n (n +) m =(n +)((n +) 3 ) k (n +) (modd) 이므로모순. (ii) m =3k + 일때, n (n +) m =(n +) ((n +) 3 ) k (n +) (mod d) 에서 (n +) n = n + n + 0 (mod d): 또한 n +3n +3 0(modd) 이므로변변빼주면 (n +) 0(modd) 이고 d 와 (n +) 이서로소이므로 d =: 그러나이경우 n(n +) 이짝수이므로 n + n + (modd) 가되어모순. (i), (ii) 에의해 m =3k 이어야한다. 이때 n (n +) m =((n +) 3 ) k (modd) 이므로 n (mod d) 이다. 따라서 (n +) 3 ( + ) 3 =8 (modd) 이므로 이경우 (n +) =8 (mod7) 이므로 d =7; n (mod 7): (n +) m n =(n +) 3k n k 0 (mod 7) (n +) m+3 n =(n +) 3k+3 n k+ 0 (mod 7) 이므로문제의조건을만족한다. 따라서문제의일반해는 (n, m) =(7` 6, 3k)(`, k 는자연수 ) 이다. } 89. a 를 3 보다큰홀수라하자. 모든자연수 n 에대하여 a n 은적어도 n + 개의서로다른소인수를가지고있음을증명하여라. ( 통신강좌 ) 증명 ( 과기원 97학번이수인 ) 수학적귀납법으로증명하자. n =인경우u = a +, v = a 라하면a가5이상의홀수이므로 u, v는연속한자연수이고둘중하 나는큰홀수이다. 따라서 a =4uv는홀수인소인수를적어도하나가지고있다. 또한 도 a 의소인수이므로이는적어도 개의서로다른소인수를가지고있다. n 인 n에대해a n 이 (n +) 개이상의소인수를가지고있다고하자. a n+ =xy; x = a n +; y = a n a n (mod4) 이므로 x (mod4) 이다. 따라서 x 는홀수인소인수 p 를갖는다. x 와 y 는연속한 자연수이므로서로소이고 p 는 x 의소인수이므로 y 의약수가아니다. 귀납법가정에의해 a n 은적어도 (n +) 개의소인수를가지며 p 가그들중하나가아니므로 xy = a n+ 은적어도 (n +) 개의소인수를가진다. 따라서임의의자연수 n 에대해 a n 은적어도 (n +) 개의소인수를가진다.

27 . 수론중급문제 어떤정수 A, B 에대해서는다음두집합 M = fx + Ax + B j x Zg; M = fx +x + C j x Zg 가교집합을갖지않도록하는정수 C 가있음을보여라. ( 통신강좌 ) 증명 ( 과기원 97학번김병두 ) i) A가홀수일때 M : x(x + A)+B B (mod ) 즉 C 6 B (mod ) 로 C를정하면됨. ii) A가짝수일때 µ M : x + A + B A 4 B A A 또는 B + (mod4) 4 4 M : x(x +)+C C (mod 4) 역시 C B A A +또는 B +3으로하면됨. 4 4 i), ii) 에서증명가능. 9. (7 + p 50 ) 997 을십진법으로썼을때의소수점이하처음 997 자리를구하여라. ( 몰도바 997 최종 -y-) 풀이 t =7 p 50, a n = t n + + tn 으로두면 a n 은정수. 0: <t < 0 이므로 n이홀수이면 t n + = a n t n (a n;a n +0: n ). 따라서, 소수점이하 n자리가모두 0. } 9. 주어진자연수 n 에대해 ¾(n) 을 n 의약수의합이라하자.( 예 : ¾(3) = +3 = 4, ¾(6) = =, ¾()= =8) 이때 ¾(n) > n 이면 n 을초과수라부르자.( 따라서, 예를들어, 는초과수이다.) a, b 가자연수이고 a 가초과수이면 ab 도초과수임을보여라. ( 아일랜드 997-6) 증명 a의약수들을d ;d ;:::;d k 라하면d b; d b;:::;d k b는 ab의서로다른약수들. 이들만모두합해도 ab를넘으므로 ab는초과수. 93. 다음성질을만족하는세자연수의쌍을모두찾아라 : 세수중임의의두수의곱을나머지한수로나눈나머지는항상 이다. ( 폴란드 997 차 -4) 풀이 abc j (ab )(bc )(ca ) 이므로 abc j ab + bc + ca. 즉 a + b + c = k( abc 정수 ). k =or이고, 경우를나눠풀면됨. } 94. a, b 는자연수이고 ab 가 a + b 의약수라고한다. a = b 임을증명하여라. (Towns 997 봄 SO) 증명 a 6= b 라면 p m k a, p n k b 이고 m 6= n 인경우가존재. 그러나 ab j a + b 임에서 m + n min(m; n) 라야하는데이것은 > 이기도해서모순. 증명 a kab + b =0에서 a 6= b 인자연수해가존재한다면 WLOG a>b인최소의해가존 재. b를고정시키면 a의이차방정식. a와짝이되는해를a 0 이라하자. 그럼 0 <a 0 = b a <b이므로 (b; a 0 ) 은 (a; b) 보다더작은해가되어최소성에모순. 95. p가홀수인소수이고 k가 k p 인정수라할때다음을증명하여라. ³ p ( ) k (mod p) ( 통신강좌 ) k 증명 ( 서울과학고 학년박영훈 ) (p )(p ) (p k) ( )( ) ( k) k! ( ) k (mod p) gcd(p; k!) = 이므로 p k ( ) k (mod p).

28 8 수론 96. A는정수들의집합으로, 모든 x; y A 에대해서 x y 또한 A에속하는성질을갖고있다.998A 이고, 구간 [ 00; 00] 가 A의원소를 33개이상,66개이하로포함한다고하자. 구간 [ 998; 998] 에는 A의원소가몇개포함되겠는가? ( 몰도바 998 최종-y0-7) 풀이 A = dz꼴 ( 셈본고등중급최대공약수편참조 ). 33 b 00 c + 66 d 에서 3 <d<7 이고, 그럼 d j 998 에서 d =6. } 97. P (x) 는정계수다항식이고 P (x) =0을만족하는정수해가있다. P (995)P (000) 이 7의거듭제곱이될수없음을증명하여라. ( 몰도바 998 최종-y-8) 증명 P (x) = 0 의정수해를 a. P (x) = (x a)q(x). P (995)P (000) = (995 a)(000 a)q(995)q(000) 이 7 의거듭제곱이려면 995 a, 000 a 도 7 의거듭제곱. 그런데두 7 의거듭제곱수의차이는 5 가될수없다 ( 가장작아도 7 =6 이상 ). 98. n 은 3 이상의정수이다. x x 와 x n x 가둘다정수가되는실수 x 는정수뿐임을증명하여라. ( 아일랜드 998-5) 증명 x x = a, x n x = b 라하자.0<x< 이면 a는정수가아님. 그외엔 a>0. x = x + a 를이용해 x n 의차수를떨어뜨리면식 x n x = b 는 Ax = B꼴이됨. 특히귀납적으로 A>0 임을확인할수있음. 따라서, x는유리수이고, 이제유리해정리를이용하거나직접결론내리면됨. 99. 다음을만족하는 a b c 이고 x y z 인자연수 a, b, c, x, y, z 를모두구하여라. a + b + c = xyz; x + y + z = abc ( 폴란드 차 -) 풀이 (a; b; c) 와 (x; y; z) 의대칭성에서 WLOG a + b + c abc. c 이면모순이므로 c =. 또 b 3 이면모순이므로 b =or. 이런식으로경우나눠서막노동. } 00. x, y 는실수이고 x + y, x + y, x 3 + y 3, x 4 + y 4 가모두정수일때, 모든정수 n 에대하여 x n + y n 이정수임을보여라. ( 폴란드 998/999 차 -4) 증명 xy, x y 이정수가되고이로부터 xy 는정수. 그럼점화식 P n = x n + y n =(x + y)p n xyp n 에의해 P n 은모두정수. 0. y x = x 50 의자연수해를모두찾아라. ( 폴란드 998/999 차 -5) 풀이 x를소인수분해했을때지수들의최대공약수를 a, 즉 x = n a 이고 n은더이상거듭제곱으로나타낼수없는수라고할때, n 50a=na = y 가자연수임으로부터 n a j 50a. 다시이로부터 n j 50 임을알아낼수있다 ( ). 그럼 n =; ; 5; 0; 50 일때각각풀면됨.( ) 이틀림없음을확인해보자.gcd(n; a) 의임의의소인수 p에대해, e p(a) e p(n a ) 임을확인할수있다 (e p(m) 은 m의소인수분해에서의 p의지수 ). n a n j 50a 에서 e p (n a )+e p (n) e p (50) + e p (a) 이므로그럼 e p (n) e p (50) 이라는것이고, 따라서 n에서 50을나누다남아서 a만나누는부분은없다. } 풀이 x가, 5 이외의소인수 p를갖는다면 y도 p를소인수로갖는다. 양변의 p의지수를비교하면 50e p (x) =xe p (y), 즉 p ep(x) j e p (x) 인데, 이것은일반적으로 e 일때p e >e임에서모순. 즉, x( 와 y) 의소인수는, 5뿐이다. x = a 5 b, y = c 5 d 이라하고대입하여비교하면,50a = a 5 b c, 50b = a 5 b d. a =0일때, b =0일때각각따로풀고, a; b > 0 일때는a a,5b 5 b 임을이용해풀면됨. } 0. n =(d(n)) 을만족하는모든자연수 n 을구하여라. 단, d(n) 은 n 의양의약수의개수를나타낸다. ( 캐나다 999-3)

29 . 수론중급문제 9 풀이 n 은완전제곱수이므로 n = p e p e k k 꼴로소인수분해된다. d(n) =(+e ) ( + e k ) 이므로 n = d(n) 은다시쓰면 가된다. 우변은홀수이므로 p i 3. 이항정리에의해 p e pe k k =(+e ) ( + e k ) ( ) p e i i ( + ) ei +e i 이성립하고, 등호는 p i =3,e i =일때만성립하므로,( ) 의등식이성립하기위해서는 k =,n =3 일수밖에없다. } 03. a 3 +6ab + 과 b 3 +6ab + 이동시에세제곱수가되도록하는자연수쌍 (a; b) 를모두구하여라. ( 폴란드 999/000 차 -5) 풀이부등식법 a 3 +6ab + (a +) 3, b 3 +6ab + (b +) 3 으로범위줄여놓고풀면금방. 아마 a b 로하면b a 이되고a 3 +6ab +< (a +4) 3 이었나.. } 04. m, n 은자연수이고 mn 은 m + n + m 을나눈다. m 이완전제곱수임을증명하여라. ( 폴란드 999/000 차 -9) 증명 gcd(m; n) =d 라하면d j m. m = d M, n = dn 으로두면 M, N은서로소. 대입하면 d 3 MN j d 4 M + d N + d M, 즉 dmn j d M + N + M. 여기서 M j N 이고서로소임에서 M j. 끝. 05. n 8 n 이 7 의배수가되지않는음아닌정수 n 을모두구하여라. ( 몰도바 000 최종 -y9-6) 풀이 n 3 0; (mod9) 이므로준식은 9의배수. 8의배수여부만검토하면됨. n이홀수이면연속한두짝수의곱n 을인수로가지므로 8의배수. n이 4의배수이면당연히8의배수. n (mod 4) 일때만8의배수가아님. 답 n =4k +꼴. } 06. f(x) =5x 3 +3x 5 +9ax 라하자. 모든정수 x 에대해 f(x) 가 65 로나누어떨어지게되는최소의자연수 a 를구하여라. ( 아일랜드 000-3) 풀이 0 f(x) x 5 ax ( a)x (mod 5). 모든 x에대해성립해야하므로 a (mod 5). 0 f(x) 8x 3 4ax ( 8 4a)x (mod 3). 모든 x에대해성립해야하므로4a 8 (mod 3), 즉 a (mod3). 따라서, a (mod65) 이고, 이것이면충분. a의최소값은 63 답 } 07. 임의의정수 n 과임의의소수 p 에대하여, n pp + p p 이항상합성수임을증명하여라. ( 폴란드 000/00 차 -5) 증명 p =일때소피제르망인수분해. p 3 일때 (n pp ) p + p p =(n pp + p)q꼴로인수분해 됨. 08. 모든자연수 k 를 k = mn + 꼴로쓸수있음을증명하여라. 단, m, n은자연수이다. m + n ( 몰도바 00 최종-y7-8) 증명 (m; n) =(k+; k ) 으로끝.(m; n) =(k+;k +k ) 로할수도. 둘다 (m k)(n k) = k 에서적당히두어구한것임. 09. 임의의 n> 에대해, n 과 (n +) 사이에는 a + b 이 c의배수가되는서로다른세정수 a, b, c가존재함을증명하여라. ( 몰도바 00 최종-y9-6)

30 30 수론 증명 (n + n +) +(n + n) (n +) +(n ) =(n +) 0(modn +). 0. a, b, c 는실수이고, ax + bx + c =0 의두근을 p, p 라하고 cx + bx + a =0 의두근을 q, q 라할때, p ;q ;p ;q 는, 이순서로, 서로다른항으로된등차수열을이룬다고한다. a + c =0 임을보여라. ( 중미 00-5) 증명 p D jaj = p + p =q, q + q =p 임에서변변더하여정리하면 p p = q q. 즉, 두근의차 p D. a = c jcj 이면두식이같으므로서로다른등차수열일수없음. 따라서, a = c. ³ n ³ k. k; n > 은정수이고 p =k 은소수이다. 가 p의배수이면 p 의배수이기도함을증명하여라. ( 폴란드 00 차-) 증명준식은 (n k)(n + k ) 이고, 이것이 p의배수이면 (n k) 와 (n + k ) 중하나가 p의배수인데,(n + k ) (n k) =p 이므로둘다 p의배수.. 다음명제가성립하도록하는정수 n 3 을모두찾아라 : a +a + + na n 이유리수인등차수열 a ;:::;a n 은항상유리수인항을적어도하나갖는다. ( 폴란드 00 차 -4) 풀이 a i = a+id 로두면합S = n(n+) a+ n(n+)(n+) d = n(n+) (a+ n+ d). 6 3 즉, a+ n+ d 3 가유리수. 따라서,3jn +, 즉 n =3k +꼴일때는명제가성립. 이꼴이아닐때는 a = p = n+ d 3 로두면성립하지않음을확인할수있음. } 3. 모든자연수 n 에대하여 n a + b 가항상완전제곱수가되도록하는정수 a, b 가있다. a =0 임을증명하여라. ( 폴란드 00 3 차 -4) 증명 n+ a + b 와 4( n a + b) 가둘다제곱수이고그차인 3b가제곱수의차. a 6= 0이면 n을키워두수를얼마든지키울수있으므로, 상수 3b가계속큰두제곱수의차가될수는없음. 4. 자연수 n 을십진법으로나타낸각자리수의합을 S(n) 이라하자. n 을십진법으로나타내었을때오른쪽으로부터몇개 ( 적어도 개이상 ) 의자리수를지워얻은자연수를 n 의도막이라고부른다. n 의모든도막의합을 T (n) 이라하자. n = S(n)+9T (n) 임을보여라. (APMO 00-) 증명 (Kalva) Let the digits of n be a d ;a d ;:::;a 0,sothatn = a d 0 d + +a 0.Andletn(k) be the number formed by deleting the last k digits of n. Thenn(k) =a d 0 d k +a d 0 d k + +a k and T (n) = P d k= n(k). Obviously S(n) =a d + + a 0. Hence S(n)+9T (n) =a d (9 0 d +9 0 d + +9+)+a d (9 0 d + +9+)+ +a d k (9 0 d k + +9+)+a (9+)+a 0 = a d 0 d + + a 0 = n. 5. n 의자릿수의총합을 S(n) 으로나타내자. 자연수 n 에대하여 S(n +3) 은완전제곱수가될수없음을증명하여라. ( 폴란드 00/00 차 -8) 증명 3 - n 이면 S(n +3) n +3 (mod3) 으로안되고,3j n 이면 S(n +3) n +3 3(mod9) 로불가능. 6. a = a = a 3 = 이고 a n+ a n a na n =(n 3) 으로정의된수열 (a n) 이있다. 모든 n 에대해 a n 은자연수임을증명하여라. ( 아일랜드 00-4) 증명 준식과 ana n 3 a n a n = 를변변빼어정리하면 a n a n + a n+ = a n a n 3 + a n = a = = a + a 3 또는 a 3 = 가된다 ( 전자는 n이짝수일때, 후자는 n이홀수일때 ). 즉, a + a 4 4 a n+ =a n a n 또는 4a n a n 의점화식으로얻어지게되므로, a n 은항상자연수이다.

31 . 수론중급문제 3 7. 다음의수들이모두소수가되도록하는자연수 p q r 을모두찾아라. pq + r; pq + r ; qr + p; qr + p ; rp+ q; rp + q ( 폴란드 00 차 -4) 풀이 p, q, r이모두홀수이면모든항이짝수, 즉모두로동일, 그럼 p = q = r =뿐. p가짝수이면 이상이므로모든항이 3 이상, 즉홀수인소수, 그럼 pq + r, pr + q 가홀수임에서 q, r은홀수라야하고그럼 qr + p 가짝수라서모순. q나 r이짝수일때도대칭적으로마찬가지. } 8. 방정식 (x + y) (xy) = 을만족하는모든자연수해 (x; y) 를구하여라. ( 폴란드 00/003 차 -) 풀이 ( 서울과학고 학년김성구 ) y = 을넣으면 (x +) x =, 즉 x +x =0,x =. 대칭성에따라일단해 (x; y) =(; ) 와 (; ) 을얻을수있다. 이제 x>, y> 일때만살피면되고, 그럼 (x )(y ) > 0, 즉 xy +>x+ y. 이것을준식에대입하면 (xy +) (xy) > 정리하면 x y +xy > 0. xy > 0 이므로나눠주면 xy +> 0, 따라서 >xy. 따라서, x; y > 일때더이상의해는없다. } 9. n 을 333 자리의자연수라고하자. n 의각자리수는 0 이아닌수들로이루어져있다. i =; ;:::;33 에대해, n i+ 은 n i 의맨마지막자리수를맨앞으로옮겨만들어진수라고하자. 이때, n ;n ;:::;n 333 은모두 333 의배수이거나, 모두 333 의배수가아님을보여라. ( 폴란드 00/003 차 -5) 증명 ( 여주홍지현 ) a i 를 n i 에서의맨마지막자리수라고하자. 그러면, 그런데, 0n i+ (0 333 )a i = n i = {z } 333 개 = {z } 3 이 개 이므로 은 333의배수. 따라서 n 0n 00n 3 (000n 4 )n 4 00n 333 (mod 333) 0, 00 모두 333 과서로소이므로, n i 중어느하나가 333 의배수이면나머지도모두 333 의배수이다. 즉, n ;n ;:::;n 333 은모두 333 의배수이거나, 모두배수가아니다. 0. 3a +4b +9c +d =4 의정수해를모두구하여라. ( 셈본중등고급도전문제..) 풀이 a +3c +4d = u 라하면 3a +4b +9c +d =3u +4b =4 (b; u) =(; 0) 은방정식의특수해이므로 (b; u) =( 3k 0 +; 4k 0 ) a +3c +4d = u에서 3c +4d = v라하면 a +3c +4d = a + v = u (a; v) =(u; 0) 은위방정식의특수해이므로 (a; v) =( k + u; k )=( k +4k 0 k; k ) 3c +4d = r 에서 (c; d) =(4k v; 3k 3 + v) =(4k 3 k ; 3k 3 + k ) ) (a; b; c; d) =( k +4k 0 ; 3k 0 +; 4k 3 k ; 3k 3 + k ) (k ;k ;k 3 Z) }

32 3 수론. a, b, c 가둘씩서로소일때 xbc + yca + zab = n 의일반해를구하여라. ( 셈본중등고급도전문제..) 풀이 xbc + yac + zab = u u = yc + zb로치환xbc + ua = n (bc; a) =이므로 xbc + ua =은해를갖는다. (x; u) =(x 0 ;u 0 ) 를 xbc + ua =의특수해라고하자. 그럼 xbc + ua = n의해는 (x; u) =( ak 0 + nx 0 ;bck 0 + nu 0 ) u = yc + zb 에서 (b; c) = 이므로 =yc + zb 는해를갖는다.(y; z) =(y 0 ;z 0 ) 가 yc + zb = 의특수해라고하면 u = yc + zb 의해는 (y; z) =( bk + uy 0 ;ck + uz 0 ) =( bk + bck 0 y 0 + nu 0 y 0 ;ck + bck 0 z 0 + nu 0 z 0 ) ) (x; y; z) =( ak 0 + nx 0 ; bk + bck 0 y 0 + nu 0 y 0 ;ck + bck 0 z 0 + nu 0 z 0 ) }. 조건 x 4 y = 을만족시키는정수의순서쌍 (x; y) 의개수는모두몇개인가? ( 한국 003 차 -S4) 풀이 x 는홀수임을알수있고, 그럼 y =(x )(x +)(x +) 에서 y 는짝수이다. y =Y, x =X + 을대입하고양변을 8 로나누면 Y = X(X + )(X(X +)+) 인데, 우변의세항이모두서로소이므로모두 완전제곱수여야한다. X 와 X + 의차는 인데 n 꼴들의수중에서차가 이되는경우는 과 0, 그리고 0 과 뿐이다. 즉, X(X +)=0 으로어느경우나 Y =0, 즉 y =0 이다. 따라서, 해는 ( ; 0) 의 개뿐이다. } 3. 음이아닌정수 n 에대하여 ³h n i h n i f(0) = 0; f(n) =f + n 을만족시키는함수 f(n) 이있다.05n5003 일때, f(n) 의최대값은얼마인가? ( 실수 x에대하여 [x] 는 x를넘지않는가장큰정수이다.) ( 한국 003 차-S7) 풀이의개요 f(n) =f(n), f(n +)=f(n) 이므로 f(n) 은 n을 진법으로썼을때자리수의합을구하는함수이다.003는 진법으로 자리의수이므로자리수의합은 을넘을수없고,인것은 047이므로역시불가능하고,0인것은여러개있다. 답 0 } 4. 조건 n = m 4 +m 3 +m +m + 를만족시키는정수의순서쌍 (m; n) 의집합을A = f (m i ;n i ) j kx i =; ;:::;kg 라할때 (m i + n i ) 의값은얼마인가? ( 한국 003 차-S6) i= 풀이 ( 대덕중 3 학년이태희학생의풀이를수정 )(m +) +> 0 이므로 n = m 4 +m 3 +m +m + >m 4 +m 3 + m =(m + m) 또, m =0이면 n =여서곤란하므로 m 0 이고, 그럼 n = m 4 +m 3 +m +m + m 4 +m 3 +3m +m +=(m + m +)

33 . 수론중급문제 33 또한, 이식의등호는 m = 일때에만성립한다. 즉, m > 이면 (m + m) <n < (m + m +) 이되어해가없다. 따라서,(m; n) 의해는m = 일때가전부이고, A = f(; 3); (; 3); ( ; ); ( ; )g kx 이다. 따라서, 구하는식의값은 (m i + n i )=( +3 )+( + )=4. } i= 5. 다음방정식을만족하는정수해 (x; y; z) 를모두구하여라. ( 북유럽 003-) x 3 + y 3 + z 3 3xyz =003 풀이좌변을 (x + y + z)((x + y + z) 3(xy + yz + zx)) 로인수분해. x + y + z =일때는mod 3으로맞지않음. 그렇지않은경우엔 003이소수이고 (x + y + z) 3(xy + yz + zx) 0 이므로 (x + y + z) 3(xy + yz + zx) =밖에없는데이건 (x y) +(y z) +(z x) =와같고, 이건 ++0꼴뿐.WLOGx y z 라하면가능한것은 (x; y; z) =(x; x; x +) 또는 (x; x +;x+) 뿐임을얻을수있고, 그중 (667; 668; 668) 만성립. } 6. m +m = n 4 +0n 3 +04n +40n 의모든정수해 (m; n) 을구하여라. ( 아일랜드 003-8) 풀이 ( 장영실과학고 학년김윤섭 ) (m +) = m +m + (n +0n +) = n 4 +0n 3 +04n +40n +4 이므로 M = m +; N = n +0n + 으로치환하면문제의조건은다음의식이된다. M N =(M + N)(M N) = 000 M + N 과 M N 은홀짝이같은데, 우변이짝수이므로둘모두짝수이다. 그러므로 fm + N; M Ng = f; 000g; f4; 500g; f8; 50g; f000g; f0; 00g; f40; 50g 혹은여기에부호를모두음으로바꾼것들이어야한다. N =(n +5) 3 이므로우선 N 3 을만족하는것만고르면 N = (M + N) (M N) =499; 48; ; 95; 40; 5; 5 즉, (n +5) =5; 7; 44; 8; 63; 8; 8 이중 (n +5) 로가능한유일한해는 44 뿐이고, 따라서 N =, 그리고 n = 7 또는 7. 즉, (M + N; M N) =(50; 8) 또는 ( 8; 50) 이고, M = 9. m = 8 또는 30. (m; n) =(8; 7); (8; 7); ( 30; 7); ( 30; 7) } 의마지막세자리를구하여라. ( 캐나다 003-)

34 34 수론 풀이 우선 x y (mod 000) 이다. Á(000) = Á( )=( 3 )(5 3 5 )=400에서페르마-오일러정리의의해 (mod 000) 이므로, y y 0 (mod 400) 즉 y z (mod 5) 이다. 다시, Á(5) = 0 에서 0 (mod5) 이므로 z (mod 0) 이제거꾸로대입해가면 y (mod 5) y 48 (mod 400) x 3 48 (mod 000) 이된다 (mod 000) (mod 000) (mod 000) (mod 000) 이과정을계속하면 (mod 000). 따라서답은 4이다. } 풀이 이항전개를이용하면 3 4n ( 0) n (n)0 n(n ) + 0 0n +00n(n ) (mod 000) 이므로,3 00 (mod 000) 임을알수있다. 이제 (mod 000) 이고, 00? (mod00) 을구해보자. 페르마 - 오일러정리에서 0 = Á(5) (mod 5) 이고 3 (mod 5) 이므로, (mod 5), 00 5 (mod 00) 이다. 그럼 (mod 000) 이된다. 그러므로, 답은 4. } 8. 수열 a k = n k (k =0; ;:::;003) 이다음성질을갖도록하는자연수 n>003 이존재함을증명하여라 : 각각의 0 m; k 003 에대해 m>k 이면 a k 는 a m 을나눈다. ( 폴란드 003 차 -) 증명 n k j n k+ = n k n k+ k 이므로 n k n+ k+ 이항상정수이면, 즉 k+ 이항상정수이면됨. n = 003! 이면충분함 <x<y<z<p 를만족하는소수 p 와정수 x, y, z 가주어져있다. x 3, y 3, z 3 을 p 로나눈나머지가모두같다면, x + y + z 은 x + y + z 로나누어떨어짐을보여라. ( 폴란드 차 -4)

35 . 수론중급문제 35 증명우선 p 5. () p j x + xy + y ;y + yz + z ;z + zx+ x.() 에서둘을빼면 () p j x + y + z 이고,() 의셋을모두더한후 () 를적당히빼면 (3) p j x +y +z. x+y +z <3p 임에서 x+y+z = p 또는 p 인데, p일때는자명하고,p일때도x + y + z 와 x + y + z 의홀짝이같으므로역시자명함. 30. 소수 p, q, r 이있다. p 는 qr 의약수이고, q 는 rp 의약수이고, r 은 pq 의약수라고한다. pqr 의값으로가능한것을모두구하여라. ( 영국 003/004 차 -5) 풀이 ( 경북과학고 학년심영준 ) p q r 이라고하자. 우선아래의세식이문제의조건에서성립해야한다 (k, m, n은정수 ). kp = qr mq = pr nr = pq 3 이제여러가지경우를살펴보자. (i) p 가짝수일때 ( 즉, p = 일때 ), 3 에서, nr =q r < r 이므로, n =. 즉, r =q ᄀ. ᄀ을 에대입하면 mq =(q ), 즉 3=(4 m)q. 여기서 q j 3 이므로 q =3 뿐이다. 그럼, r =5. 따라서, (ii) p 가홀수일때,,, 3 에서 qr p (p; q; r) =(; 3; 5) 이고 pqr =30, pr, pq q r 이모두정수이므로, 셋의곱역시정수이다. (qr )(pr )(pq ) P = pqr = (pqr) pqr(p + q + r)+(pq + qr + pr) pqr 이정수이려면, pq + qr + pr 이정수이면된다. 그런데, p:q:r 3 에서 pqr r ; p ; q 3 이므로 pq + qr + pr pqr = r + p + q pqr < 로이것은정수일수없어서모순. 따라서, p가홀수일때는만족하는 (p; q; r) 이없다. 그러므로가능한 pqr의값은30뿐이다. 답 } 3. (x + 5)(y +7)=p z 을만족하는음이아닌정수 x, y, z 와소수 p 가존재하는지결정하여라. ( 폴란드 003/004 차 -) 풀이 p 6= ; 3 이므로 p 5. p (mod3; 4) 이므로 p (mod). 그럼 x +5 나 y +7 모두 p 의홀수승이어야함. 즉, z 는짝수. 그럼준식은 (mod) 로모순. 즉, 해는없음. } 3. 자연수 m, n 이식 m +n = 37(m n) 을만족시킬때, m + n 의값은얼마인가? ( 한국 004 차 -S3) 풀이좌변이짝수이므로우변도짝수. 즉, m과 n은홀짝이같다. 그럼 m 과 n 도홀짝이같으므로좌변은다시 4의배수이고, 따라서우변의 m n도 4의배수. m = n +4k (4는자연수) 를준식에대입하면 (n +4k) + n = 37 k (n +k) = k(37 4k)

36 36 수론 로정리된다. 좌변이양수이므로우변도양수, 따라서 0 < 4k <37. 그럼 gcd(k; 37 4k) =gcd(k; 37) 은 37 일수없으므로 일수밖에없다. 서로소인두수의곱이완전제곱수이므로둘다각각완전제곱수 k = a,37 4k = b 꼴이어야한다. 4a + b =37 을만족하는경우는 (a ;b )=( ; ) 뿐이다. 따라서, k =4,n =4,m =30 이되고, m + n = 44. } 33. 피보나치수열은 f =0,f =, 그리고 n 에대해 f n+ = f n+ + f n 으로정의된다. 단조증가하는정수들의등차수열중에, 피보나치수를하나도갖지않는것이있음을증명하여라. ( 북유럽 004-) 증명 f n 은순환잉여수열. 적당한 m에대해mod m으로나타나지않는것이있으면충분. 즉,k+4, 6, 7 등. 34. n 0 + n 5 + 이소수인자연수 n 을모두구하여라. ( 오폴 004-4) 풀이 n 0 + n 5 +=(n + n +)(n 8 n 7 + n 5 n 4 + n 3 n +) 인수분해이용. } 35. 정확히 p n 개의양의약수를갖는자연수 n 을모두찾아라. ( 폴란드 004 차 -4) 풀이 n은제곱수, 또홀수. p n = m =k + 으로두자. m보다작은약수와 m보다큰약수가쌍을이루므로각각 k개씩인데, m보다작은홀수도 k개이므로그것들이모두약수. 특히 k j (k +) 에주목하면 k j 4, 즉 k =0;. 고로 n =; 9뿐. } 36. 방정식 n(m + n ) m(m + n +47) = 0 을만족시키는자연수쌍 (m; n) 의집합을 A = f (m i ;n i ) j i =; ;:::;kg 라할때m + m + + m k 의값은? ( 한국 005 차-S7) 풀이 ( 대전전민중 3학년정명진, 수정됨 ) n(m + n ) = m(m + n +47) 에서모든인수가양수이고 m + n <m + n +47 이므로 n>m이어야한다. n = m + k 라두자 (k ). (m + k)(m + n ) = m(m + n +47) m + km + kn k =47m km +k m + k 3 k =48m km +(k 4)m + k(k ) =0 k 4 이면 ( 좌변 ) 4m 8m +30> 8(m ) 0 으로성립하지않는다. 따라서, k =; ; 3 만가능. ² k =이면 ; m 3m =0. ) m =3. ² k =이면 ; 좌변이홀수이므로모순. ² k =3이면 ;3m 5m +=0. (m )(m 4) = 0. ) m =; 4. 따라서, 가능한 m은, 4, 3뿐이고,+4+3=8 답 } 주이외에몇몇학생이제출한풀이에서는, km +(k 4)m + k(k ) = 0 에서이식의정수해를가져야하므로근과계수와의관계를이용, k 4 k 와 (k ) 이정수여야한다고주장하며풀이를쓴사례가있었다. 그러나, 정수해를갖는것과두근이모두정수라는것은다른얘기이므로이런풀이는직접성립하지않는다. 37. 이차방정식 (bc )x +(a b + c abc)x + ab =0 이정수근을갖도록하는한자리의자연수 a, b, c 에대하여 00a +0b + c 의최대값을구하여라. ( 한국 005 차 -S7)

37 . 수론중급문제 37 풀이 ( 제주과학고 학년강진호, 수정됨 ) 정수계수이차방정식이므로정수근을갖는다면판별식이완전제곱수라야한다. D =(a b + c abc) 4(bc )(ab ) = a b c abc(a + b + c)+(a + b + c )+(ab + bc + ca) 4 =(abc) (abc)(a + b + c)+(a + b + c) 4 =(a + b + c abc) 4=m 즉,(a + b + c abc) m =4 이다. 완전제곱수들 0,, 4, 9, 6, ::: 의분포를관찰하면두완전제곱수의차가 4 가되는경우는 4 0 일때뿐이다. 따라서, m =0 이고 a + b + c abc = ( ) 이다. 그럼 a(bc ) = b + c, 즉 bc j b + c 이다. b + c =0 일때는 bc =0 이기도하므로, bc b + c 이항상성립한다. 즉, 이다.( ) 은대칭식이므로, 마찬가지로 (b )(c ) 4 (a )(b ) 4; (a )(c ) 4 이기도하다. a>5 이면 b = c = 이어야하므로문제의식에서최고차항이 0 이되어이차방정식이아니므로곤란하다. a =5 일때는 b ;c 이고, 이경우 (a; b; c) =(5; ; ) 또는 (5; ; ) 일때 ( ) 이만족된다.(a; b; c) =(5; ; ) 일때문제의방정식은 x 6x +9=0 으로 x =3 의정수근을갖는다. 따라서, 00a +0b + c 의최대값은 5 이다. } 38. 어떤적당한서로소인자연수 a, b 에대하여, a + b 와 a005 + b 005 모두구하여라. a + b 의최대공약수가될수있는정수를 ( 한국 005-S) 풀이 a b 005 a + b = a 004 a 003 b + a 00 b ab b 004 =(a + b)(a 003 a 00 b +3a 00 b 004b 003 ) + 005b 004 이다. 이것과 gcd(a + b; b 004 )= 임으로부터 d =gcd µa + b; a005 + b 005 =gcd(a + b; 005b 004 )=gcd(a + b; 005) a + b 따라서, d =, 5, 40, 005 만가능하다. 그리고, 이각각의경우에대해 (a; b; d) =(5; ; ); (3; ; 5); (00; 0; 40); (; 003; 005) 의실제예가존재한다. 답, 5, 40, 005 } 39. 다음을만족하는함수 f : Z Z! R 을모두구하여라. (i) 임의의정수 x; y; z에대해f(x; y) f(y; z) f(z;x) =. (ii) 임의의정수 x에대해f(x +;x)=. ( 루마니아 005 지역예선 y0-)

38 38 수론 풀이 ( 대전과학고 학년송지용 ) (i) 에서 y; z 에모두 x 를대입하면 f(x; x) 3 =, 즉 다시 (i) 에서 z 에 x 를대입하고 f(x; x) 를소거하면 f(x; x) = f(x; y)f(y; x) = 이로부터,(i) 의양변에 f(x; z) 를곱하면다음의관계식을얻을수있다. 이로부터, x>y 일때 f(x; y)f(y; z) =f(x; z) f(x; y) =f(x; x )f(x ;y) = = f(x; x )f(x ;x ) f(y +;y) = = {z } x y x y 개 와같이분해하여계산할수있다. 또한, 앞의성질들에의해이것은 x = y, x<y 일때도성립함을확인할수있다. 따라서, 답은 f(x; y) = x y. } 40. x 는정수이고 y, z, w 는양의홀수들이다. x yzw x yz 가 7 로나누어떨어짐을증명하여라. ( 아일랜드 005-8) 증명 x 7 x (mod 7) 이므로 y zw y z (mod 6) 임을보이면충분. 이것은또 z w z (mod 8) 이면충분. z (mod) 이므로이것은당연. 4. 다음을만족하는최소의자연수 a 를구하여라 : a p a p 을만족하는소수 p 와자연수 b 가존재한다. ( 오폴 005-4) 풀이 a p a = a(a p ). gcd(a; a p ) =. gcd(a; p) =일때와그렇지않을때로나눠서풀자. () gcd(a; p) =일때 : 페르마소정리에의해 p j a p 이므로 a = A, a p =pb 꼴. A (p ) =(A p +)(A p ) = pb. p j A p 이므로 (A p +;A p ) = (x ;py ) 꼴 (i) 또는 (x ; py ) 꼴 (ii) 이다.(i) 의경우 : p가홀수이면 A p +=x 이양의제곱수에 을더했더니다시제곱수가되는꼴이라성립할수없고, 따라서 p =. A =B 의가장작은해는 (A; B) =(3; ) 이므로 a =9가이경우의최소이고, p =,b =6의해가실제로존재한다.(ii) 의경우 : 이경우는 A가홀수일때만생기므로, A 3 이라서어차피 a 9 가되어 (i) 에서얻은것보다 a가더작은경우는없다.()gcd(a; p) =a 일때 : a = pk 라하자. k((pk) p ) = b 에서두인수가서로소이므로 k = A,(pk) p =B 꼴. 여기서 p가홀수이면뒷식이제곱수에서 을뺐더니양의제곱수가되는꼴이라곤란하고, 따라서 p =. A =B 의가장작은해는 (A; B) =(; ) 인데이것은 b =이되어문제의조건에위배되고, 그다음해는 (A; B) =(5; 7) 인데이것은 (i) 에서구한것보다훨씬해가커진다. 답 9 } = b 4. n n +과 (n) n +이둘다소수가되게하는자연수 n을모두구하여라. ( 폴란드 005 차-) 풀이 n이홀수인소인수를가지면 n n + 이인수분해되어곤란. 즉, n = m 꼴. 그럼 n n + = m m + 임에서 m도홀수인소인수를가지면곤란. 즉, n =또는 n = k 꼴. 그럼 (n) n += (k +) k + +에서 k 이면또끝. 즉 n =; 일때만가능하고둘다 ok. }

39 . 수론중급문제 n +05 가완전제곱수가되는음이아닌정수 n 을모두구하여라. ( 폴란드 005/006 차 -) 풀이 mod 3으로보면 n은짝수. n =m 이라하고 m +05=x 이라하면 (x + m )(x m )= 05 = 경우나눠풀면 답 n =4; 6. } 보다큰소수 p 와자연수 a, b, c 가 a + b + c = p + 을만족하고, a 3 + b 3 + c 3 은 p 로나누어떨어진다. a, b, c 중에 인것이있음을증명하여라. ( 폴란드 005/006 차 -7) 증명 a 3 +b 3 +c 3 (a+b+c)((a+b+c) 3(ab+bc+ca)) +3abc 3abc 3(ab+bc+ac) 3(abc (ab + bc + ca)+(a + b + c) ) = 3(a )(b )(c ) (mod p). 45. 세자연수 a, b, c 에대하여,gcd(a; b; c) = 이고 a + b + c =(ab + bc + ca) 일때, a, b, c 가모두완전제곱수임을보여라. ( 한국 006-3) 증명 ( 서울중산고 학년최서준 ) a + b + c =(ab + bc + ca) () a (b + c)a +(b c) =0 a 는자연수이므로판별식은제곱수여야한다. D 4 =(b + c) (b c) =4bc = k (k 는정수 ) 여기서 bc 도제곱수임을알수있다. 이제 b, c 가서로소임을보이면충분하다. b 와 c 의공통소인수 p 가존재한다고하자. 원식에대입하면 p 는 a 을나눈다. p 가소수이므로 p 는 a 를나눈다. 이것은 gcd(a; b; c) = 에모순. 따라서 b, c 의공통소인수는없고, 즉 b 와 c 는서로소이며, bc 가제곱수이므로 b, c 모두각각제곱수이다. 문제는 a, b, c 에대해대칭적이므로, 같은방법으로 a, c 도모두제곱수라는결론을내릴수있고, 따라서 a, b, c 는모두제곱수이다. 46. n = 006 일때다음방정식의정수해 x, y, z 가존재하는가? z =(x +)(y ) + n n = 007 일때는어떤가? ( 아일랜드 006-) 풀이 n = 006 일때는 (x; y; z) =(4; 6; 5) 등의해가존재한다. n =007일때는mod 8로해보면해가없음을확인할수있다. } 47. 자연수 a, b, c, x, y, z 가다음을만족한다. a + b = c ; x + y = z ; jx aj ; jy bj 집합 fa; bg 와 fx; yg 가같음을보여라. ( 폴란드 006 차 -) 증명 (a; b) 6= (x; y) 라하자.WLOGjx aj =,WLOGx = a+. y = b 이면 z = a +a++b = c +a + 인데, c>a 이므로이것은 c <z < (c +) 임을의미하여모순. y = b + 일때도비슷하게좀해보면 (c +) <z < (c +) 로모순. y = b 일때만보면됨. c z =(a + b )(x + y ) (ax + by) 이므로 cz ax + by. (c z) = c cz + z (a ax + x )+(b by + y ). 즉, jc zj. 막노동좀하면확인은되는데막노동피하고깔끔하게끝내는방법이없나 k +4m 과 m +5k 가모두완전제곱수가되는자연수쌍 (k; m) 을모두구하여라. ( 폴란드 006/007 차 -) 풀이 A := k +4m>k 이고 A 6= (k +) 이니까 (4m과 k +을홀짝이달라서 ), A (k +), 즉 m k +. 그럼 m <B:= m +5k<m +5m<(m +3) 이니까 B =(m +) 또는 (m +). 즉,5k =m + 또는 5k =4m +4. 전자일때 A = k +0k < (k +5) 이고, A =(k +) ; (k +3) ; (k +4) 일때각각풀어보면됨. 후자일때 A = k +5k 4 < (k +3) 이고, A =(k +) 일때만풀어보면됨. 답 (,), (8,9), (9,) }