정수론의 기반 수학적 귀납법의 원리 Nottion 1.1 N = {1,, 3,...} = 자연수 전체의 집합 Z = {...,, 1, 0, 1,,...} = 정수 전체의 집합 Q = { b, b Z, b 6= 0} = 유리수 전체의 집합 R = {limn n

Transcription

1 정수론 정주희경북대학교수학교육과 018년 11월 3일 차례 1 정수론의기반 1.1 수학적귀납법의원리 약수와배수 최대공약수와최소공배수 소수와소인수분해 부정방정식과합동식 14.1 부정방정식 합동식 완전잉여계 페르마의정리와오일러의정리 페르마의정리와윌슨의정리 오일러의정리 원시근과이산로그 위수와원시근 이산로그 원시근정리 차잉여 차합동식 제곱수판정, 오일러와르장드르 차잉여의상호법칙 연분수 연분수와근사분수 제곱근의연분수 펠방정식 찾아보기 45 1

2 정수론의 기반 수학적 귀납법의 원리 Nottion 1.1 N = {1,, 3,...} = 자연수 전체의 집합 Z = {...,, 1, 0, 1,,...} = 정수 전체의 집합 Q = { b, b Z, b 6= 0} = 유리수 전체의 집합 R = {limn n (i )i 는 유리수의 수열} = 실수 전체의 집합 C = { + ib, b R} = 복소수 전체의 집합 (i = 1) Q: 확장된 수의 체계는 방정식의 해를 추가함으로써 얻어지는가? 각 수의 체계들은 어떤 연 산에 의하여 닫혀있는가? (사칙연산과 극한) 이 책에서는 표기법 Zn = {0, 1,..., n 1}을 사용한다. Definition 1. 실수의 최소상계성질(lest upperbound property): 공아닌 실수들의 집합 S의 상계가 존재하면 최소상계 sup S가 존재한다. Theorem 1.3 (정수의 정렬성, p:정리 1.) 정수들로 이루어진 공아닌 집합 S에 하계가 존 재하면 S는 최소원을 가진다. 자연수들로 이루어진 공아닌 집합은 최소원을 가진다. Theorem 1.4 (실수의 아르키메데스 성질) (, b R) > 0 ( n N)(n > b) Proof. 실수의 최소상계 성질을 이용한다. Remrk 1.5 아르키메데스 성질이 정수론에서 쓰이는 대표적인 예를 아래에 보였다. ( x R)( 1 n Z)(n x < n + 1) (1.1) Theorem 1.6 (수학적 귀납법의 원리, p3:정리 1.4)) S N이 (i) 1 S, (ii) ( n N)(n S (n + 1) S) 를 만족하면 S = N이다. Proof. S c = N S = 6 를 가정하고 모순을 유도한다. 정수의 정렬성에 의하여 S c 6= 의 최소원 m이 존재할 것이다. m 6= 1이므로 m 1 N이다. m의 최소성에 의하여 m 1 S 이다. (ii)의 n에 m 1을 대입하면 m S를 얻게 된다. 이것은 실은 정리가 아니라 공리(xiom)로 보는 것이 맞다. See Remrk 1.8. 교과서에는, b N으로 되어 있지만 아르키메데스 성질은 원래 실수에 대한 것임.

3 Theorem 1.7 (완전 귀납법의 원리(Principle of Complete Induction)) S N이 (i) 1 S, (ii) ( n N)({1,..., n} S (n + 1) S) 를 만족하면 S = N이다. Proof. 정리 1.6의 증명을 흉내낸다. Remrk 1.8 완전 귀납법을 사용해서 증명하는 대표적인 예로 정리 1.63이 있다. (또는 p69: 5.1, 또는 p83: 6.1) 정수의 정렬성, 수학적 귀납법의 원리, 완전 귀납법의 원리는 모두 서로 동등하다. 이 책에 서는 정수의 정렬성으로부터 나머지 두 원리를 증명하였는데, 책에 따라서 수학적 귀납법의 원리를 공리로 삼고, 이로부터 출발하여 정수의 정렬성을 증명하기도 한다. 책의 p:정리 1.에서 정수의 정렬성을 증명하였는데, 이 증명에서 유한집합은 최소원을 가진다. 는 사실을 사용했다. 이 사실 은 수학적 귀납법의 원리로부터 증명되는 정리 로 볼 수도 있으며, 증명과정에서 유한집합에 대한 엄격한 정의를 필요로 한다. Fct 1.9 아래의 명제들은 모두 수학적 귀납법의 원리와 동등하다. 단, (1), ()에서 k Z 이고 k = {n Z n k}이다. (1) S Z이 (i) k S와 (ii) ( n k)(n S (n + 1) S)를 만족하면 k S이다. () S Z이 (i) 1 S와 (ii) ( n S) {n, n + 1} S 를 만족하면 N S이다. 앞으로 모든 변수는 별도의 언급이 없다면 정수를 나타낸다. 1. 약수와 배수 Definition 1.10 (p43) 두 정수 6= 0, b Z가 ( k Z)(b = k) 를 만족할 때 를 b의 약수, b를 의 배수라 하고 b 로 나타낸다. 그렇지 않을 때는 6 b로 나타낸다. Remrk 1.11 정의에 의하여 0은 어떤 수의 약수도 아니다. 즉 0을 약수로 가지는 정수는 존재하지 않는다. 한편 0은 0을 제외한 모든 수의 배수이다. 0은 0의 약수가 아니다. Theorem 1.1 약수의 약수는 약수이다. 배수의 배수는 배수이다. 배수들의 선형조합은 배수이다. (배선배의 법칙) 즉, b1,..., bn 이 모두 의 배수라면 이 들의 임의의 선형조합(liner combintion) k1 b1 + + kn bn 도 의 배수이다. 3

