정수론 - (Number Theory)

정수론 (Number Theory) 정주희 (Jeong, Joohee) Kyungpook National University 2017 년 9 월 4 일. 자연대 101 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 1 / 36

목차 1 최대공약수 2 부정방정식과합동식 3 페르마의정리와오일러의정리 4 원시근, 이산로그, 연분수 5 응용과연습 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 2 / 36

최대공약수 All variables are integers unless stated otherwise. ( a)( b 0)( 1 q)( 1 r)(a = qb + r and 0 r < b ) q = quotient, 몫 r = remainder, 나머지, a%b b a def (b 0) q(a = qb) Fact 1. a ( (±1 a) (a 0 ±a a ±a 0) ) ( a)( b 0)(a b a b ) a b ( (a b) (b a) a = ±b ) a(a ± 1 a = ±1) 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 3 / 36

최대공약수 Fact 2. 약수의약수는약수이다. 배수의배수는배수이다. 배수들의선형조합은배수이다. ( 배선배의법칙 ) Definition 1. gcd(a, b) = c def lcm(a, b) = c def ( (c > 0) (c a) (c b) ( x) ( (x a) (x b) c x )) ( (c > 0) (a c) (b c) ( x > 0) ( (a x) (b x) c x )) 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 4 / 36

최대공약수 Fact 3. gcd 와 lcm 에는교환법칙이성립한다. gcd(a, b) = gcd(b, a), lcm(a, b) = lcm(b, a) Fact 4. 0은모든수의배수이므로, gcd(0, 0) : 존재하지않음 gcd(0, a) : a (a 0) lcm(0, a) : 존재하지않음 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 5 / 36

최대공약수 Theorem a, b 의최대공약수는이둘의선형조합으로서양수인것중에 가장작은것이다. gcd(a, b) = min ( {ax + by x, y Z} N ) Corollary. 최대공약수는모든공약수의배수이다. Problem. 최소공배수는모든공배수의약수임을증명하시오. ( 위의정리를사용할필요가없다.) Problem. a, b의임의의선형조합은 gcd(a, b) 의배수이며역으로 gcd(a, b) 의임의의배수는 a, b의선형조합임을보이시오. Definition. gcd(a, b) = 1일때 a와 b는서로소 (relatively prime) 라한다. (1은모든정수와서로소임.) 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 6 / 36

최대공약수 Definition. 소수 (prime number) 는 1 과자기자신외에는양의 약수가없는 2 이상의자연수이다. Theorem (The Fundamental Theorem of Arithmetic) 임의의 2 이상의자연수 n 은유일한방법으로소인수분해된다. ( 음의정수의소인수분해는그것의절댓값의소인수분해에 1 을곱한것이다.) n = p e 1 1... p em m (p 1 < p 2 < < p m are primes, e i 1) Fact. 두수가서로소라는것은두수가공통소인수를가지지않는다는것을의미한다. a b a와 b를소인수분해했을때 a의각소인수 p 의지수가 b 의 p의지수이하이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 7 / 36

최대공약수 Fact. 두자연수 a, b 가아래와같이소인수분해된다면, a =p e 1 1... p em m and b = p f 1 1... p fm m, p 1 < p 2 < < p m are primes and e i, f i 0 이두자연수의최대공약수와최소공배수는다음과같이 얻어진다. gcd(a, b) = p min(e 1,f 1 ) 1... p min(em,fm) m, lcm(a, b) = p max(e 1,f 1 ) 1... p max(em,fm) m. Problem. gcd(a, b) lcm(a, b) = ab 를증명하시오. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 8 / 36