4 Proof. (1) b, b c이면 c = m 1 b = m 1 (m ) = (m 1 m ) () 생략 (3) b i = m i, i = 1,..., n이면 k 1 b k n b n = (k 1 m k n m n ) Theorem 1.13 ( 나눗셈알고리듬 (Division Algorithm), p5: 정리 1.6) ( )( b 0)( 1 q)( 1 r)( = qb + r nd 0 r < b ) (1.) q = quotient, 몫 r = reminder, 나머지, %b, [] b (p106) (b 는 b 0 %b = 0를의미함을알수있다.) Proof. 존재성은정수의정렬성을이용하여증명한다. 유일성을증명할때는 ( x, y 0) ( x y mx(x, y) ) 를이용한다. (P (x) 가참인 x 의유일성을증명하려면 ( x 1, x )(P (x 1 ) P (x ) x 1 = x ) 를보인다.) Exercise %( 5) 와 ( 13)%( 5) 를각각계산하여라. 각경우의몫도계산하여라. Fct 1.15 (p43, 정리 3.1) (1) ( (±1 ) ( 0 ± ± 0) ) () ( )( b 0)( b b ) ( ) (3) ( )( b) ( b) ( > b ) (b = 0) ( (n ) ) (4) ( n)( b, c Z n ) (b c) (b = c) (5) b ( ( b) (b ) = ±b ) (6) ( ± 1 = ±1) Nottion 1.16 x R 에대하여 x 는 x 이하의정수중가장큰것을뜻하고, x 는 x 이 상의정수중가장작은것을뜻한다. ( 흔히 x 대신 가우스기호 [x] 를사용한다.) x 는 floor of x 로읽고 x 는 ceiling of x 로읽는다. ( 엄격히말하자면여기서아르키메데스의 원리가필요하다.) Exercise 1.17 다음사실들을증명하여라. 단 x, y R 이다. (i) x x < x + 1, (ii) x y x y (p6) (iii) Z x + = x + (iv) x + y x + y x + y + 1 (p9: #1) 흔히 lgorithm 을 알고리듬 이아니라 알고리즘 으로쓰는데이것은마치 rhythm 을 리즘, mother 를 마저 라고쓰는것과같다. Algorism 이라고하는, lgorithm 과는의미가다른단어가있는데이것을 알고리즘 이라고쓰면된다. 위키피디아에서알고리듬과알고리즘의차이를검색해보라. 조금다른얘기지만, query 를 쿼리 라고쓰고또이럴게발음하는사람들이많은데이것은 퀴리, 또는 퀴어리 라고해야맞다. 쿼리는 qurry, 즉사냥감, 또는채석장을뜻하는단어이다. 4

5 (v) ( x R + )( n N) ( {nk N nk x} = x/n ) (p7: 정리 1.8) Exercise 1.18 b 1 일때 %b = b /b 임을보여라. ( 힌트 : p6: 정리 1.7) Exercise 1.19 b 1일때 를 b로나눈몫은 (1) b 일때는 ( 몫 = /b = /b ) 이고, () 그렇지않을때는 ( 몫 = /b + 1) 임을보여라. ( 힌트 : n Z, x R일때 n x < n + 1 n = x 임을보인다.) Lemm 1.0 (p7: 1.8) x R + 와 n N에대하여 x 이하의자연수증 n의배수의개수는 x/n 이다. Proof. x/n n x < ( x/n + 1)n이므로 kn x인최대의 k는 x/n 이다. Exercise 1.1 x y R일때 x 이상 y 이하의자연수중에 n의배수의개수는어떻게구하면되겠는가? Exercise 1. p9: #11, #14 #17 Exercise 1.3 연이은 n 개의자연수의곱 m(m + 1) (m + n 1) 은 n! 의배수임을증명하 여라. (p9: #13) Discussion. 다음의명제를생각해보자. 연이은 n 개의수 m, m + 1,..., m + n 1 에는 각 k = 1,,..., n 에대해서 k 의배수가적어도하나들어있다. ( ) k n을고정하고생각한다. m%k = r로두었을때, 즉 m = qk + r, 0 r < k로두었을때 r = 0이면 ( ) 는당연히성립한다. r > 0인경우에는 r = k 1, k,..., 1인경우들에대해서차례로생각해보자. r = k 1 경우 : m = qk + (k 1) 이므로 (m + 1)%k = 0. 따라서 ( ) 성립. r = k 경우 : m = qk + (k ) 이므로 (m + )%k = 0. 따라서 ( ) 성립. r = k i (i n 1) 경우 : m = qk + (k i) 이므로 (m + i)%k = 0. 따라서 ( ) 성립. 이로써 ( ) 는항상성립함을알수있다. 모든 k = 1,,..., n에대해서 k의배수임 은 n! 의배수임 의필요충분조건이라면이제이문제는풀린것이다. 그러나전자는후자의필요조건이기는하지만충분조건은아니다. 예를들어 1는 1,,3,4의배수이지만 4! 의배수가아니다. 다른방법을생각해보자. m(m + 1) (m + n 1) = m+n 1 P n = m+n 1 C n n! ( 대단히쉽다.) Definition 1.4 (p34) q가 이상의자연수이고 N N일때어떤 n 0에대해서 N = n q n + 1 q + 0, 0 i < q (1.3) 가성립한다면 n n (q) 를 N의 q진법표현이라고한다. 5

6 x R + 일때 x = n q n + 1 q q 1 + q +, 0 i < q (1.4) 가성립한다면 ( n n ) (q) 를 x의 q진법표현이라고한다. 음수의 q-진법표현은그것의절댓값의 q진법표현의앞에 를더한것이다. 0의 q진법표현은 0이다. Fct 1.5 (1.3) 과 (1.4) 를만족하는 ( i ) i 는항상유일하게존재한다. 이사실은나눗셈알고리듬을사용하여증명할수있다. 나눗셈알고리듬을사용하지않고도 n = N/q n 등을증명할수있을것이다. Exmple 1.6 ( 진법변환 #1, p34) Exmple 1.7 ( 진법변환 #, p37) 9 3 = 9 + 3을 5진법으로나타내어보자. 정수부분 9의 5 진법표현 14는쉽게구할수있을것이다. 3 = , 0 i < 5 (1.5) 를만족하는 i 들을구해야한다. 1 은 (1.5) 의양변에 5 를곱했을때의정수부분이다. 계산해 보면 10 3 = = , 0 i < 5 1 = 3 이다. 다시양변에 5 를곱하면 = 1 임을알수있다. 그리고 3 = , 0 i < 5 를얻게되는데이것은 (1.5) 와같다. 따라서앞으로는 로이어질것이다. 따라서 9 3 = (5) 이다. Exercise 1.8 p41: #5, #7 6

7 1.3 최대공약수와최소공배수 Definition 1.9 정수, b 의최대공약수 (gretest common divisor) 는 의약수인동시에 b 의약 수인수 ( 즉, 공약수 ) 중에서가장큰수를뜻하며 gcd(, b) 로나타낸다. 정수, b 의최소공배수 (lest common multiple) 는 의배수인동시에 b 의배수인자연수 ( 즉, 양의공배수 ) 중에서가장작은 수를뜻하며 lcm(, b) 로나타낸다. gcd(, b) = c lcm(, b) = c ( (c ) (c b) ( x) ( (x ) (x b) c x )) ( (c > 0) ( c) (b c) ( x > 0) ( ( x) (b x) c x )) Fct 1.30 gcd 와 lcm 에는교환법칙이성립한다. 즉, gcd(, b) = gcd(b, ), lcm(, b) = lcm(b, ) Fct 은 (0 을제외한 ) 모든수를약수로가지며 0 의배수는존재하지않으므로, gcd(0, 0) : 존재하지않음 gcd(0, ) : ( 0 경우 ) lcm(0, ) : 존재하지않음 Fct 1.3 gcd(, k) =, for > 0 gcd(, b) = gcd(±, ±b), lcm(, b) = lcm(±, ±b) Theorem 1.33 (p46:3.3), b 의최대공약수는이둘의선형조합으로서양수인것들중에가 장작은것이다. gcd(, b) = min ( L(, b) N ), L(, b) = {x + by x, y Z}. where Proof. 위식의우변이하나의자연수를규정함은정수의정렬성에의하여보장된다. ( (x, y) = (, b) (0, 0) 일때 x+by = +b N.) 나눗셈알고리듬과 g = gcd(, b) 의최소성에의하여 g 가 의약수이고또한 b 의약수임을보인다., b 의임의의공약수 k 는배선배의법칙에의하여 L(, b) 의모든원소의약수이므로 g 의 약수이다. 따라서 k g = g 이다. Remrk 1.34 (p49: 3.10) 위의정리의증명에서최대공약수는모든공약수의상계일뿐만 아니라배수임을보였다. Exercise 1.35 (p49: 3.10) 최소공배수는모든공배수의약수임을증명하시오. ( 정리 1.33 을 사용할필요가없다.) 7

8 Fct 1.36 (p47) (, b) (0, 0) 이고 k > 0 일때 gcd(k, kb) = k gcd(, b) Exercise 1.37 (p47: 3.5), b 의임의의선형조합은 gcd(, b) 의배수이며역으로 gcd(, b) 의 임의의배수는, b 의선형조합임을보이시오. Definition 1.38 (p47) gcd(, b) = 1 일때 와 b 는서로소 (reltively prime) 라한다. (1 은모든 정수와서로소임. 자기자신과도서로소임.) Lemm 1.39 (p47: 3.6) 모든, b Z 에대하여 gcd(, b) = 1 ( x, y Z)(x + by = 1) 가성립한다. Proof. Trivil. Remrk 1.40 아래의명제는일반적으로참이아니다. (d = 1 일때만참이다.) gcd(, b) = d ( x, y Z)(x + by = d) 은항상참이다. Lemm 1.41 gcd(, b) = g 이고 k > 0, k g 이면 ( gcd k, b ) = g k k. Proof. Fct 1.36 의증명을흉내내면된다. Exercise 1.4 (p48) 가무리수임을증명하시오. (가지방법이있다. 책에있는증명은 가정수가아님을보이는부분이 ( 물론이를보이기는쉽지만 ) 추가되어야한다.) Theorem 1.43 ( 서로소보조정리, p48: 3.8, 3.9) gcd(, b) = 1 이면모든 k Z 에대하여 (i) ( k) (b k) b k, (ii) bk k ( 유클리드의레마 ) Proof. p48 (i), (ii) 모두 k = k 1 = k(x + by) 로둔다. Exercise 1.44 위의정리 1.43 의역을증명하여라. Lemm 1.45 (p49: 3.11), b > 0 이면 gcd(, b) lcm(, b) = b 이다. Proof. 소인수분해를사용하면쉽다. Lemm 1.46 (p55: 4.1) 모든 b > 0, q Z 에대하여 gcd(, b) = gcd( bq, b) (1.6) 8

9 Proof. L( bq, b) = L(, b)임을 보인다. Remrk 1.47 위의 보조정리는 선형대수학에서 Spn(~, ~b) = Spn(~ q~b, ~b)가 성립하는 것과 비슷하다. 그런데 가정 b > 0는 꼭 필요했나? Theorem 1.48 (p56: 4.3, 유클리드 알고리듬) b > 0인 경우에 gcd(, b)를 다음과 같은 방법으로 구할 수 있다. 0 bk < b가 되도록 k(몫, b/bc)를 취한 다음 b를 로 renme하고 kb(나머지, %b)를 b로 renme하기를 반복하여 나머지가 0이 되도록 한다. 이때의 가 최대공약수이다. (유클리드 알고리듬은 호제법이라고도 한다.) Proof. gcd(, b) = gcd( ± bk, b) = gcd(b, ± bk)를 이용하면 gcd(, b) = gcd(b, %b)임을 알 수 있다. 수학적 귀납법을 수행한다. 그리고 > 0 gcd(, 0) = 를 이용한다. Exercise 1.49 p5: #3 #6, #7(어려움, (3)에 오타 있음), #10, #16, #18 유클리드 알고리듬을 더 정교하게 다음으면 최대공약수 뿐만 아니라 이것을 와 b의 선형조 합으로 나타낼 때의 계수까지도 구할 수 있다. Remrk 1.50 (p57) b > 0인 경우에 gcd(, b) = x + by인 x, y를 구하는 알고리듬을 아래에 소개한다. (확장된 유클리드 알고리듬) till 주어진 두 자연수 358과 189의 최대공약수를 구하고 이를 이 두 수의 선형조합으로 나타내고 re 자 한다. 둘 중 큰 수를, 작은 수를 그리고 re 다음과 같이 초기화하여 시작한다. 0 b로 가둔다. 세로 r 1 =, r0 = b x 1 = 1, x0 = 0 gud Lb y 1 = 0, y0 = 1 이제 각 k = 1,,...에 대하여 다음과 같이 진행한다. gcd b 인 이유 gcdl bk.d.tk ke L 의미로 수면 te go.dk b qk = brk /rk 1 c rk = rk %rk 1 xk = xk qk xk 1 yk = yk qk yk 1 ut byte kilo 일때 me t 9bye clc r 인 이유 一一 t 기 ki 기 GePl b bd

10 r k = 0 가될때까지진행하면 d = r k 1, x = x k 1, y = y k 1 로두었을때 d = gcd(, b) = x + by 가된다. ( 혹시 r k 1 = 1 에도달하게된다면여기서멈추어도된다. 왜냐하면이경우 r k = 0 가보장되기때문이다.) Exercise 1.51 위의알고리듬이작동하는이유를설명하여라. ( 힌트 : k = 1, 0, 1,... 에대한 수학적귀납법을사용하여 x k + by k = r k 를보인다. x k+1 + by k+1 = (x k 1 q k+1 x k ) + b(y k 1 q k+1 y k ) = x k 1 + by k 1 q k+1 (x k + by k ) = r k 1 q k+1 r k = r k 1 %r k ) Exercise 1.5 p66 #(p50: 3.1), #4( 오타있음. n ), #5( 같은오타 ) 1.4 소수와소인수분해 Definition 1.53 (p69) 소수 (prime number) 는 1과자기자신외에는양의약수가없는 이상의자연수이다. 소수인약수를소인수 (prime fctor) 라한다. 정수를소인수들의곱으로표현한것을그정수의소인수분해 (prime fctoriztion) 라한다. 소수가아닌 이상의정수를합성수 (composite number) 라한다. Fct 1.54 n 이합성수라면그것은 n 이하의소인수를가진다. 자연수는합성수이면이자 신보다작은자연수들만의곱으로표시된다. Theorem 1.55 (Euclid, p71: 5.) 소수는무한히많다. Proof. 모든소수들을 p 1 < p < < p n 으로나열할수있다고가정하고 N = p 1 p p n + 1 으로놓았을때 p i N 임으로부터모순을유도한다. Remrk 1.56 모든소수들을크기순으로나열하여 (p i ) i=1 로두었을때 q n = p 1 p p n + 1 이라하면 q 1,..., q 5 는소수이지만 q 6 = = 는소수가아니다. n p n q n Definition 1.57 (p75) M n 메르센소수라한다. = n 1 형태의수를메르센수라하고, 소수인메르센수를 Lemm 1.58 (p75: 5.6) k, n N 이 k n 을만족하면 ( k 1) ( n 1) 이다. Proof. Wlog q = n k > 1 라하자. k = x 로두면 n 1 = kq 1 = (x q 1) = (x 1)(x (q 1) + x (q ) + + x + 1) 이므로 ( k 1) = (x 1) ( n 1) 가성립한다. Theorem 1.59 (p75: 5.7) 메르센수 n 1 이소수이면 n 도소수이다. Proof. n 1 이소수이면 n 이므로, n 이소수가아니라면 n = kq, 1 < k, q < n 인 k, q N 이존재한다. 그러면 n 1 = kq 1 은합성수가된다. 음의정수의소인수분해는그것의절댓값의소인수분해에 1 을곱한것이다. 1 이하의정수는소수도아니고합성수도아니다. 이상의정수는소수와합성수둘중하나이다. 10

11 n Definition 1.60 (p77) Fn = + 1 형태의 수를 페르마 수라고 한다. 소수인 페르마 수를 페르마 소수라고 한다. Theorem 1.61 (p77) m + 1이 소수이면 m = n 꼴이다. 즉, m + 1은 페르마 소수이다. Proof. 임의의 자연수 m은 ( 1 n, k N) (m = n k) (k는 홀수) 를 만족한다. 이때 만일 k > 1 n 이라면 = x로 두었을 때 n k m + 1 = + 1 = xk + 1 = (x + 1)(xk 1 xk + x + 1) 이므로 m + 1은 소수가 아니다. 따라서 m + 1이 소수라면 k = 1이어야 한다. 즉, m = n 꼴이다. Lemm 1.6 (소수 보조정리, p84) p가 소수이면 다음이 성립한다. gcd(p, ) 6= 1 p (1.7) p b p or p b (1.8) Proof. (1.7)은 대단히 쉽다. (1.8)은 (1.7)과 유클리드의 레마를 이용하면 금방 얻어진다. Theorem 1.63 (산술의 기본정리(The Fundmentl Theorem of Arithmetic), p83: 6.1, p85: 6.4) 임의의 이상의 자연수 n은 아래의 형식을 취했을 때 유일한 방법으로 소인수분해 된다. n = pe11... pemm (p1 < p < < pm re primes, ei 1) (1.9) Proof. n이 소수들의 곱으로 표현됨은 완전귀납법을 사용하여 증명한다. 유일성은 레마 1.6(1.8)을 이용하여 증명한다. 이때 최소반례를 사용하면 좋다. Definition 1.64 (1.9)와 같은 형식의 소인수분해를 표준형 소인수분해라고 하고, (1.10)과 같 은 형식의 소인수분해를 확장표준형 소인수분해라고 한다. Nottion 1.65 (p86) p가 소수일 때, 자연수 pr n인 최대의 자연수 r을 εp (n)으로 나타낸다. pr 을 n의 p 성분이라고 한다. Fct 1.66 (p88) 양의 정수 n이 완전제곱수일 필요충분조건은 임의의 소수 p에 대하여 εp (n) 이 짝수일 것이다. (n = mk 일 필요충분조건은?) Exercise 1.67 (p 1)!은 p와 서로소임을 보여라. (힌트: 레마 1.6 사용.) Exercise 1.68 p80: #, #3 Fct 1.69 (1) 두 수가 서로소라는 것은 두 수가 공통 소인수를 가지지 않는다는 것을 의미한다. () 1,..., m 이 모두 각각 n과 서로소이면 이들의 곱 1 m 도 n과 서로소이다. (3) b 와 b를 소인수분해 했을 때 의 각 소인수 p 의 지수가 b 의 p의 지수 이하 이다. (p89: 6.9) 11

12 (4) b n b n Fct 1.70 (p90: 6.10) 두자연수, b 가아래와같이소인수분해된다면, =p e pem m nd b = p f pfm m, p 1 < p < < p m re primes nd e i, f i 0 (1.10) 이두자연수의최대공약수와최소공배수는다음과같이얻어진다. gcd(, b) = p min(e 1,f 1 ) 1... p min(em,fm) m, lcm(, b) = p mx(e 1,f 1 ) 1... p mx(em,fm) m. Exercise 1.71 gcd(, b) lcm(, b) = b 를증명하여라. Fct 1.7 (p9, p94) 자연수 n 의소인수분해 n = p e pem m (p 1 < p < < p m, e i 1) 로부터 n 의양의약수의개수 τ(n) 과이들의합 σ(n) 을얻을수있다. 우선아래의사실을 쉽게확인할수있다. τ(p n ) = n + 1 σ(p n ) = 1 + p + + p n = pn+1 1 p 1 n 의소인수가여러개있는경우에는아래의정리 1.74 를활용하면 τ(n) 과 σ(n) 의식이얻어 진다. Definition 1.73 (p9) gcd(n, m) = 1 f(nm) = f(n)f(m) 을만족하는함수 f : N R 를 승법적 (multiplictive) 이라고한다. Theorem 1.74 τ 와 σ 는승법적이다. Proof. (p90: 6.11) 은다음과같다 : gcd(m, n) = 1 인경우 m 의약수전체의집합을 {x 1,..., x r }, n 의약수전체의집합을 {y 1,..., y s } 라하면, mn 의약수전체의집합은아래의행렬로나타 난다. (See Fct 1.69.(3).) x 1 y 1 x 1 y x 1 y s x y 1 x y x y s x r y 1 x r y x r y s 게다가이행렬의성분들은모두서로다르다. 이것은표준형소인수분해가 p m 1 1 pm p mr r 인수의모든약수들의집합은 {p e 1 1 pe per r 0 e i m i, 1 i r} 1

13 가된다는사실로부터보일수있다. (See Fct 1.69.(3).) τ와 σ가승법적임은이보조정리를사용하여어렵지않게증명된다. Definition 1.75 (p95) 어떤자연수가자신을제외한양의약수들의합과같을때그자연수를완전수라한다. Theorem 1.76 짝수 n이완전수일필요충분조건으로 ( r ) ( n = r 1 ( r 1) = r 1 ) M r 이있다. Proof. p96: 6.16 Remrk 1.77 홀수인완전수의존재에대해서는알려진바없다. Exercise 1.78 p97: #, #9, #10, #17, #3 13

14 부정방정식과합동식.1 부정방정식 Definition.1 (p61) 우리가다룰 (1차) 부정방정식은대부분 x + by = c, ( 계수, b, c Z, 미지수 x, y Z) (.1) 형태이다. 통상 0 b 인경우를다룬다. Theorem. (p6: 4.5) (.1) 이해를가질필요충분조건으로 gcd(, b) c 이있다. Proof. gcd(, b) = g = x 1 + by 1 로둔다. g c 이면 c = kg 로두었을때 (kx 1 ) + b(ky 1 ) = kg = c 이므로 (x, y) = (kx 1, ky 1 ) 이하나의해가된다. 역으로 (x, y) 가 (.1) 의해라면이것은 L(, b) 의원소이므로 g 의배수가된다. (See Exer ) Theorem.3 (p63: 정리 4.6 의일반화버전 ) (x 0, y 0 ) 가 (.1) 의해이면, 모든 m Z 에대하여 ( x0 + b g m, y 0 g m) 도 (.1) 의해이다. 역으로모든해는이런꼴로얻어진다. 단, g = gcd(, b). Proof. ( ) 는당연하다. ( ) 를보이기위하여 x + by = c 를가정하고 ( m) ( x = x 0 + b g m nd y = y 0 g m) 을 증명하겠다. 먼저 = g, b = gb 으로둔다. x 0 + by 0 = c = x + by 이므로 (x x 0 ) + b(y y 0 ) = 0 x = x 0 b (y y 0) x = x 0 b (y y 0 ) x = x 0 + b g y0 y (.) 이다. 이제 y y 0 = m Z 를보이면된다. gcd(, b ) = 1 이므로유클리드의레마에의하여 b (y y 0 ) (.) 를보면 b (y y 0 ) = x 0 x Z 임을알수있다. Exmple.4 p64: 예제 4.7, p65: 예제 4.8 Exercise.5 p67: #10, #11, #1 Z 를보이면충분하다. 여기서. 합동식 Definition.6 (p103) 각 n N 에대하여두자연수간의관계 n ( 법 n 으로같음 ) 을아래와 같이정의한다. n b n b b (mod n) 14

15 Remrk.7 (p104: 7., 7.3, 7.4) n b 는 %n = b%n 과동등하다. 이관계는합동관계 (congruence reltion) 이다. 즉, 동등관계이고또한 1 n b 1 nd n b 1 + n b 1 + b, nd 1 n b 1 b. 따라서임의의 ( 정수계수 ) 다항식 f(x) = n x n + 1 x + 0 에대하여 x n y f(x) n f(y) 이다. Exercise.8 (Z, +, ) 위의합동관계는반드시 n 꼴이다. 그리고 (Z, +, ) 위의합동관계 도반드시 n 꼴이다. 이사실을증명하여라. ( 힌트 ). b 이면 ( k Z) ( 0 k(b ) ) 임을 보인다. Remrk.9 c, x, y Z 일때 x n y cx n cy 는당연히성립한다. 이것의역 cx n cy x n y 에대해서생각해보자. 좌변을 c 로나눌수있다면좋을텐데... 정수들의세계에서덧셈과곱셈은문제가없으나나눗셈이문제다. 법 n 으로생각하면 때로는 나눗셈이가능하다. c로나눈다는것은 1 c 을곱한다는것이다. n이소수일때는, 대부분의 c Z는법 n으로역원 (inverse) 이존재한다. ( 역원은곧역수 라고생각하면된다.) 예를들어 n = 7 이면 이다. 7 은법 7 로역원이없으나이건 이므로문제가안된다. 즉 7 의배수가아닌 ( 법 7 로 0 이아닌 ) 모든정수는법 7 로역원이존재한다. 그러나소수가아닌수, 예를들어법 6 으로역원을가지는수는 1 과 5 밖에없음을금방확인할수있을것이다. 는다음과같은의미로나눗셈도존중한다. ( 나눗셈합동식보존레마 ) n b d n d b, provided tht d, d b, nd d n (.3) d 덧셈, 곱셈, 뺄셈의존중과다른점은법 n 도나누어진다는것이다. 아래의 ( 한방향 ) 함의도자주유용하게사용된다. n b n d b, provided tht d n (.4) Lemm.10 ( 역원의존재성레마, p14: 8.9) gcd(c, n) = 1 ( b)(cb n 1) Proof. 정리 1.39 를이용한다. Remrk.11 법 n 에대한역원이존재하는정수들을 ( 법 n 에대한 ) 가역원소 (invertible element) 라고한다. Z 의법 n N 에대한역원들은법 n 으로유일하다. b n 1 n b 15

16 이라면 b n 1b n (b )b n b (b) n b1 n b이기때문이다. 의역원이존재한다면 Z n 의원소중에유일하게존재한다. 존재성의증명은양의역원들의집합의최소원을생각하면된다. 의역원중 Z n 의원소를 1 으로나타내기로한다. 법 7로 ( ) 1 는? Corollry.1 (p105: 7.5, 7.7. 합동식소거율 ) gcd(c, n) = 1 ( c n cb n b ), (.5) c n cb (n/g) b, where g = gcd(c, n). (.6) Proof. (.5) 는역원의존재성레마.10을이용하여보인다. (.6) 은우선나눗셈합동식보존레마 (.3) 을이용하여 c/g (n/g) cb/g를얻은후에서로소보조정리 1.43과 gcd(c/g, n/g) = 1 를이용하여보인다. 실은 (.5) 는 (.6) 의특수한경우이다. Exercise.13 (p106: 7.8) 다음을증명하여라. n b gcd(, n) = gcd(b, n) Exercise.14 (1) gcd(, n) = 1이고 gcd(b, n) = 1이면반드시 gcd(b, n) = 1인가? 역은어떠한가? () n 1이고 b n 1이면반드시 b n 1인가? 역은어떠한가? (3) gcd(, n) = 1과 n 1 간의함의관계는? (4) n 1이고 m 1이면 nm 1인가? 역은어떠한가? gcd(n, m) = 1일때는? 그리고 3 합동식의우변들의 1을 c Z로바꾸면어떻게되는가? Exercise.15 (p107: 7.9) 을 7로나눈나머지를구하여라. ( 정리 3.1과의연관성은?) Remrk.16 배수판정법 (pp ) 여기서다루는내용은배수임을판정하는것이상이다. 3, 7, 9, 11, 13으로나눈나머지를구하는방법을알려준다., 4, 5, 6, 8, 10으로나눈나머지를구하는방법은더쉽고잘알려져있다. 논의중에, b, c 1이고 b일때 (c% = (c%b)%) 라는사실이쓰인다. 이를증명하여라. Theorem.17 (p119: 8.5) 합동 ( 방정 ) 식 x n c (.7) 가해를가질필요충분조건으로 gcd(, n) c가있다. Proof. x(x n c) x y(x c = ny) x y(x + n( y) = c) gcd(, n) c 마지막의양방향함의는앞서정리. 에서보았듯이 x+by = c 가해를가지는것은 gcd(, b) c 의필요충분조건이었기때문에성립한다. 16

17 Discussion.18 (p1: 8.7) 합동식 x n c 은, gcd(, n) = 1 인경우에는 gcd(, n) c 의조 건이당연히만족되므로해를가질것이다. 그리고 x = 1 c 는해가됨을알수있다. 법 n 으로는이것이유일한해이다. 왜냐하면 x n c n y 이면 n (y x), 따라서 n y x 이기때문이다. gcd(, n) = g 1일경우에는 x n c의해가 ( 존재하는경우에는 ) 여럿존재한다. x n c g x c n/g, (See (.3).) g 이고우변의해는, gcd(/g, n/g) = 1이므로, 법 n g 으로유일하게존재하게된다. 좌변의해는곧우변의해이므로법 n g 으로는유일하다. 좌변의해는법 n으로따지는것이옳으므로법 n 으로는몇개인지아래에알아보았다. 따라서 x 0 를 g x n/g c g 의해라하면 x 0 + n g 도 g x n/g c g 의해이고따라서 x n c 의해이다. x 0, x 0 + n g, x 0 + n g,..., x 0 + (g 1) n g 는모두 x n c의해이다. 이들은법 n g 으로는동일하지만법 n으로는구별된다. 따라서 x n c의해는 ( 법 n으로 ) 정확히 g = gcd(, n) 개존재한다..3 완전잉여계 Definition.19 (pp ) A Z 가법 n 에대한완전잉여계라는것은 ( r Z n )( 1 x A)(x%n = r) 를뜻한다. (1 Z n = {0, 1,..., n 1}, 잉여 란나눗셈알고리듬에나오는몫 (quotient) 과 나머지 (reminder) 에서의 나머지 이다.) Exmple.0 예를들어 Z n, {1,..., n}, {,..., n, n + 1}, { 1, 1,..., n, n} 등은모두 완전잉여계이다. 완전잉여계의원소의개수는반드시 n 이된다. (Why?) Fct.1 (p11: 7.13) n 개의정수로이루어진집합 { 1,..., n } = A 에대해서다음의 4 명제들은모두서로동등하다. (1) A 는완전잉여계이다. () A 는 n- 동등류들에서각각하나씩원소를뽑아이룬집합이다. (3) A 의임의의두원소가법 n 으로다르다. (4) { 1 %n,..., n %n} = Z n Theorem. (p113 정리 7.14) { 1,..., n } Z 가법 n 에대한완전잉여계이고 c Z 일 때 (i) { 1 + c,..., n + c} 는법 n 에대한완전잉여계이다. (ii) gcd(n, c) = 1 이면 { 1 c,..., n c} 는법 n 에대한완전잉여계이다. 게다가 i n 0 c i n 0 이다. 17

18 Proof. Fct.1을사용한다. (i) 의증명은아주쉬우므로생략한다. (ii) 는 gcd(n, c) = 1 n ( i j )c n i j 로부터얻어진다. ( 여기서 gcd(n, c) = 1 조건이없으면어떻게되겠는가? 이면 을 이면이 로바꾸어야하겠는가?) Theorem.3 ( 중국인나머지정리, p16: 8.10) 연립합동방정식 x n1 1, x n,..., x nr r 의해는, n i 들이쌍마다서로소이면, 법 n 1 n n r 로유일하게존재한다. Proof. r 에대한수학적귀납법을사용한다. 유일성 : x n1 1 n1 y, x n n y 라하면 n 1 (x y), n (x y) 이므로서로소보조정 리 1.43.(i) 에의하여 n 1 n (x y), 즉 x n1 n y 가성립한다. 이것이 r = 경우의증명이다. x ni i ni y, (i < r), x nr r nr y 이면귀납가설에의하여 x n1 n r 1 y 이다. n 1 n r 1 과 n r 이서로소이므로 x n1 n r 1 y 와 x nr y nr r 에 r = 인경우의결과를적용하면 원하던 x n1 n r y 를얻는다. 존재성 : r = 경우, 즉 x n1 1, x n 의해를위하여 x 1, x 를 n 1 x 1 + n x = 1 되도록취한다음, x = n 1 x 1 + n x 1 로둔다. 그러면 x 1 = n 1 x 1 + (n x 1) 1 = n 1 x 1 ( 1 ) 이므로 x n1 1 이성립하고, x = n x 1 + (n 1 x 1 1) = n x ( 1 ) 이므로 x n 가성립한다. 이것으로써 r = 경우에대한 존재성 이증명되었다. 일반적인경우, 즉 x n1 1,..., x nr r 의해는다음과같이얻는다. 먼저귀납가설에의하여 x n1 1,..., x nr 1 r 1 의해 y 를얻는다. 그리고연립방정식 x n1 n r 1 y, x nr r 의해를 r = 의경우의결과를이용하여얻는다. 위에보인것과다른, 중국인나머지정리에대한증명 개를아래에보였다. r = 인경우의 존재성과유일성만증명하며, 일반적인경우에대한증명은수학적귀납법에의하여쉽게얻 18

19 을수있을것이다. 아래의두증명에서 gcd(n, m) = 1임을가정하고연립합동방정식 x n, x m b의해를찾는다. Proof #. 함수 f : Z nm Z n Z m 을 f(x) = (x%n, x%m) 로정의하면이함수는, gcd(n, m) = 1이므로단사이며, Z nm = Z n Z m 이므로전사가된다. r = 인경우에 x n, x m b의해는 f(x) = (x%n, x%m) = (%n, b%m) 인 x이며이러한 x는 f가전사이므로존재한다. 또한 f가단사이므로유일하게존재한다. Proof #3. 유일성의증명은정리.3 과같이하면되고, 여기서는존재성만증명하겠다. x n 의해들로이루어진집합 {, + n, + n,..., + (m 1)n} 를생각해보자. 이집합은정리. 에의하여 ((ii) 와 (i) 을각각한번씩적용한다 ) 법 m 에대한완전잉여계이므로원소중어느하나, x i = +i n 는 b 와법 m 으로같다. 그러면 x i n 이고또한 x i m b 이다. Remrk.4 정리.3 에서보인증명은증명 #, #3 보다조금더복잡하지만그대신 해를얻는알고리듬이약간은더효율적이다. Exercise.5 (p17: 8.11) 다음연립일차합동식을풀어라. x 3, x 5 3, x 7 ( 힌트 ). 책의풀이에오타가많다. Exercise.6 (p18: 8.1) 다음일차합동식의해를구하여라. 17x 76 9 ( 힌트 ). 17 의법 76 에대한역원을구하는것도하나의방법임. Exercise.7 p19: #1 #5 ** 중간고사범위는여기까지입니다. ** 19

20 3 페르마의정리와오일러의정리 3.1 페르마의정리와윌슨의정리 Theorem 3.1 (Fermt s little theorem, p131: 9.1) 소수 p 와정수 에대하여 gcd(, p) = 1 p 1 p 1. Proof. gcd(, p) = 1 이므로 p 에대한완전잉여계 {1,..., p} 에 를곱하여얻은집합 {,,..., p} 도완전잉여계이다. 따라서법 p 로 0 인 p 와 p 를제외한나머지 p 1 개정수의곱은법 p 로 같다. 1 (p 1) p () ((p 1)) (p 1)! p (p 1)! p 1 이제 (p 1)! 의역원을위합동식의양변에곱하면원하는합동식을얻는다. (See Exer nd Corollry.1.) Definition 3. (p135) 자연수 n 에대하여아래와같이정의한다. U n = {x Z gcd(x, n) = 1}, ( 가역원소들의집합 ) U n = {x Z n gcd(x, n) = 1} = U n Z n ϕ(n) = U n, (Euler s function) Exercise 3.3 U n 는곱셈및역원에대하여닫혀있음을보여라. 또한 U n 은 곱한후 n 에대한 나머지취하기 에대하여닫혀있음을, 즉 ( x, y U n )(xy%n U n ) 임을보여라. Discussion 3.4 법 n 에대한역원이자기자신인수, 즉 x n 1 인 x 에는 1 과 n 1 이있다. x U n 에대해서 x 1 는 x 의역원중에 Z n 에속하는것을뜻하는것으로정의하였었다. 이때 x 1 = x 는 x n 1 과동등하다. Q1: 이둘외에더있을수있는가? Ans: 3 8 1, 등의예가있다. n = p 가소수일때는이럴수없다. x 1 p 0 p (x 1)(x + 1) x p ±1 Q: n 이소수가아니면어떻게되는가? (Ans: 이건답정너다. n = 8, x = 3, 5) Theorem 3.5 ( 윌슨의정리, p136: 9.5) p 가소수이면 (p 1)! p 1 이다. ( 실은이것의역도 성립한다.) Proof. ( 힌트 ). p > 3 인경우에대하여만보이면충분하다. {,..., p } 의각원소 x 는그것의 역원 x 1 x 를이집합내에가지므로 개씩짝을지을수있다. 이들을다곱하면법 p 로 1 이된다. 즉, (p )! 은법 p 로 1 이다. 역을증명하기위하여는 n 이합성수임을가정하고 d n 인 d > 1 을취한다. (n 1)! n 1 을 가정하고모순을유도하자. (n 1)! = dq, q N 으로놓으면 dq n 1 이므로 dq ( 1) = nx, x Z 로둘수있다. 그러면 d( q) + nx = 1 이므로 gcd(d, n) = 1 을얻게된다. 이것은원래의 가정 d n, d > 1 에모순된다. 윌슨의정리의응용으로 0! % 3 을계산해보라. (p137: 9.6) 0

21 Exercise 3.6 p140 에있는문제 #1, #, #3, #6, #8, #10, #11 를풀어라. 단, (1) #3. 오타수정. 7 의배수이고, 바로뒤에 n 이 3 의배수가아닐때, 를넣는다. () #8. 오타수정. p 인소수 p 와정수 에대하여... Discussion 3.7 (p13) 페르마의정리에의하여모든소수 p 와모든정수 에대하여 p p (3.1) 임을알수있다. 이는페르마의정리를쓰지않고도다음과같이증명할수있다. Proof. 먼저다음을증명한다. ( + 1) p p p + 1 (3.) 좌변에 항정리를적용하여전개하면 p p 1 ( p r=1 r) r 이다. 그런데 ( p r) p 0이므로 (3.) 가성립하게된다. 이제 (3.1) 을 에대한귀납법으로보일수있다. Z p 에대해서만보이면된다. 0 n p 0 는당연히성립하고, ( + 1) p p p + 1 p + 1 에서두번째등호는귀납가설 p p 에 의하여성립한다. Discussion 3.8 페르마의정리의역은 n 1 n 1인 Z가존재하면 n은소수가아니다. 이다. 예를들어 6 1 = 이므로 6은소수가될수없다. n 1 n 1인지를모든 에대해서확인할수는없으므로 = 에대해서만테스트하여 n이소수인지를판정하는것을페르마판별법이라고한다 : n 1 n 1이면소수일가능성이있는것이고, 그렇지않다면소수가아닌것이확실하다. 117이소수인지를알아보는과정이 p133에나와있다. 3. 오일러의정리 Exercise 3.9 (p145: 보조정리 10.3) A Z가법 n에대한완전잉여계라면 A의원소중에 n 과서로소인것들의개수는 ϕ(n) 임을보여라. ( 힌트 ). 1대1 대응 Fct 3.10 p 가소수일때, ϕ(p) = p 1, ϕ(p n ) = p n p n 1 = p n 1 (p 1). Theorem 3.11 (p145: 10.4) ϕ는승법적이다. Proof. n, m N, gcd(n, m) = 1이라하고 ϕ(nm) = ϕ(n)ϕ(m) (3.3) 를보인다. n = 1이거나 m = 1일때는 (3.3) 이당연히성립하므로 n, m 를가정한다. 1

22 그리고 1,,..., nm 을아래와같이배열한다. 1 j m m + 1 m + m + j m (n 1)m + 1 (n 1)m + (n 1)m + j nm 이행렬의 j 열의모든성분들은서로법 m 으로같으므로다음의양방향함의들이성립함을 알수있다. j 가 m 과서로소 j 열의모든성분이 m 과서로소 j 가 m 과서로소아님 j 열의모든성분이 m 과서로소아님 이제 j 가 m 과서로소 일때 j 열이 m 과서로소 라고말하기로하자. 한편우리는다음의 양방향함의가성립함을안다. k 가 nm 과서로소 k 가 n 과서로소이고또한 k 가 m 과서로소 ϕ(nm) 은위의행렬의성분 k 중에 nm 과서로소인것들의개수를뜻한다. k 가 nm 과서로 소라면 k 는 m 과서로소이므로 k 는 m 과서로소인열에속해야한다. 그런데 m 과서로소인 열들의개수는 ϕ(m) 이다. 따라서이제아래의명제를증명하면충분하다. 위행렬의모든열에대해서, 그열의성분중에 n 과서로소인것은 ϕ(n) 으로일정하다. 위행렬의 j 열은법 n 에대한완전잉여계인 Z n 의각원소에 m 을곱하고여기에 j 를더하여 얻어진다. 따라서 j 열은법 n 에대한완전잉여계이다. (See Thrm...) 이제연습문제 3.9 를 적용하면된다. Exmple 3.1 ϕ(108) 를구해보자. 소인수분해하면 108 = 3 3 을얻는다. ϕ 가승법적이 므로 ϕ(108) = ϕ( )ϕ(3 3 ) = ( 1 )(3 3 3 ) = (4 )(7 9) = 36. 답 : 36 Corollry 3.13 (p147) n 의표준형소인수분해가 n = p k 1 1 pkr r 일때 ϕ(n) = (p k 1 1 pk ) (p kr r p kr 1 r ) = p k p kr 1 r (p 1 1) (p r 1) ) ) = n (1 1p1 (1 1pr. Theorem 3.14 ( 가우스의오일러함수정리, p148: 10.5) n N이면 ϕ(d) = n d n, d>0 (3.4) Proof. n의소인수의개수 π n 에대한수학적귀납법을사용한다. π n = 0인경우는 n = 1 에해당하므로 (3.4) 가당연히성립한다. π n = 1인경우에는 n = p e 으로두면 n의약수는 1, p, p,..., p e 이며, 이들의 ϕ 값은 1, p 1, p p,..., p e p e 1 이다. 따라서 ϕ(d) = 1 + ( 1 + p) + ( p + p ) + + ( p e 1 + p e ) = p e = n d n,d>0

23 이다. π n > 1인경우에는 n = b, gcd(, b) = 1, > 1, b > 1 으로둔다. 의모든약수들의집합을 {x 1,..., x r }, b의모든약수들의집합을 {y 1,..., y s } 로두었을때 n의모든약수들의집합은 {x i y j 1 i r, 1 j s} 이므로 (See the proof of Thrm 1.74.) ϕ(d) = d n,d>0 = r s r s ϕ(x i y j ) = ϕ(x i )ϕ(y j ) i=1 j=1 r ϕ(x i ) i=1 j=1 s ϕ(y j ) = i=1 j=1 d,d>0 d b,d>0 ϕ(d) ϕ(d) = b = n 이다. Theorem 3.15 ( 오일러의정리, p149: 10.7) ( 페르마의정리 3.1 의일반화버전임.) 임의의정 수 와자연수 n 에대해서, gcd(, n) = 1 ϕ(n) n 1 Proof. 힌트 : m = ϕ(n), U n = {x 1,..., x m } 이라하면임의의 U n 에대해서 {x 1 %n,..., x m %n} = U n 이다. 이제페르마의정리의증명을흉내내면된다. Exercise 3.16 U n 의원소들을모두곱한것은법 n 으로무엇인가? ( 이것이 n 과서로소임은 바로앞에있는오일러의증명에써먹었다.) n 이소수일때는이것의값은윌슨의정리에 의하여 1 이된다. ( 힌트 ). 답은 ±1 이다. 문제는 x n 1 인 x 들인데이런것들을 single 이 라고부르기로한다. 이때 n x 도 single 이다. 그리고이둘의곱은법 n 으로 x n 1 이다. n x = x 인상황은 x U n 이므로발생하지않는다. Discussion 3.17 (p138: 9.7) 앞서 x n 1 의해에대해서관심을두고알아보았는데이번 에는 x p 1 의해를조사해보자. 법이소수 p > 인경우에대해서만알아본다. p = 인 경우에는 1 1 이므로이토픽은별의미가없다. p = 5, 13, 17, 9,... 에대해서는해가존재하고 p = 3, 7, 11, 19, 3,... 에대해서는해가존 재하지않음을확인할수있을것이다. 일반적으로 p 가홀의소수일때 p 4 1 ( x)(x p 1) (3.5) 임을아래와같이증명할수있다. Proof. p 가홀수이면 ( 소수가아니더라도 ) 3

24 (p 1)! = (1 (p 1)) ( (p )) ( p 1 p+1 ) p ( 1 ) ( ) ( ( p 1 ) ) = ( 1) p 1 ( p 1 )! 이된다. (3.6) 은공식으로암기해둘가치가있다. p가소수이면 (p 1)! p 1이므로 ( p 1 )! = ±1이될것이다. p = 4m+1 꼴인경우에는 p 1 = m이므로 (3.6) 으로부터 ( p 1 )! 이 x p 1 의해임을알수있다. (3.6) 이제 p = 4m + 3 일때는 x p 1 의해가존재한다고가정하고모순을유도하겠다. p 1 을가정하자. 페르마의정리에의하여 4m+ p 1 이다. 그러므로 1 p (m+1) = ( ) m+1 p ( 1) m+1 p 1 라는모순을얻게된다. Exercise k + 1 꼴의소수인 5 는 = 10 의약수, 13 은 = 6 의약수, 17 은 = 170 의약수이다. 반면에 4k + 3 꼴의소수인 7, 11, 19, 3 등은 n + 1 꼴의정수의 약수가될수없다. 이를증명해보라. 4k + 1 꼴의소수는반드시어떤 n + 1 꼴의정수의 약수가되는가? Exercise 3.19 pp 에있는문제 #1 #4, #6, #7, #1, #14, #16 을풀어라. 단, (1) #3. Z 700 U400 와 Z 700 U800 도구하여라. 아래의 #4와연관지어생각해보라. () #4. 오타수정 : ϕ(n ) = nϕ(n) 을증명하여라. (3) #6. 오타수정 : k =, 3 에대해서 n k 와 n k 를각각 k n 와 k n 으로고칠것. 또한 문제번호 () 가 3 개있는데, 뒤의 개는 (3), (4) 로고칠것. Discussion 3.0 중국인나머지정리를이용하여오일러의 ϕ 함수가승법적임을증명할수 있다. n, m 을서로소인두자연수라하자. ϕ(nm) = U nm, ϕ(n)ϕ(m) = U n U m 이므로전 단사함수 f : U nm U n U m 을만들면된다. 이함수는다음과같이정의한다. (cf. p19, Proof # ) f(x) = (x%n, x%m) 먼저 f 는잘정의되었음을 (well-ined) 보여야한다. 즉 gcd(x, nm) = 1 gcd(x, n) = 1 nd gcd(x, m) = 1 (3.7) 을보여야하는데, 이것이성립함은 nm 의소인수들은 n 의소인수들과 m 의소인수들로분할 된다는점에착안하면곧알수있을것이다. 실은같은이유로 (3.7) 의역도성립한다. f 가단사임은 ( 서로소보조정리 1.43).(1) 을써서쉽게증명된다. f 가전사임을보이려면 x (x%n, x%m) 이 Z nm 에서 Z n Z m 로가는전사함수임을이 용한다. ( 이사실은중국인나머지정리에의하여함의된다.) 즉, 임의의 (, b) U n U m 에 대하여 (x%n, x%m) = (, b) 인 x Z nm 이존재함이보장된다. 우리는 x U nm 이기를원한다. 그리고이것은 (3.7) 의역에의하여함의된다. 4

25 4 원시근과이산로그 4.1 위수와원시근 Definition 4.1 (p157) 법 n N 에대한가역원소 U n 에대하여 k n 1 을만족하는 최소의자연수 k 를 법 n 에대한 의위수 (order) = ord n () 라정의한다. Exmple 4. 법 7에대한 의위수는 3이다. i 1 3 i 4 1 법 7 법 n에대한가역원 의위수를 m이라할때 mq+r n r 이므로 k n k%m 이됨을알 수있다. 법 7에대한 3의위수는 6이다. i i 법 7 Fct 4.3 (pp ) n N,, b U n 일때 (1) n b ord n () = ord n (b) () 위수 ord n () 는반드시존재한다. (3) k n 1 ord n () k (4) ord n () ϕ(n) (5) ( n)( k ϕ(n))( )(ord n () k) (6) j n k j ordn() k (7) 1,,..., ordn() 는법 n 으로모두서로다르다. (Exmple 4. 참조.) Theorem 4.4 (p159: 11.3) ord n ( k ) = ord n () gcd(ord n (), k) Proof. ord n () = m, gcd(m, k) = g로둔다. ord n ( k ) = m g 임을보이겠다. Clim 1. ( k ) m g n 1 : ( k ) m g = ( m ) k g n 1 k g = 1 Clim. 만일 l N 이 ( k ) l n 1 을만족하면 l m g : m g l을보이면충분하다. kl n 1 m kl m g g k g gl m g k g l. 여기서유클리드의 레마를사용하여 m g l을얻는다. 5

26 Corollry 4.5 (p160: 11.4) ordn (k ) = ordn () gcd(ordn (), k) = 1 Definition 4.6 (p160) n N일 때, ordn () = ϕ(n)인 정수 Un 를 법 n에 대한 원시근이라 한다. 법 7에 대한 원시근이 존재하는가? (Exmple 4..) 법 8에 대한 원시근은 어떤가? (p158, 마 지막 문단.) Theorem 4.7 (p178: 1.9) 자연수 n에 대한 원시근은 n이 다음 중 어느 하나일 때면이 존 재한다., 4, pk, pk, (단 p는 홀의 소수.) Theorem 4.8 (p161: 11.5) 가 법 n N에 대한 원시근이면 A = {%n, %n,..., ϕ(n) %n} = Un 이다. (원시근의 거듭제곱으로 모든 가역원소들을 얻을 수 있다.) Proof. 연습문제 3.3에 의하여 A Un 이다. Fct 4.3.(6)에 의하여 A = ϕ(n) = Un 이다. 유한 집합 Un 의 부분집합 A가 Un 과 원소의 개수가 같으므로 A = Un 이다. Exmple 4.9 (p161: 11.6) U9 = {1,, 4, 5, 7, 8}, ϕ(9) = 6이므로 아래의 표를 보면 가 9의 원시근임을 알 수 있다. 또한 {i %9 i Zn } = U9 임을 확인할 수 있다. i i 법 9 Fct 4.10 법 n에 관한 원시근이 존재한다면 Un 내의 원시근은 ϕ(ϕ(n)) 개 존재한다. (힌트: Use Coro 4.5.) Exmple 4.11 Z54 내에 있는 54의 원시근을 모두 구해 보자. (정리 4.7에 의하여 원시근의 존재가 보장된다.) 이들 원시근은 U54 의 원소이므로 먼저 54와 서로소인 54 이하의 자연수들 을 찾아야 한다. 54 = 33 로부터 U54 의 원소는 1, 5, 7, 11,... 등이다. 이들 원소의 개수는 ϕ(54) = (1 0 )(33 3 ) = 18로 계산된다. 이제 5가 원시근인지 알아 보자 은 당연히 성립할 것이고, 5k 54 1인 k < 18이 존재하지 않으면이 5가 원시근이다. 18의 진약수는, 3, 6, 9이므로 5, 53, 56, 59 을 법 54로 계산해 보면 각각 5, 17, 19, 이다. 따라서 5는 54의 원시근이다. 원시근 하나를 구하면 나머지 원시근들은 쉽게 구할 수 있다. 이들은 5k, gcd(k, 18) = 1 으로 얻어지며 총 ϕ(18) = 6개 있다. 55, 57, 511, 513, 517 는 법 54로 각각 47, 41, 9, 3, 11이다. (힌트: wolfrmlph.com에서 517 mod 54 등을 계산할 수 있다.) 답: 5, 11, 3, 9, 41, 이산로그 Definition 4.1 (p16) Z가 법 n N에 대한 원시근일 때, 각 x Un 에 대하여 를 밑으로 하는 x의 이산로그 ind (x) {1,..., ϕ(n)} 를 x n k 를 만족하는 최소의 자연수 k로 정의한다. 이산로그는 지수라고도 한다. 6

27 Exercise 4.13 법 7 일때, 원시근 3 을밑으로하는이산로그표를 Exmple 4. 를참고하여 그려라. 법 9 일때, 원시근 를밑으로하는이산로그표를 Exmple 4.9 를참고하여그려라. 이산로그표의형식은 Exercise 4.15 를따른다. (p163: 보기를따르지말고 p164: 을따를 것.) Fct 4.14 가 n 을법으로하는원시근일때모든가역원소 x, y U n 와자연수 m N 대하 여다음이성립한다. (1) ind (1) = ϕ(n) () ind(x) n x (3) x n y ind (x) = ind (y) (p163: 정리 11.7) (4) t n s t ϕ(n) s (5) ind (xy) ϕ(n) ind (x) + ind (y) (p163: 정리 11.8.(1)) (6) ind (x m ) ϕ(n) m ind (x) (p163: 정리 11.8.()) (7) ind ( m ) ϕ(n) m (p164) Q: ind (x) 와 log (x) 의같은점과다른점은각각무엇인가? Exercise 4.15 아래에법 13 과 17 에대한이산로그표를보였다. 원시근은각각 와 3 으로 잡았다. x ind (x) x ind 3 (x) (1) 각경우에원시근들을모두찾아보아라. () 법 9 에대한이산로그표를, 모든원시근에대해서각각작성하여라. Exmple 4.16 (p164: 11.10) 합동방정식 5x 을풀어라. ( 힌트 ). 교재에주어진이산 로그표에는오타가있다. Exercise 4.17 pp 에있는문제 #1 #10, #1, #13, #14, #16 을풀어라. 단, (1) #1 ( 법 n 에대한위수는 ϕ(n) 의약수임을이용한다.) () #3 (U n 중에서있는대로모두구한다.) (3) #5 (Coro 4.5 를이용한다.) (4) #6 (3 k %43 형태로답해도좋다.) (5) #10 ( 소수 p 에대한원시근은항상존재한다는사실을이용한다.) (6) #1 ( 법 n 1 에대한 의위수는 n 이다. Fct 4.3.(3) 이용.) (7) #16 ( 추가 : 7 9 을 17 로나눈나머지. 원시근은 3.) 7

28 4.3 원시근정리 Theorem 4.18 ( 라그랑즈의정리, p171: 1.1) 소수 p 와 n 차정수계수다항식 f(x) = n x n + n 1 x n x + 0, ( n p 0) 에대하여, 합동방정식 f(x) p 0 의해의개수는법 p 로 n 개이하이다. Proof. n 의법 p 에대한역원을양변에곱하여 n p 1 로보아도된다. n 에대한수학적귀 납법을사용한다. f(x) p 0 가법 p 로서로다른해 c 0,..., c n 를가진다고가정하고모순을 유도하겠다. n 1 f(x) f(c 0 ) = (x n c n 0 ) + k (x k c k 0) = (x c 0 )g(x) k=0 로둘수있다. 여기서 g(x) p 0 는 n 1 차다항방정식이므로귀납가설에의하여기껏해야 n 1 개의해를가진다. 위식의좌변과우변에 x = c k, k = 1,..., n 을대입하면 f(c k ) f(c 0 ) = (c k c 0 )g(c k ) 인데, f(c k ) f(c 0 ) p 0 0 p 0 이므로 (c k c 0 )g(c k ) p 0 를얻는다. 그런데 c k c 0 p 0 이므로 p 의소수성에의하여 g(c k ) p 0 가성립한다. 이것은 g(x) 에대한귀납가설에모순된다. Theorem 4.19 (p17: 1.) p 가소수일때각 d (p 1) 에대하여합동방정식 x d 1 p 0 는 정확히 d 개의해를법 p 로가진다. Proof. d = 1 일때와 d = p 1 일때는이정리의주장이옳음을쉽게알수있다. (Why?) 1 < d < p 1, p 1 = de, e 로두면 (x d ) e 1 = x p 1 1 = (x d 1)g(x) (4.1) 로쓸수있다. 여기서 g(x) 는차수 p 1 d 인다항식이다. 페르마의정리에의하여 x p 1 1 p 0 는 U p 내에 p 1 개의해를가지게되는데, (4.1) 과 p 의소수성에의하여이해들은모두 x d 1 p 0 의해이거나또는 g(x) p 0 의해이다. 앞으로 해라함은 U p 내의해를뜻하는것으로하자. x d 1 p 0 의해의개수를 k, g(x) p 0 의해의 개수를 l 이라하면, p 1 = k + l 이되어야한다. 그런데라그랑즈의정리에의하여 k d 이고 l p 1 d 이다. 따라서 k = d, l = p 1 d 일수밖에없다. Theorem 4.0 ( 원시근정리 (by 르장드르 ), p173: 1.3) 임의의소수 p 는원시근을허용한다. Proof. 각 d (p 1) 에대하여 Λ d = { U p ord p () = d}, λ d = Λ d 라둔다. 우리의목표는 λ p 1 > 0 를증명하는것이다. 각 U p 의위수는 p 1 의약수이므로 U p d (p 1) Λ d 이고 U p Λ d 는당연하며, 또한 d d Λ d Λ d = 이므로 U p = d (p 1) Λ d, 즉 p 1 = d (p 1) λ d (4.) 8

29 가성립한다. 한편가우스의정리 3.14에의하여 p 1 = ϕ(d) (4.3) d (p 1) 가성립한다. 이제우리는 ( d (p 1))(λ d ϕ(d)) (4.4) 를보일것이다. 그러면 (4.), (4.3) 과 (4.4) 에의하여 ( d (p 1))(λ d = ϕ(d)) (4.5) 를얻게되며이것으로우리의목표였던 λ p 1 = ϕ(p 1) > 0 가증명된다. 이제 (4.4) 를증명해보자. 일반성의손실없이 λ d > 0 를가정한다. 그러면 ord p () = d 인 U p 가존재한다. 여기서 d 개의수 {%p, %p,..., d %p} = A (4.6) 를생각해보자. 이들중어느두개도같지않다. 왜냐하면만일 i p j, 1 i < j d 라면 j i p 1 이되어 의위수가 d > j i 라는것에모순되기때문이다. 집합 (4.6) 의원소중에위수가 d 인것을 k %p 라하면 gcd(k, d) = 1 이며이러한 k 의개수 는 ϕ(d) 이다. 즉 Λ(d) A ϕ(d) 이다. 따라서이제 (4.4) 를보이기위하여남은것은 Λ(d) = Λ(d) A, 즉 Λ(d) A 뿐이다. S = {x U p x d 1 p 0} 로두면 A S 이다. 라그랑즈의정리에의하여 S d 이지만 우리는 A = d 임을안다. 이것은 A = S 임을의미한다. 따라서 Λ(d) S = A 이다. Exercise 4.1 p = 13 일때각 d p 1 에대하여 Λ d 와 ϕ(d) 를구하고 (4.5), 즉 ( d ϕ(n))(λ d = ϕ(d)) 를확인하여라. n 이소수가아니지만원시근을가지는경우 d ϕ(n) 에대하여같은작업 을해보라. n = 4, n = 9 의두경우만해볼것. Theorem 4. 법 n N 에대한원시근이존재할필요충분조건은 n =, 4, p k, p k 이다. ( 단, p 는홀의소수, k N.) Proof. 생략. (pp ) Exercise 4.3 () p173: 1.4 의증명과정과의미를설명하여라. (cf. p138: 9.7, (3.5)) (b) p179 의모든문제를풀어라. p179 의문제들에대한힌트를아래에보였다. (1) #1 : 정리 4. () # : 예 4.11 (3) #3 : 해를 Z p 내에서구하라는뜻이다. (1) 원래 x p 0 인모든 x 에대해서 x p 1 p 1 가 성립하는데, 여기서는지수 p 1 이 p 로바뀌어있다. 책의해답은틀려있다. 문제를 x p p 1 로바꾸면책의해답이맞다. () ( 유한 ) 등비급수합의공식사용. 9

30 (4) #4 : 위수가 4 인 U 61 의원소의개수는 (4.5) 에의하여금방구할수있다. 원시근을먼 저찾아야할것이다. 원시근을 라하면위수가 4 인원소는 k 꼴로나타낼수있으며 이때 4 gcd(k, 60) = 60 이어야한다. (5) #5 : (rs) n p 1 인 n < p 1 을찾으면된다. p = n + 1 꼴임을이용한다. 또한 x p 1 의해는 1, 1 둘밖에없음을이용한다. (6) #6 : 책의힌트를보라. (7) #7 : (1) r 의위수 d 는 ϕ(p) = p 1 = 4k 의약수다. d 가 k 의약수가아님을보이면 된다. 먼저 d k 임을보이고, 그다음 d < k 이면 r 의위수가 4k 미만임을보인다. () p = 4k +3 이라면 ϕ(p) = p 1 = (k +1) 이된다. p 1 = k +1 이므로 ( r) k+1 p 1 이고 ( m < k + 1) ( ( r) m p 1 ) 을보이면된다. ( r) m p 1 이면 r m p 1 이라는모순을 얻는다. (8) #8 : (1) f(x) p 0 의해가 p 1 개인데 f(x) 의차수는 p 이하이다. 여기서라그랑즈의 정리 4.18 을이용한다. () f(p) 5 차잉여 5.1 차합동식 소수를법으로하는 차합동방정식을푸는 개의방법을소개한다. Exmple 5.1 (p183, 인수분해 ) 차합동방정식 x + 11x 를풀어보자. 차항의계수 를 1로바꾸기위하여 의역원 7을양변에곱하고인수분해한다. x + 77x x x (x 3)(x + ) 13 0 이제소수보조정리 1.6 에의하여 x 13 3, 를해로얻는다. Exmple 5. (p184, 완전제곱식으로변환 ) (1) 3x + x x + 9x x 4x x 4x (x ) 13 3 x 13 ±3 x 13 5, 1, ( 라그랑즈의정리에의하여해는 개이하임.) () x + x x 4x x 4x (x ) 5 3, ( 해가없다.) 소수 p 3 를법으로하는모든 차합동식은 30

31 x p (5.1) 꼴로 변환된다. 이 식은 의 값에 따라 해를 가질 수도 있고 가지지 않을 수도 있다. (5.1)의 해가 존재할 때면이 Up 를 법 p에 대한 차잉여(또는 제곱수)라고 한다. 제곱수 전체의 집합을 Q p 로 나타내고, Qp = Q p Up = Q Zp 로 정의한다. 이때의 해 x를 의 법 p에 대한 제곱근이라고 한다. Q p 는 1을 원소로 가지고, 곱셈과 역원에 대하여 닫혀 있다. (주의). 교재에서는 기호 Q p 를 쓰지 않으며, Qp 는 이 강의노트의 Q P 를 의미한다. (5.1)의 해를 구하기는, p185: [보기]에서 보듯이 법 p가 비교적 작은 소수일 때는 쉽다. Exercise 5.3 (p185: 13.1) 소수 p > 와 Up 에 대하여 다음은 모두 동등함을 보여라. (i) 는 제곱수이다. (ii) 는 Up 의 어떤 원소의 제곱과 법 p로 같다. (iii) %p는 Up 내에서 법 p에 대한 제곱근을 가진다. Discussion 5.4 (p186) 법 13에 대한 제곱수를 U13 안에서 찾아보자. 각 U13 에 대해서 = (13 ) 이므로 1,..., 6의 제곱만 살펴보면, 즉 1,..., ( p 1 ) 만 보면 된다. 아래에 p = 3, 5, 7, 11, 13에 대한 제곱수들을 보였다. 1,..., ( p 1 ) 가 모두 법 p로 서로 다르다는 사실의 증명은 p187에 나와 있는데, 실은 다 음과 같이 더 쉽게 증명된다. 1 j < i p 1 일 때 p (i j ) = (i + j)(i j)가 성립하려면 p i + j 또는 p i j여야 하는데 i ± j > 0의 최댓값은 원소의 개수는 5. p 1 이다. 결론: Qp = p+1 p 1 < p이기 때문이다. 따라서 Qp 의 제곱수 판정, 오일러와 르장드르 Theorem 5.5 (p187: 13.) 소수 p > 의 임의의 원시근 r에 대하여 법 p에 대한 가역원소 가 제곱수인 것은 indr ()가 짝수일 필요충분조건이다. 따라서 원시근은 제곱수가 될 수 없다. Proof. 임의의 가역원소는 원시근의 거듭제곱임을 이용한다. Theorem 5.6 (오일러의 제곱수 판정 기준, p188: 13.4) 소수 p > 와 Up 에 대하여 다음 이 성립한다. (1) p 1 p ±1 () Q p p 1 p 1 Proof. Esy. 31

32 Corollry 5.7 (p189: 13.5) 소수 p > 와, b U p 에대하여 b Q p {, b} Q p or {, b} Q p = 가성립한다. Nottion 5.8 소수 p > 와 U p 에대하여르장드르기호 ( p ) 는 ( ) = p 1, if Q p, 1, otherwise 로정의된다. Exercise 5.9 (p189: 13.6) 소수 p > 와, b U p 에대하여다음이성립함을증명하여라. (1) p b ( p ) = ( b p ) () ( p ) = 1 (3) ( b p ) = ( p )( b p ) (4) ( p ) p p 1 (5) ( 1 p ) = ( 1) p 1 Exercise 5.10 (p190) 소수 p > 와, b Up, k Z에대하여다음이성립함을증명하여라. ( ) 1 1, if p = 4k + 1, (1) = p 1, if p = 4k + 3. ( ) ( ) ( ) ( ) + kp b () =, =. p p p p Exmple 5.11 르장드르기호를사용하여다음 차합동식의해의존재성을판정해보자. x (5.) ( 풀이 ). 위의두연습문제의결과를적용하여 ( ) 46 = 17 ( ) 1 46 = 17 ( 1 17 여기서오일러의판정기준을적용하면 ) ( ) 46 = (17 1)/ = 3 8 = 81 = ( 4) = ( ) 1 = 17 이므로 (5.) 는해를가지지않는다. 한문제더보자. ( ) 3 = 17 ( ) x (5.3) 3

33 ( 풀이 ). 아래의계산에서앞의문제와다른점을찾아보라. ( ) ( ) ( ) ( ) ( ) = = = = ( ) ( ) ( ) ( ) ( ) = = = = = 그러므로 (5.3) 은해를가진다. Discussion 5.1 p191 에나와있는소수 p > 에대한아래의사실들은아주쉽게증명할수 있는데, 교재에서는제곱근의개념과라그랑즈정리를굳이사용하여설명하였다. ( ( ) ( ) (1) 1 p) + p + + p 1 p = 0 () b 가 x p 의해이면 ±b 가이 차합동식의모든해이다. (3) ( 정리 13.8) p 4 1 이면 x p 1 의해는 ± ( p 1 )! 이다. Theorem 5.13 (p19) p가 4k + 3 꼴의소수일때 Z에대하여 x p 가해를가진다면그해는 x p ± p+1 4 이다. ( 증명 ). Wlog Up 이다. 가제곱수이므로오일러의판정기준에의하여 p 1 p 1이다. b = p+1 4 Z로두면 b = p+1 = p 1 +1 = p 1 p 이다. 이제 5.1.() 에의하여원하는결론을얻는다. Exmple 5.14 (p19) 차합동식 x 3 3 의해를구해보자. 3 (3 1)/ = 3 11 = = = ( 5) 9 = 이므로오일러의판정기준에의하여이합동식은해를가진다. 3 = 이므로그해는 ±3 (3+1)/4 = ±3 6 = ±(7) 3 ±4 = ±16 이다. Discussion 5.15 앞서 4k + 3 꼴의소수가무한히많다는것을증명한바있다. 이번엔 4k + 1 꼴의소수도무한히많음을증명해보자. 이를부정하여 p 1,..., p n 을모든 4k + 1 꼴소수의 나열이라고가정하고모순을유도한다. N = (p 1 p n ) + 1 로두면 N 은홀수이지만위의가정에의해서소수가아니다. 그러므로 N 의소인수를하 나취할수있는데, 이를 p 로두면이것은홀수이다. 그런데 p N = (p 1 p n ) + 1 는곧 (p 1 p n ) p 1 을뜻하고이제 5.10.(1) 에의하여 p = 4k + 1 꼴이어야한다. p = p i 로두면 p (p 1 p n ) = N 1 을얻게되고이는 p N 에모순이다. 5.3 차잉여의상호법칙 홀의소수 p, q에대하여 x p q가해를가지는 ( ) 것과 ( x q p가해를가지는것사이에어떠한연관관계가있는가? 이는르장드르기호 p q 와 q p) 의부호들이언제같고언제다른지에 33

34 대한 어떤 규칙이 있는지에 대한 물음이다. 다음의 정리에 그 답이 있으며, 몇 개의 p, q에 대하여 이 정리가 참임을 그 아래의 표에서 관찰할 수 있다. Theorem 5.16 (차잉여의 상호법칙, p195: 14.1) 서로 다른 홀의 소수 p, q에 대하여, p if p 4 1 or q 4 1, q q, = (5.4) p, otherwise. p q 정리 5.16의 증명을 위하여는 준비작업이 필요하다. 아래의 정리는 주어진 수가 제곱수인지를 판별하는, 오일러의 판정기준과는 다른, 하나의 방법을 제시한다. Theorem 5.17 (가우스의 차잉여 보조정리, p196: 14.) 소수 p > 와 Up 에 대하여, p Vp = {1,,..., p 1 } = {x Up x < } 로 정의하고, x 7 x%p의 연산에 의하여 Vp 로부터 이탈 한 것들의 집합, 즉 S = {y Up y > p, ( x Vp )(y = x%p)} 의 원소의 개수를 n이라고 놓았을 때 p = ( 1)n 이다. p = 13인 경우 = 에 대해서 위의 보조정리를 적용해 보라. 또한 = 3에 대해서 다시 적용해 보라. Q13 여부가 오일러의 판정기준을 적용했을 때와 같음을 확인하라. (증명). f : Vp Up 를 f (x) = x%p로 정의하면 이탈자들의 집합 S = f (Vp ) Vp = {s1,..., sn } 이다. R = f (Vp ) S = {r1,..., rm } 으로 두어 f (Vp ) = R ] S로 분할한다. 이제 S 0 = {p s s S} Vp 로 두었을 때 Vp = R ] S 0 이 됨을 보이겠다. 34

35 V p R S 는당연하다. 는 V p = R S = m + n 를보임으로써증명하기로한다. 이것은 R S = 임을보이면충분하다. R S 를가정하고 r i = p s j R S 로놓은 다음모순을유도하겠다. r i = x%p, s j = y%p 인 x, y V p 를취한다. 그러면 r i + s j = p r i + s j p 0 (x + y) p 0 x + y p 0 를얻게되는데이는 0 < x + y < p + p = p 이므로불가능하다. 이제 V p = R S 이므로각변의모든원소들을곱한결과도같을것이다. 따라서 p 1! = r 1r r m (p s 1 )(p s ) (p s n ) = ( 1) n r 1 r r m s 1 s s n ( ) p ( 1) n ()() p 1 = ( 1) n p 1 p 1! 를얻게되고, 이로부터 n 이짝수이면이 p 1 p 1 임을알수있다. 이제오일러의판정기준을 사용하면원하는결론을얻는다. Theorem 5.18 소수 p > 에대하여, ( ) 1, if p 8 1, 7, = p 1, if p 8 3, 5. (5.5) ( 증명 ). {1,,..., p 1 } 의각원소를 배하고 p로나눈나머지중에 p 이상인것들의집합은 {m p m p 1} 이다. 이것이곧이탈자들의집합이다. 이것의원소의개수 n은 n = {m p 4 m p 1 } = p 1 p 4 (5.6) 오얻어진다. (5.6) 의 p 에 8k + 1, 3, 5, 7 을각각대입하여 n 이짝수여부를관찰하면원하는결 과를얻을수있다. Corollry 5.19 ( ) = ( 1) p 1 8 p (5.7) 이제 5.9.(),(3) 과 (5.7) 에의하여 인경우에대해서는별도의식이 5.9.(5) 에나와있다. ( p) 의값은 가홀수일때만알면계산할수있다. = 1 Theorem 5.0 ( 가우스의 차잉여정리, p00: 14.4) 소수 p > 와홀수 Up 에대하여 ( ) = ( 1) λ, where λ = p 1 p k=1 k p 이다. ( 증명 ). 가우스의보조정리 5.17 에서의 35