최대공약수 자연수 n 의소인수분해 n = p e 1 1... p em m (p 1 < p 2 < < p m, e i 1 로부터 n 의양의약수의개수 τ(n) 과이들의합 σ(n) 을얻을수 있다. gcd(n, m) = 1 f (nm) = f (n)f (m) 을만족하는함수 f 를 승법적 (multiplicative) 이라고한다. τ 와 σ 는승법적이다. τ(p n ) = n + 1 σ(p n ) = 1 + p + + p n = pn+1 1 p 1 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 9 / 36

최대공약수 gcd(ka, kb) = k gcd(a, b) k gcd(a, b) gcd(a/k, b/k) = gcd(a, b)/k (k = gcd(a, b) 인경우가특히중요하다.) gcd(a, b) = 1이면 (a k) (b k) ab k이고, 또한 a bk a k이다. gcd(a, b) = gcd(a ± bk, b) = gcd(a, b ± ak) 유클리드알고리듬 : 위의식을 a b > 0인경우에 0 a bk < b가되도록 k를취하며반복적용하면 b = 0가되기직전의 b가최대공약수이다. gcd(a, b) = ax + by인 x, y를구하는알고리듬은 pp58 59에나와있다. 특별히 gcd(a, b) = 1인경우에는연분수를이용하여구하는방법이있다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 10 / 36

부정방정식과합동식 ax + by = gcd(a, b) 를일반화한방정식 (1) ax + by = c 에대해서생각해보자. (1) 이해를가질필요충분조건은 gcd(a, b) c이다. (x 0, y 0 ) 가 (1) 의해이면모든 m Z에대하여 (x 0 + bm, y 0 am) 도 (1) 의해이다. 역으로모든해는이런꼴로얻어진다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 11 / 36

부정방정식과합동식 각 n N 에대하여두자연수간의관계 n ( 법 n 으로같음 ) 을 아래와같이정의한다. (2) a n b def n b a def a b (mod n) 이관계는합동관계이다. 즉, 동등관계이고또한 a 1 n b 1 and a 2 n b 2 a 1 + b 1 n a 2 + b 2, and a 1 b 1 n a 2 b 2 따라서임의의 ( 정수계수 ) 다항식 f (x) = a n x n + a 1 x + a 0 에대하여 x n y f (x) f (y) 이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 12 / 36

부정방정식과합동식 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 으로역수가 존재한다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 13 / 36

부정방정식과합동식 예를들어 n = 7 이면 1 1 7 2 4 7 3 5 7 4 2 7 5 3 7 6 6 7 1 이다. 7은법 7로역수가없으나이건 7 7 0이므로문제가안된다. 즉 7의배수가아닌모든정수는법 7로역수가존재한다. 그러나소수가아닌수, 예를들어법 6으로역수를가지는수는 1과 5밖에없음을금방확인할수있을것이다. Theorem gcd(a, n) = 1 ( b)(ab n 1) 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 14 / 36

부정방정식과합동식 합동 ( 방정 ) 식 (3) ax n c 가해를가질필요충분조건은 gcd(a, n) c이다. Proof. x(ax n c) x y(ax + ny = c) gcd(a, n) c 앞서 (1) 에서 ax + by = c가해를가질조건은 gcd(a, b) c 이었기때문이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 15 / 36

부정방정식과합동식 합동식 ax n c은, gcd(a, n) = 1인경우에는 gcd(a, n) c의조건이당연히만족되므로해를가질것이다. 그리고 x = a 1 c 는해가됨을알수있다. 법 n으로는이것이유일한해이다. 왜냐하면 ax n c n ay이면 n a(y x), 따라서 n y x 이기때문이다. gcd(a, n) = g 1 일경우에는 ax n c 의해가 ( 존재하는경우에는 ) 여럿존재한다. ax n c a g x n/g 이고우변의해는법 n 으로유일하게존재한다. g c g 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 16 / 36

부정방정식과합동식 x 0 를 a g x n/g c g 의해라하면 x 0 + n g 도 a g x n/g c g 의해이고 따라서 ax n c 의해이다. x 0, x 0 + n g, x 0 + 2 n g,..., x 0 + (g 1) n g 는모두마찬가지로 ax n c 의해이다. 이들은법 g n 으로는 동일하지만법 n 으로는구별된다. 따라서 ax n c 의해는 ( 법 n 으로 ) 정확히 g def = gcd(a, n) 개 존재한다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 17 / 36

페르마의정리와오일러의정리 Definition A Z는법 n에대한완전잉여계 ( r {0, 1,..., n 1})( 1 x A)(x%n = r) 예를들어 {1,..., n} 은완전잉여계이다. Theorem {a 1,..., a n } Z가법 n에대한완전잉여계이고 c Z일때 (i) {a 1 + c,..., a n + c} 는법 n에대한완전잉여계이다. (ii) gcd(n, c) = 1이면 {a 1 c,..., a n c} 는법 n에대한완전잉여계이다. 게다가 a i n 0 ca i n 0이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 18 / 36

페르마의정리와오일러의정리 Theorem (Fermat s little theorem) a Z가소수 p의배수가아니면 a p 1 p 1 이다. Proof. gcd(a, p) = 1이므로 p에대한완전잉여계 {1,..., p} 에 a 를곱하여얻은집합 {a, 2a,..., pa} 도완전잉여계이다. 따라서 1 2 (p 1) p a (2a) ((p 1)a) (p 1)! p (p 1)! a p 1 (p 1)! 의역원을위합동식의양변에곱하면원하는합동식을얻는다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 19 / 36

페르마의정리와오일러의정리 Remark. 법 n에대한역원이자기자신인수, 즉 x 2 n 1인 x 에는 1과 n 1이있다. Q1: 이둘외에더있을수있는가? A: 3 2 8 1, 4 2 15 1 등의예가있다. n = p가소수일때는이럴수없다. x 2 1 p 0 p (x 1)(x + 1) x p ±1 Q2: n이소수가아니면어떻게되는가? Theorem. p가소수이면 (p 1)! p 1이다. ( 윌슨의정리 ) 증명의힌트 : {2,..., p 2} 의각원소는그것의역원을이집합내에가지므로 2개씩짝을지을수있다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 20 / 36

페르마의정리와오일러의정리 Remark. 법 n에대한역원이자기자신인수, 즉 x 2 n 1인 x 에는 1과 n 1이있다. Q1: 이둘외에더있을수있는가? A: 3 2 8 1, 4 2 15 1 등의예가있다. n = p가소수일때는이럴수없다. x 2 1 p 0 p (x 1)(x + 1) x p ±1 Q2: n이소수가아니면어떻게되는가? Theorem. p가소수이면 (p 1)! p 1이다. ( 윌슨의정리 ) 증명의힌트 : {2,..., p 2} 의각원소는그것의역원을이집합내에가지므로 2개씩짝을지을수있다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 20 / 36

페르마의정리와오일러의정리 Definition. U n def = {x gcd(x, a) = 1} U n def = {x Z n gcd(x, a) = 1} φ(n) = U n (Euler s function) Fact. φ(p) = p 1 φ(p n ) = p n p n 1 = p n 1 (p 1) φ is multiplicative 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 21 / 36

페르마의정리와오일러의정리 Theorem a U n 이면 a φ(n) n 1. 증명의힌트 : m def = φ(n), U n def = {x 1,..., x m } 이라하면임의의 a U n 에대해서 {ax 1 %n,..., ax m %n} = U n 이다. 이제페르마의 정리의증명을흉내내면된다. Problem. U n 의원소들을모두곱한것은법 n 으로무엇인가? n 이소수일때는이것의값은윌슨의정리에의하여 1 이된다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 22 / 36

원시근, 이산로그, 연분수 Definition n N, a U n 에대하여 a k n 1 을만족하는최소의자연수 k 를 법 n 에대한 a 의위수 def = ord n (a) 라정의한다. Fact. n N, a U n 일때 위수 ord n (a) 는반드시존재한다. a k n 1 ord n (a) k ord n (a) φ(n) a j n a k ord n (a m ) = j ordn(a) k ord n(a) gcd(ord n(a),m) 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 23 / 36

원시근, 이산로그, 연분수 Definition n N일때, ord n (a) = φ(n) 인정수 a Un 를법 n에대한원시근이라한다. Theorem a가법 n N에대한원시근이면 {a%n, a 2 %n,..., a φ(n) %n} = U n 이다. Fact. 법 n에관한원시근이존재한다면 n 이하의양의원시근은 φ(φ(n)) 개존재한다. n = p( 소수 ) 이면 p 1의각약수 d에대해서위수가 d인 U p 의원소의개수는 φ(d) 이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 24 / 36

원시근, 이산로그, 연분수 Theorem 법 n N에대한원시근이존재할필요충분조건은 n = 2, 4, p k, 2p k 이다. ( 단, p는홀수의소수.) Definition a Z가법 n N에대한원시근일때, 각 x Un 에대하여 a를밑으로하는 x의이산로그 ind a (x) {1,..., φ(n)} 를 x n a k 를만족하는최소의자연수 k로정의한다. Q: ind a (x) 와 log a (x) 의같은점과다른점은무엇인가? 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 25 / 36

원시근, 이산로그, 연분수 Fact. a가 n을법으로하는원시근일때모든 x, y Un, m N 에대하여다음이성립한다. x n y ind a (x) = ind a (y) ind a (xy) φ(n) ind a (x) + ind a (y) ind a (x m ) φ(n) m ind a (x) a inda(x) n x ind a (a m ) φ(n) m 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 26 / 36

원시근, 이산로그, 연분수 Notation. a 0 Z, a 1, a 2,... N일때 1 [a 0, a 1, a 2,...] = a 0 + 1 a 1 + a 2 + 1... Fact. 모든유리수는 a n > 1 의조건하에서는 [a 0, a 1,..., a n ] 으로 유일하게표현된다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 27 / 36

응용과연습 gcd(a, n) = 1이고 gcd(b, n) = 1이면반드시 gcd(ab, n) = 1 인가? 역은어떠한가? a n 1이고 b n 1이면반드시 ab n 1인가? 역은어떠한가? gcd(a, n) = 1과 a n 1 간의함의관계는? a n 1이고 a m 1이면 a nm 1인가? 역은어떠한가? 우변의 1을 c로바꾸면어떻게되는가? 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 28 / 36

응용과연습 Theorem. ( 중국인나머지정리 ) 연립합동방정식 x n1 a 1, x n2 a 2,..., x nr a r 의해는, n i 들이쌍마다서로소이면, 법 n 1 n 2 n r 로유일하게존재한다. Proof. 유일성은당연히성립하므로존재성만증명하기로한다. r = 2, n 1 = n, n 2 = m인경우에대하여먼저증명하겠다. 오일러함수를이용하는증명 : 함수 f : U nm U n U m 을 f (x) = (x%n, x%m) 로정의했을때이것이전사임을보이겠다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 29 / 36

응용과연습 오일러의 φ 함수가승법적이므로 U nm = U n U m 이고, 원소의개수가같은두유한집합간의함수는단사일때면이전사이므로 f 가단사임을보이면되는데, (x%n, x%m) = (y%n, y%m) n x y and m x y nm x y x U mn 이면 x%n U n and x%m U m 임은 서로소 공통소인수없음 을생각하면곧알수있다. ( 여기서는 m, n이서로소임을필요로하지않는다.) 이로써 gcd(n, a) = 1 = gcd(m, b) 인경우에는 x n a, x m b의해가법 nm으로유일하게존재함을증명하였다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 30 / 36

응용과연습 이제일반적인경우를생각해보자. gcd(n, a) def = g 1, gcd(m, b) def = g 2 로두면 a/g 1 U n/g1 and a/g 2 U m/g2 이므로 x n/g1 a/g 1 and x m/g2 a/g 2 인 x 이법 nm/g 1 g 2 으로 유일하게존재함을안다. x g 1 n a 이고 x g 2 m b 이므로 x def = x g 1 + nq 1 = x g 2 + mq 2, 즉 nq 1 mq 2 = x (g 2 g 1 ) 인 q 1, q 2 Z 를찾으면된다. 이것은 gcd(n, m) = 1 에의하여 보장된다. 이로써 r = 2 인경우에대한중국인나머지정리의 증명이완성되었다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 31 / 36

응용과연습 r > 2인경우에는수학적귀납법을사용한다. (4) x n1 a 1, x n2 a 2,..., x nr 1 a r 1, x nr a r 가주어졌을때, n = n 1 n r 1, m = n r 로두면, (5) x n1 a 1, x n2 a 2,..., x nr 1 a r 1 의해는귀납가설에의하여존재할것이므로이를 x라하자. x%n = a, a r = b로두면 (6) x%n = a, x%m = b 의해가존재할것인데, x%n = a인 x는 (5) 의해가되므로, (6) 의해는바로원래의연립합동방정식 (4) 의해가된다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 32 / 36

응용과연습 r = 2 인경우에대한, 오일러의함수를이용하지않는증명 2 개를더제시한다. 증명 1: 함수 f : Z nm Z n Z m 을 f (x) = (x%n, x%m) 로정의하면이함수는단사이며 Z nm = Z n Z m 이므로전사가된다. 증명 2: x n a의해로이루어진집합 {a, a + n, a + 2n,..., a + (m 1)n} 를생각해보자. 이집합은법 m에대한완전잉여계이므로원소중하나, x i = a + i n는 b와법 m으로같다. 그러면 x i n a이고또한 x i m b이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 33 / 36

응용과연습 Remark 1. 중국인나머지정리를이용하여오일러의함수 φ가승법적임을보이는증명은여기있다. 이강의노트를충분히이해한학생들은이웹페이지를읽지않고도이증명을찾을수있을것이다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 34 / 36

응용과연습 Theorem. ( 가우스의정리 ) n N이면 φ(d) = n d n, d>0 Proof. n의소인수의개수 π n 에대한수학적귀납법을사용한다. π n = 1인경우에는 n = p e 으로두면 n의약수는 1, p, p 2,..., p e 이며, 이들의 φ 값은 1, p 1, p 2 p,..., p e p e 1 이다. 따라서 φ(d) = 1+( 1+p)+( p+p 2 )+ +( p e 1 +p e ) = p e = n d n 이다. π n > 1 인경우에는 n = ab, gcd(a, b) = 1, a > 1, b > 1 으로둔다. 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 35 / 36

응용과연습 a 의모든약수들의집합을 {x 1,..., x r }, b 의모든약수들의 집합을 {y 1,..., y s } 로두었을때 n 의모든약수들의집합은 {x i y j 1 i r, 1 j s} 이므로 r s r s φ(d) = φ(x i y j ) = φ(x i )φ(y j ) d n i=1 j=1 i=1 j=1 r s = φ(x i ) φ(y j ) = φ(d) φ(d) = ab = n i=1 j=1 d a d b 이다. - end - 정주희 (Jeong, Joohee) (K.N.U.) 정수론 2017 년 9 월 4 일 36 / 36