36 V p = {1,..., p 1 }, R = {r 1,..., r m } V p, S = {s 1,..., s n } U p V p 및 S = {p s s S} 를그대로사용한다. 그러면 {x%p x Vp } = R S, V p = R S 이다. 우리의목표는 λ n을보이는것이다. 다음과같이계산한다. Vp = p 1 k=1 k = m i=1 r i + n j=1 (p s j) = m i=1 r i + np n j=1 s j. x = r + np s, where x = V p, r = R, s = S. ( 1) 한편, R S = R + S = r + s = p 1 k=1 (k%p) = p 1 k=1 k (k p p) = x pλ ( ) ( 1) ( ) 를계산하면 (1 )x + pλ = np s 를얻는다. 위의식을법 로보면원하던 λ n 을얻는다. 이제 차잉여상호법칙을증명하겠다. 서로다른홀의소수 p, q에대하여, ( ) ( ) q p q, if p 4 1 or q 4 1, = ( ) p p q, otherwise. (5.8) ( 증명 ). 모든홀수 p에대해서 p가 4k + 1 꼴인것은 p 1 가짝수일필요충분조건이다. 따라서 (5.8) 은아래의식과동등하다. ( q p ) ( p q ) = ( 1) p 1 q 1 (5.9) 아래의그림이이증명의이해에도움이될것이다. 좌표평면위에서격자점들의집합 3 개를아래와같이정의한다. R = {(x, y) Z 0 < x < p, 0 < y < q } A = {(x, y) R y < q p x} 36

37 B = {(x, y) R y > q p x} 직선 y = q px 위에는격자점이존재하지않으므로 R = A B이고, 따라서 R = A + B 이다. 가우스의 차잉여정리 5.0에의하여 ( ) q = ( 1) A, p ( ) ( ) q p p q ( p q ) = ( 1) B = ( 1) A ( 1) B = ( 1) A + B = ( 1) R = ( 1) p 1 q 1 Exmple 5.1 (p04) 르장드르기호 ( 9 53) 을계산해보자. 9 = 이므로분자, 분모를뒤바꾸어도된다. ( 9 53 ) = ( 53 9 ) = ( ) 4 = 9 9 = 이므로 ( 9) = 1이고, ( ) ( ) ( ) 3 9 = = = ( ) 3 = 9 ( ) ( ) 이다. 따라서 ( 9 53) = ( 1) ( 1) = 1 이다. 르장드르기호의값을계산할때는위의예에서보듯이분자의소인수분해가빈번하게요 구되며이단계에서계산시간이많이소모된다. 소인수분해를하지않고도르장드르기호의 값을계산하기위하여야코비기호가도입되었다. Definition 5. ( 야코비기호, p04) 홀수 n 3의소인수분해가 p 1 p p r 일때 Un 에대해서야코비기호 ( ) n J 는 ( ( ) ( ) ( ) n) J 로정의된다. = p 1 p p r 르장드르기호의 분모 는홀의소수이어야만하는데반하여야코비기호의분모는임의의홀 의자연수일수있다는점이다르다. 그런데분모가소수가아닐때는야코비기호에서첨자 J 를구태여쓰지않아도르장드르기호로혼동할염려가없으므로첨자 J 는생략해도된다. 야코비기호의값은 ±1들의곱이므로역시 ±1이된다. 그런데야코비기호는그자체로는의미가없다. 예를들어 ( ) n J 1 = 1이라고해서 x n 의해가존재하는것은아니다. ( 예 : ( ) 7 15 J = ( ( 7 7 3) 5) = ( 1) = 1이지만 x 15 7의해는존재하지않는다.) 야코비기호는르장드르기호의값을계산하는도구로서의의미만가진다. Fct 5.3 (p05: 14.5) 홀의자연수 m, n 3 과 gcd(, mn) = gcd(b, mn) = 1 인, b Z 에 대하여다음이성립한다. (1) n b ( ( n) = ) n () ( ) ( b n = ) ( ( ) b n n), 따라서 n = 1 (3) ( mn) = ( m) ( n), 따라서 ( n ) = 1 Exercise 5.4 (p06) x, y 가홀수일때다음이성립함을증명하려라. 37

38 (1) ( 1) x 1 () ( 1) x 1 8 ( 1) y 1 ( 1) = ( 1) y 1 8 xy 1 = ( 1) x y 1 8 Theorem 5.5 (p06: 14.6) n 3이 홀수일 때 다음이 성립한다. (n이 소수일 때 성립하던 식과 동일하다. 연습문제 5.9.(5), 따름정리 5.19.) (1) 1 n () n = ( 1) = ( 1) n 1 n 1 8 (증명). 연습문제 5.4의 결과를 이용한다. Theorem 5.6 (p07: 14.7, 상호법칙) gcd(m, n) = 1인 홀수 m, n에 대하여 m n n 1 m 1 = ( 1) n m (5.10) 이 성립한다. (m, n이 소수일 때 성립하던 (5.9)와 동일한 식임.) (증명). m, n이 모두 소수일 때 (5.10)이 성립함을 (당연히) 이용한다. n이 소수일 때 (5.10)이 성립함을 m에 대한 완전귀납법을 써서 증명한다. 그 다음은 n이 합성수일 때, (5.10)이 성립함을 n에 대한 완전귀납법을 써서 증명한다 연분수 연분수와 근사분수 Nottion 6.1 (pp3 4) 0 Z, 1,,... N일 때 1 [0, 1,,...] = 를 연분수라 한다. (엄격한 정의는 (6.3)과 Definition 6. Remrk 6.7을 참조할 것.) 38

39 i 들이정수가아닌실수인경우도허용하여이론을전개할수있다. i 들이정수인경우를단순연분수라부르기도하는데우리는단순연분수만공부할것이며이를부를때 단순 을빼고그냥 연분수 라고부를것이다. [ 0, 1,,...] 대신 [ 0 ; 1,,...] 를쓰기도한다. 수열 [ 0, 1,,...] 이유한수열일때이를유한연분수라하고무한수열일때는무한연분수라한다. 1,,... 들을부분분모라하며이들은모두양수이어야한다. (pp5 6) 모든유리수 q는어떤유한연분수 [ 0 ; 1,..., n ] 으로표현된다. (p7: 정리16.) 또한 n = 0 또는말항 n 의조건하에서는이표현은유일하다. pp3 7의예들을보라. 무리수 3, 또는 π를연분수로나타낼수있겠는가? 이들을나타내는연분수가존재하는가? 그리고연분수가존재한다면이를찾는알고리듬이존재하는가? (p40: 정리17., p44: 정리17.5) 모든무리수는무한연분수로유일하게표현된다. Definition 6. (p8, p9: 16.3) (1) 연분수 ( 무한또는유한 ) [x 0, x 1, x,...] 가주어졌을때제k근사분수 C k 는부분수열 [x 0, x 1, x,..., x k ] 가나타내는분수이다. () 수열 (p k, q k ), (k ) 를다음과같이정의한다. (p, q ) = (0, 1), (p 1, q 1 ) = (1, 0) (p k, q k ) = (p k + p k 1 x k, q k + q k 1 x k ), (k 0). Exmple 6.3 (p31) 위의정의에따라 [1, 1, 1, 1, 1, ] 에대한 (p k, q k ) 5 k= 를계산해보자. C k 도함께계산해본다. C k = p k q k 가항상성립함을알수있다. gcd(p k, q k ) = 1도확인된다. 이사실은정리 6.6.(3) 에의하여증명된다. 이연분수알고리듬을앞서공부했던 확장된유클리드 알고리듬 과비교해보라. k x k p k q k C k C 0 = 1, C 1 = =, C = C 4 = C 3 = = 8 5, C 1 5 = = = 3, C 3 = = = C 4. 이번에는 [1,,3,4,5,6] 에대해서도같은작업을해보아라. = = 5 3, 이예로부터 C k+1 을직접 C k 로부터얻는점화식은얻기어렴움을알수있다. C k+1 을 C k 와 C k 1 로부터얻는점화식은얻을수있겠는가? (p30) [x 0, x 1,...] 에연분수알고리듬을적용하여 k =, 1, 0, 1까지계산한결과를아래에보였다. 39

40 k x k x 0 x 1 p k 0 1 x x 0 x 1 q k x 1 Theorem 6.4 (p30:16.4) 모든 k 0 에대하여 C k = [x 0, x 1,..., x k ] = p k q k (6.1) Proof. k = 0, 1인경우에는각각 C 0 = x 0 = p 0 q 0, C 1 = x x 1 = 1+x 0x 1 x 1 = p 1 q 1 이성립함을바로 위에보인표로부터확인할수있다. 이제모든 k n에대해서 (6.1) 이성립함을가정하고 [x 0, x 1,..., x n, x n+1 ] = p n+1 q n+1 (6.) 를보이겠다. [x 0, x 1,..., x n 1, x n, x n+1 ] = [x 0, x 1,..., x n 1, x n + 1 x n+1 ] (6.3) 이므로 y n = x n + 1 x n+1 로두고 [x 0, x 1,..., x n 1, y n ] 의 p값, q값 을각각 p i, q i, ( i n) 로나타내기로하면 (6.3) 과 y n 의정의및귀납가설에의하여 [x 0, x 1,..., x n 1, x n, x n+1 ] = [x 0, x 1,..., x n 1, y n ] = p n q n 이된다. 이제우리의목표 (6.) 는 p n q = p n+1 n q n+1 으로변경되었다. 여기서 (p i, q i) = (p i, q i ), for i n 1 가성립함은당연하다. 이제 (p n, q n) 을구하기위하여먼저 p n 만계산해보면 p n = p n + p n 1y n = p n + p n 1 (x n + 1 x n+1 ) = p n + p n 1 x n + p n 1 x n+1 = p n + p n 1 x n+1 이므로 q n 은같은방법으로 q n = q n + q n 1 x n+1 이될것이다. 그리하여이제우리의목표인 p n q n = p n + p n 1 x n+1 q n + q n 1 x n+1 를얻는다. = p nx n+1 + p n 1 q n x n+1 + q n 1 = p n+1 q n+1 이제우리가증명해야할것은수열 (C k ) k=0가수렴한다는사실이다. Remrk 6.5 (p3) 연분수알고리듬의점화식 [ 정의 6..()] 는다음과같이행렬을이용하 여나타낼수있다. [ ] [ ] p p =, 1 0 q q 1 [ ] [ ] pk p k 1 1 = q k q k 1 x k [ pk q k ]. 40

41 Theorem 6.6 (p3:16.5) [x 0, x 1,...] 에연분수알고리듬을적용하여얻은 (p k, q k ) 에대하여, [ ] pk 1 p k R k =, (k = 1, 0,...) A k = q k 1 q k [ ] 0 1, (k = 0,...) 1 x k 로정의하면각 k = 0, 1,... 에대하여다음이성립한다. (1) R k 1 A k = R k, () R k = R 1 A 0 A 1 A k, (3) det(r k ) = p k 1 q k p k q k 1 = ( 1) k. (4) gcd(p k, q k ) = 1 (5) C k C k 1 = ( 1)k 1 q k q k 1 Proof. Strightforwrd. Theorem 6.7 연분수의근사분수의수열 (C k ) k=0는반드시수렴한다. Proof. (pp35 36) 연분수 [x 0, x 1, x,...] 에서 x k, (k 1) 는모두자연수이므로 q k, (k 0) 는 자연수의증가수열을이룬다. 정리 6.6.(5) 를보면 C k 는증가와감소를교대하며수렴함을알 수있다. Remrk 6.8 (p34) 정수, b 가주어졌을때 gcd(, b) = u + bv 인계수 u, v Z 를구하는 알고리듬은앞서단평 1.50 에서알아본바있다. gcd(, b) = 1 일때는계수 u, v 를아래와같이 연분수를이용하여구하는방법이있다. b = [ 0, 1,..., n ] 으로놓으면 C n = p n q n = b, C n 1 = p n 1 q n 1 이된다. 정리 6.6.(3) 에의하여 p n 1 b q n 1 = ( 1) n 이고, 따라서 ( ( 1) n 1 q n 1 ) + b ( ( 1) n p n 1 ) = 1 이된다. 그러므로 u = ( 1) n 1 q n 1, v = ( 1) n p n 1 를얻는다. p34 의예제 16.8 을보라. Exercise 6.9 det(r k ) = det(r k 1 ) 가성립함을정의 6.로부터직접증명하여라. (det(r k ) = det(r k 1 ) 가성립함은정리 6.6.(3) 을보면쉽게알수있지만...) Exercise 6.10 p37: #1, #, #3( 근사분수는하나의연분수에대하여여러개존재한다.), #6( 연분수를이용하여 ), #7(k에대한귀납법사용 ), #8(α 1일때는?) 41

42 6. 제곱근의연분수 Definition 6.11 (p51) 순환연분수 [ 0, 1,..., m, b 1,..., b n ] 은 m = 0 일때순순환연분수 라고한다. Definition 6.1 (p5) 완전제곱수가아닌자연수 d 에대하여 r + s d, r, s Q 형태로나타낼수있는실수를 차무리수라고한다. r s d 를 r + s d = α 의켤레무리수 (conjugte) 라고하고 α 로나타낸다. Theorem 6.13 (p5) 무리수가어떤정수계수 차방정식의근인것은그것이 차무리수일 필요충분조건이다. Theorem 6.14 (p53: 18.1) 순환연분수는 차무리수이다. Theorem 6.15 (p55, 라그랑즈알고리듬 ) 모든 차무리수는아래에정의된알고리듬에의 하여연분수로표현할수있다. ( 증명 ). 차무리수 θ = + b, (, c Z, c 0, d N N ) c 가주어졌을때다음과같이 θ k, k, m k, λ k, (k 0) 를잡는다. 1 θ = + b 가된다. c = c+ bc c 이므로 d = bc, λ 0 = c, m 0 = c 로두면 θ = m 0 + d λ 0, λ 0 (d m 0) k = 0, 1,,... 에대하여 (i) θ k = m k+ d λ k (ii) k = θ k (iii) m k+1 = k λ k m k (iv) λ k+1 = d m k+1 λ k 로둔다. Theorem 6.16 (p56: 18.) 차무리수의연분수는순환연분수이다. Theorem 6.17 (p57: 18.3) 차무리수 θ 가순순환연분수이기위한필요충분조건으로 이있다. θ > 1 nd 1 < θ < 0 Theorem 6.18 (p58: 18.4) d N N 에대하여 d 의연분수는 d = [b, 1,,..., n 1, b] 꼴이다. 4

43 6.3 펠방정식 Definition 6.19 ( 펠방정식, p63) x dy = ±1, (d N N ) (6.4) 형태의 ( 정수 ) 부정방정식을펠방정식 (Pell s eqution) 이라고한다. 펠방정식 x dy = ±1 의해는 d 의연분수와밀접한관계가있다. Lemm 6.0 (p64: 19.1) 무리수 θ 의제 k 근사분수가 p k q k 라하면 1 θ 의제 k 근사분수는 q k 1 p k 1 이다. Theorem 6.1 (p65: 19.) (p, q) 가펠방정식 x dy = ±1 의양의해이면 p q 는 d 의연 분수의어떤근사분수이다. d 의연분수의성질을이용하여펠방정식 x dy = ±1 모든양의해를구해보겠다. Theorem 6. (p67: 19.5) 펠방정식 x dy = ±1 에서, d 의연분수의주기를 n, 제 k 근사분수를 p k q k 라하면, (1) n 이짝수일때, x dy = 1 은해를가지지않는다. x dy = 1 의모든양의해는 (p nj 1, q nj 1 ), (j = 1,, 3,...) 꼴이다. () n 이홀수일때, x dy = 1 의모든양의해는 (p nj 1, q nj 1 ), (j = 1, 3, 5,...) 꼴이다. x dy = 1 의모든양의해는 (p nj 1, q nj 1 ), (j =, 4, 6,...) 꼴이다. Theorem 6.3 (p69: 19.6) 펠방정식 x dy = ±1 에서, d 의연분수의주기를 n, 제 k 근사분수를 p k q k 라하면, (1) n 이짝수일때, x dy = 1 의최소양의해는 (p n 1, q n 1 ) 이다. () n 이홀수일때, x dy = 1 의최소양의해는 (p n 1, q n 1 ) 이다. x dy = 1 의최소양의해는 (p n 1, q n 1 ) 이다. Theorem 6.4 (p71: 19.8) 펠방정식 x dy = 1 의최소양의해를 (x 1, y 1 ) 라하면, 이 방정식의모든양의해는 n = 1,, 3,... 에대하여 (x 1 + y 1 d) n 로주어진다. 43

44 Theorem 6.5 (p7: 19.9) 펠방정식 x dy = 1에서 d의연분수의주기가홀수라하자. 이방정식의최소양의해를 (x 1, y 1 ) 라하면 (1) x dy = 1의모든해는 (x 1 + y 1 d) n, (n = 1, 3, 5,...), 로주어지며, () x dy = 1의최소양의해는 (x, y ) 이고, 모든양의해는 (x 1 + y 1 d) n, (n =, 4, 6,...) 로주어진다. 단 (x, y ) 는 x + y d = (x1 + y 1 d) 으로정의된다. 44

45 찾아보기 b, 3 x, 4 x, 4 /b, 5 b%, 4 gcd(, b), 7 lcm(, b), 7 k, 3 L(, b), 7 τ(n), σ(n), 1 n, 14 (mod n), 14 1, 16 Un, U n, 0 ϕ(n), 0 ord n (), 5 ind (x), 6 Q p, Q p, 31 ( p ), 3 ( n ) J, 37 [ 0, 1,,...], 39 [ 0 ; 1,,...], 39 C k, 39 (p k, q k ), 39 α, 4 차무리수, 4 Archimedin Property of rel numbers, congruence reltion, 15 conjugte irreducible number, 4 continued frction, 39 Division Algorithm, 4 Euclid Algorithm, 9 extended, 9 Euclid s Lemm, 8 Euler s function, 0 Fermt s little theorem, 0 Fundmentl Theorem of rithmetic, 11 gretest common divisor, 7 inverse modulo n, 15 invertible element modulo n, 15 lest common multiple, 7 Mthemticl Induction complete, 3 principle of, multiplictive function, 1 order modulo n, 5 Pell s eqution, 43 prime fctor, 10 prime fctoriztion, 10 prime number, 10 quotient, 4 reltively prime, 8 reminder, 4 Well-ordering Principle of integers, 가역원소법 n 에대한, 15 가우스기호, 4 오일러함수정리, 차잉여보조정리, 34 차잉여정리, 35 근사분수연분수의, 39 나눗셈알고리듬, 4 나눗셈합동식보존레마, 15 단순연분수, 39 라그랑즈알고리듬순환연분수, 4 라그랑즈의정리, 8 르장드르, 8 르장드르기호, 3 45

46 메르센소수, 10 메르센수, 10 몫, 4 배선배의법칙, 3 배수, 3 배수판정법, 16 부분분모, 39 부정방정식 1 차, 14 산술의기본정리, 11 상호법칙 차잉여의, 34 서로소, 8 서로소보조정리, 8 소수, 10 소수보조정리, 11 소인수, 10 소인수분해, 10 표준형, 11 확장표준형, 11 수학적귀납법의원리, 순순환연분수, 4 순환연분수, 4 승법적함수, 1 아르키메데스성질실수의, 야코비기호, 37 약수, 3 역원법 n 에대한, 15 역원의존재성레마, 15 연분수유한연분수, 무한연분수, 39 연분수알고리듬, 39 오일러의정리, 3 오일러의함수, 0 완전수, 13 완전잉여계, 17 원시근, 6 원시근정리, 8 위수법 n 에대한 의, 5 윌슨의정리, 0 유클리드알고리듬, 9 확장된, 9 유클리드의레마, 8 이산로그, 6 차잉여법 p 에대한, 31 차잉여의상호법칙, 34 이탈자, 34 정수의정렬성, 제곱근법 p 에대한, 31 제곱수법 p 에대한, 31 중국인나머지정리, 18 지수, 6 진법, 5 최대공약수, 7 최소공배수, 7 켤레무리수, 4 페르마소수, 11 페르마수, 11 페르마판별법, 1 페르마의 ( 소 ) 정리, 0 펠방정식, 43 합동관계, 15 합동식, 합동방정식, 16 호제법유클리드의, 9 46