4.2 합동연산 합동연산, 이른바 모듈로연산은 제 3장: 군론편에서 이미 한번 소개되었다. 하지만, 다소 설명이 부족했던 관계로, 모듈로연산이 진정 무엇을 의미하는지 조금 더 살펴보 도록 하겠다. 필자는 합동연산의 예제로 5 (mod 4)임을 보였다. 왜냐하면 과 5는

Transcription

1 Chapter 4 정수론 4. 여는 글 2500여년 전, 피타고라스는 만물의 근원을 수라고 주장했다. 수는 단순히 숫자들의 연속이 아니다. 수를 살펴보면 특이한 법칙들로 조화로운 구조를 이룬다. 심지어 그것 이 모두 수 라는 하나의 집합에 포함되어 있지만 실수냐, 유리수냐, 혹자는 정수냐에 따라서 그 성질들은 모두 다르다. 예컨데, 정수집합과 유리수집합의 크기는 ℵ0 이며 실수집합은 연속체이다. 같은 가산무한이지만 유리수는 어디에나 있지만, 정수는 정해진 곳 에만 있다. 그리고 이러한 성질들 덕에 각각의 수에 대한 연구들은 독자적 으로 전개되었다. 그리고 그 중 하나가 정수에 대한 연구, 바로 정수론이다. 정수에 대한 정의가 워낙에 이해하기 쉽고 직관적이다보니, 정수에 대한 연구가 과연 수학의 한 분야로 대접받을 정도로 난해하고 깊이있는 학문일까 의문이 들 수도 있다. 혹자는 오히려 연구가 다 진행될 대로 진행되어 더 이상 연구할 필요가 없는 학 문이 아닐까 하고 의문을 가질 수 있다. 하지만 실상은 반대다. 그만큼 직관적이기에 수 천년전부터 수많은 수학자와 철학자들이 도전해왔고, 그리고 이제는 그렇게 오래 고민했지만 풀리지 않은 난제들로 넘쳐난다. 결국 수학은 수에 대한 학문이다. 수에서 시작되었으며, 수가 수학의 관심거리가 아닐 날은 수학이 끝나는 날까지 오지는 않을 것이다. 피타고라스처럼 모든 것 은 수라고 주장하기는 다소 힘든 부분이 있을지는 몰라도, 결국 수학의 본질은 수 이다. 그리고 가장 기본적인 수, 정수에 대한 연구인 정수론을 이 장에서 소개해볼까 한다. 89

2 4.2 합동연산 합동연산, 이른바 모듈로연산은 제 3장: 군론편에서 이미 한번 소개되었다. 하지만, 다소 설명이 부족했던 관계로, 모듈로연산이 진정 무엇을 의미하는지 조금 더 살펴보 도록 하겠다. 필자는 합동연산의 예제로 5 (mod 4)임을 보였다. 왜냐하면 과 5는 둘 다 4로 나누었을 때 3이기 때문이다. 마찬가지로 5 (mod 7)이며, 또한 (mod 000)이다. 그렇다면 a b (mod n)을 만족하는 세 정수 a, b, n이 있다고 가정해보자. 그렇다 면, a를 n으로 나눠도 b를 n으로 나눠도 둘의 나머지는 동등하다는 의미라 하였다. 이 나머지를 k라고 두자. 이는, a와 b가 n의 임의의 배수에 k를 더한 값이라고 해석할 수 있다. 다시말해, a = in + k 그리고 b = jn + k를 만족하는 정수 i, j가 항상 존재한다는 것이다.2 알파벳이 많이 나와 헷갈린다고? 충분히 그럴 수 있다. 이번엔 위에 소개했던 몇가 지 예제들을 사용해 설명해보겠다. 5 (mod 4)의 예제를 보면, 을 4로 나눠도 5를 4로 나눠도 나머지는 3이다. 즉, 은 어떤 4의 배수에 3을 더한 값이며, 5는 또다른 4의 배수에 3을 더한 값이다. 이는 = 이며, 5 = 이다. 위의 알파벳으로 돌아가보면, 이 a에, 5가 b에, 4가 n에 해당한다. 또한 나머지인 3 은 k에, 몫이었던 2와 3이 각각 i와 j에 해당한다. 5 (mod 7)에 이 법칙을 적용하면, 5 = 이며 = 으로 표현이 가능하다. 그렇다면, a b를 생각해보기로 하자. a = in + k였고, b = jk + n이었으니, a b = in + k jn k = in jn = (i j)n이 된다. 고로 a b는 n의 배수이 며, n (a b)라고 표현이 가능하다. 다시말해, a b (mod n)은, a와 b의 차가 n의 배수라는 의미와 동일하다. 해당 해석은 다음과 같이 유용한 법칙을 유도해낼 수 있다. 임의의 정수 a, b, a0, b0, n 에 대해서 a b (mod n)과 a0 b0 (mod n)이 성립한다고 가정해보자. 그렇다면, a b 와 a0 b0 는 각각 n의 배수이다. 제 2장: 소수편에서 k a와 k b이면 k (a + b)와 k ab가 성립한다는 사실을 배웠으니, 다음과 같은 정리를 유도할 수 있다. 정리 4.. 임의의 정수 a, b, a0, b0, n에 대해서 a a0 (mod n)과 b b0 (mod n)이 성립한다면, a + b a0 + b0 (mod n)이 성립한다. 90

3 a b a0 b0 (mod n)이 성립한다. ab a0 b0 (mod n)이 성립한다. Proof. 일단은 a a0 (mod n)과 b b0 (mod n)이 성립한다 했으니, n (a a0 )과 n (b b0 )이 성립한다는 사실을 염두에 두자. 이는, 다시말해 a a0 과 b b0 는 n의 배수이며, 이를 각각 n의 j배, 그리고 n의 k배로 두자. 즉, a a0 = nj, b b0 = nk 이다. 이를 약간 더 변형해, a = a0 + nj, b = b0 + nk로 둔 채, 증명을 시작해보자. a + b = a0 + nj + b0 + nk이다. 그러므로 a0 + b0 + n(j + k) = a + b이다. 즉, (a + b) (a0 + b0 )는 n의 배수이며, n ((a + b) (a0 + b0 ))이 성립한다. 고로, a + b a0 + b0 (mod n)이다. a b = a0 + nj b0 nk이다. 그러므로 a0 b0 + n(j k) = a b이다. 즉, (a b) (a0 b0 )은 n의 배수이며, n ((a b) (a0 b0 ))이 성립한다. 고로, a b a0 = b0 (mod n)이 성립한다. ab = (a0 + nj)(b0 + nk) = a0 b0 + a0 nk + b0 nj + n2 jk이다. 그러므로, a0 b0 + n(a0 k + b0 j + njk) = ab이다. 즉, ab a0 b0 는 n의 배수이며, n (ab a0 b0 )이다. 고로, ab a0 b0 (mod n)이다. 이 증명이 맞는지, 이번엔 한번 예제를 들어 살펴보기로 해보자. 예컨데 3 (mod 8)과 9 4 (mod 8)을 보자. + 9 = 20이며, = 44이다. 약간의 계산을 하면, 20과 44는 둘 다 8로 나눴을 때 나머지가 4임을 알 수 있다. 그러므로 (mod 8)이다. 뺄셈도 한번 살펴보자. 9 = 2이고, 3 4 = 38이다. 2는 8로 나눠도 나머 지가 2이고, 38 = 8 ( 5) + 2로 표현이 가능하다.3 즉, 나머지가 2이다. 그러므로 2 38 (mod 8)로 잘 성립한다. 마지막으로 곱셈은, 9 = 99이며, 3 4 = 23이다. 두 숫자 모두 8로 나누면 나머지가 3이다. 즉, (mod 8)로 곱셈에서도 역시 잘 성립한다. 비록 a b (mod n)은 a = b와는 다른 개념이지만, 위의 정리에서 본 것 처럼 양변에 동등한 값 을 더하고 빼고 곱해도 해당 식은 성립한다. 아니, 심지어 수 자체 가 동등하지 않더라도 동등한 모듈로 값 을 양쪽에 더하고 곱해도 관계는 성립한다. 9

4 그런의미에서 모듈로 연산은 기존의 연산보다 조금 더 포괄적이고 넓은 개념이라고 할 수 있다. 단, 주의해야 할 점은, 나눌 때는 항상 그렇지만은 않다 는 것이다.4 예 제를 선보여 보라면, 8 80 (mod 8)이며, 2 0 (mod 8)이다. 하지만, 8 2 = 4 이며, 80 0 = 8인데, 4 8 (mod 8)이다. 그러므로 나눗셈에서 만큼은 이 법칙이 성립하지 않는다. 이제 이러한 모듈로연산에 양변에 더하고 빼고 곱해도 성립한다는 것을 알았으니, 이 연산을 유용하게 사용해볼 차례이다. 어떻게 하면 모듈로 연산을 잘 사용했다고 소문날까? 그렇다. 대수학이다. 4.3 약간의 대수학 다음의 식을 한번 해결해보도록 하자. 3x (mod 9) 단, 모듈로연산의 방정식에는 다음 두 개의 규칙이 있다. 첫째는 x는 무조건 자연수만 들어갈 수 있다는 것이다. x의 자리에는 유리수나 무리수같은 숫자가 들어가선 절대 로 안된다는 것이다. 둘째는, 식에 명시된 mod값보다 더 큰 숫자가 들어가선 안된다. 예컨데, 위의 식은 (mod 9)로 정의되었기 때문에 x자리에 9, 혹은 그 이상의 숫자가 들어가선 안된다. 왜냐하면 예컨데 x = 0이라면, 0 (mod 9)이기 때문에 결국 x = 0은 x = 과 동일한 경우로 취급되어지기 때문이다.5 이 두 규칙을 염두에 두고 식을 해결해보도록 하자. 가장 쉬운 답은 x = 2를 들 수 있을 것이다. 모듈로 연산이 아니라고 생각하고 x 를 풀면 해당 답이 나오기 때문이다. 하지만 답이 오로지 그 뿐일까? 한번 다른 답도 있는지 찾아보자. 위에 명시된 두 규칙을 보면, x의 자리에 어차피 9개의 숫자밖에 들어올 수 없다 는 사실을 알 수 있다. 0,, 2,, 8이렇게 말이다. 어차피 숫자도 많은 편은 아니니 하나씩 대입해보도록 하자. 92

5 x 3x (mod 9) x 3x (mod 9) x 3x (mod 9) 표 4.: x값에 따른 3x (mod 9) 해당 표를 보니 3x (mod 9)를 만족하는 값이 무려 3개나 있다. x = 2, 5, 8이렇게 말이다. 어째서 셋일까? 3x여서 셋일까? 그렇다면 다음 식을 살펴보도록 하자. 3x 7 (mod 9) 이번에는 이 아니라 7이다. 위의 표를 살펴보면 3x 7 (mod 9)를 만족하는 값이 없음을 알 수 있다. 그 이유는 3x (mod 9)는 x가 몇이든 상관없이 항상 0, 3, 혹은 만을 내뱉기 때문이다. 3x n (mod 9)라는 식에 있어서 n이 0, 3, 이면 각각에 대응 하는 x값이 3개씩, 그리고 그 이외의 값들이라면 해당 식을 만족하는 x값이 없음을 알 수 있다. 여기서 또 하나 주목할 사실은, 3x 0, 3, (mod 9)을 만족하는 x의 경우의 수는 3이며, 3은 mod뒤에 딸려오는 수, 즉 9를 나눈다는 것이다. 이것이 이 경우에만 국한되는 현상일까? 한번 다른 예제를 살펴보자. 2x (mod 4) 이번 역시도 표를 이용해 이 식을 풀어보자. x 2x (mod 4) x 2x (mod 4) x 2x (mod 4) 표 4.2: x값에 따른 2x (mod 4) 이번 경우에는 해당 식을 만족하는 값이 두 개이며, 그 값이 x = 3과 x = 0임을 알 수 있다. 그리고 2x n (mod 4)라는 식에 대해서 n이 짝수라면 해당 식을 만족하는 x 93

6 가 두 개, n이 홀수라면 해당 식을 만족하는 x가 하나도 없음을 알 수 있다. 이번에도 역시 해당 식을 만족하는 해의 개수 2는 mod뒤에 딸려오는 수, 4를 나눈다. 해의 개수는 mod 뒤의 값을 나눠준다는 것은 사실인 것으로 보인다. 몇몇 독자들은, 3x의 경우에는 답이 있는 식은 답이 3개였고, 2x의 경우, 답이 있는 식은 답이 2개였다는 사실을 주목하면서, 방정식 ax b (mod n)이 답이 있다면 해의 개수는 a개일 것이라 주장할 수 있을 것이다. 과연 그럴까? 마지막으로 식 하나를 더 풀어보도록 해보자. 4x (mod 7) 역시 이번에도 표를 사용해서 풀어보도록 해보자. x 4x (mod 7) x 4x (mod 7) x 4x (mod 7) 표 4.3: x값에 따른 4x (mod 7) 4x (mod 7)를 만족하는 값은 x = 7이다. 허나 이번 경우엔 식을 만족하 는 값이 단 하나 뿐이다. 더 나아가, 4x n (mod 7)에서 n이 몇이든 간에(물론 7 보단 작아야겠지만) 해당 식을 만족하는 x값이 항상 하나씩 있다는 사실 또한 알 수 있다. 이번 경우는 너무나 당연해보이는 사실이지만, 한번 더 짚고 넘어가보면, 식을 만족하는 해의 개수 은 mod뒤에 따라오는 7을 나눠준다. 이제 우리가 아는 사실을 종합해보자.. ax b (mod n)을 만족하는 x값은 하나만 있을 수도, 여럿이 있을 수도, 아예 없을 수도 있다. 2. ax b (mod n)을 만족하는 x값이 하나라면, 0 c < n을 만족하는 임의의 자연수 c에 대해서 ax c (mod n)을 만족하는 x값 또한 단 하나 존재한다. 94

7 3. ax b (mod n)을 만족하는 x값이 여럿이라면, 0 c < n을 만족하는 임의의 자연수 c에 대해서 ax c (mod n)을 만족하는 x값의 개수는 ax b (mod n) 을 만족하는 x의 개수와 같거나 아예 없다. 4. ax b (mod n)을 만족하는 x값이 k개 존재한다면, k n이 성립된다. 하지만 여전히 가장 중요한 의문은 남아있다. 그것은 언제 해당 식을 만족하는 값이 하나이고, 여럿이고, 아예 없냐는 것이다. 그 언제 의 경우를 한번 증명하기에 앞서, 한가지 유용한 테크닉을 소개해볼까 한다. 바로 유클리드 호제법이다. 4.4 유클리드 호제법 초등학교 때 우리는 두 수의 최대공약수를 구하는 방법을 배웠을 것이다. 먼저 두 수를 소인수분해 해준 뒤, 공통된 약수들을 간추려 곱하는 것이다. 초등학교를 졸업한지 꽤 되어서 기억이 가물가물한 독자들을 위해 친히 시범을 보이도록 하겠다. 예컨데 8과 24를 소인수분해 한다고 가정해보자. 8 = = gcd(8, 24) = 2 3 = 위와 같은 방식을 통해 8과 24의 최대공약수는 임을 알 수 있다. 이 방법은 숫 자가 작은 경우에는 매우 편리하지만 숫자가 커지면 매우 복잡해진다는 단점이 있다. 예컨데 4,502,42과 24,00,592의 최대공약수를 구한다고 가정해보자. 일단은 각각의 수를 소인수분해 해주어야 할 것이다.7 하지만 제 2 장: 소수편에서 언급했듯 아주 큰 수를 소인수분해 해주는 데에는 아주 많은 시간이 걸린다. 그러므로 이 방법은 큰 숫자들의 최대공약수를 찾아주는데에 그다지 좋은 방법은 아니다. 그렇다면 아주 큰 수들의 최대공약수는 도대체 어떻게 찾는 것일까? 이에 대하여 유클리드는 두 수의 최대공약수를 찾아내는 알고리즘을 만들었다. 해 당 알고리즘을 유클리드 호제법 이라 부르는데, 다소 그 방법이 번거로울지는 몰라도 큰 수의 최대공약수를 찾는데 최적화 되어있다. 95

8 일단 제 2장: 소수에 소개되었던 나눗셈 법칙 중 하나였던 k (a + b)의 법칙을 떠올려보자. 해당 법칙은, k (a + b)면 k a이고 k b이거나 k - a이고 k - b라는 법칙이었다. 이것과 비슷한 법칙으로 k a이고 k b면 k (a + b)이 있다.(다소 당연 한 고로 증명은 생략하도록 하겠다.)8 해당 법칙은 덧셈의 경우만을 서술하고 있지만, 사실 덧셈이 아니라 뺄셈이어도 해당 법칙은 성립한다. 즉 k a고 k b면 k (a b)역 시 성립한다.(역시 이 증명은 생략하도록 하겠다.) 이 사실을 나눗셈의 법칙에 적용할 것이다. 나눗셈의 법칙이란, a를 b로 나눴을 때 몫을 q로, 나머지를 r로 둔다면, a = bq + r 가 성립한다는 것을 의미한다.(혹은 종종 r = a bq로 표현하기도 한다.) 알파벳들만 나와서 다소 헷갈린다면, 다음의 예제를 주목해보자. 78을 9로 나눠준다고 가정해보자. 그렇다면 몫은 8, 나머지는 이 된다. 78을 9와 8과 으로 표현해주는 방법은 78 = 이다. 여기서 몫인 8이 위의 식에서의 q 에 해당하며, 나머지인 이 r에 해당한다. 이 식을 나눠지는 수(피제수)에 중점을 두지 않고 나머지에 중점을 둔다면 다음과 같다: = 다시 원래의 문제로 돌아와보자. a가 b보다 크며, 나눗셈의 법칙을 사용해 a = bq+r 라고 정의해보자. 그랬을 때, 다음과 같은 정리가 성립한다. 정리 4.2. a = bq + r이라면, gcd(a, b) = gcd(b, r)이다. 이 증명의 방법으로는 여러가지가 있겠다. 물론 a와 b의 최대공약수를 k로 둔 뒤, k가 b와 r의 최대공약수임을 보여주는 방법도 있겠지만, 필자는 다소 다른 방법을 사용해볼까 한다. a와 b의 공약수의 집합이 사실상 b와 r의 공약수의 집합과 정확히 일치한다는 것을 보여줄 것이다. 두 집합이 동일하다면, 두 집합의 가장 큰 원소 역시 동일할 것이다.9 여기서 두 집합이 공약수의 집합이라 하였으니, 가장 큰 원소는 최 대공약수일 것이다. 즉, a, b의 최대공약수와 b, r의 최대공약수는 같다는 논리를 펼칠 것이다. Proof. 임의의 자연수 k가 k a이면서 동시에 k b를 만족한다고 가정해보자. 이제 나눗셈의 법칙을 이용해 r = a bq라고 하자. 최대공약수인 k는 k b를 만족하니, 임의의 q에 대해서 k bq또한 만족한다. 앞서 k a이니, k (a bq)또한 만족시킬 것이 다. 즉, k r이다. 약간의 논리학적 트릭을 사용해, 조건절의 k b를 결과절에도 두도록 하자.0 즉, k a이며 k b면, k b이며 k r이다. 다시말해 k가 a, b의 공약수라면, k는 b, r의 공약수다. 9

9 역으로 k b이며 k r이라고 가정해보자. 그렇다면 역시 임의의 q에 대해서 k bq 가 성립한다. 여기서 둘을 합하면, k (bq + r)이니 고로 k a가 성립한다. 역시 이번 에도 조건절인 k b를 결과절에 가져오면 다음과 같다: k r이며 k b이면, k b이며 k a이다. 고로 k가 b, r의 공약수라면, k는 a, b의 공약수다. 즉, 우리는 a, b의 공약수와 b, r의 공약수가 완전히 일치한다는 것을 보였다. 고로 a, b의 공약수 중 가장 큰 공약수는 b, r의 공약수 중 가장 큰 공약수와 같을 것이다. 그러므로 a, b의 최대공약수는 b, r의 최대공약수이며, 표기로는 gcd(a, b) = gcd(b, r) 이다. 이 증명에서 굳이 k가 a, b의 공약수면 k는 b, r의 공약수다. 와 k 가 b, r의 공 약수면 k는 a, b의 공약수다 를 둘 다 보여준 이유는 a, b의 공약수와 b, r의 공약수가 정확히 일치한다는 것을 보여주기 위함이었다. 만약 k가 a, b의 공약수면 k는 b, r의 공약수다 만을 보여주었다고 가정해보자. 그렇다면 임의의 b, r의 공약수 j가 a, b의 공약수인지는 모르는 것이다. 즉 a, b의 공약수의 모임은 b, r의 공약수의 모임과 동일 하지 않을 수 있으며, 그러므로 그 중 가장 큰 공약수, 최대공약수를 비교하는 과정에서 같지 않다고 나올 수 있다. 그러므로 귀찮더라도 양 방향을 모두 보여준 것이다. 이 정리의 놀라운 점은 두가지가 있다. 첫번째는 r < b라는 것이다. 그리고 a b 라고 가정했으니, a, b > r이 된다. 즉, 아주 큰 두 숫자 a, b의 최대공약수를 구하는 작업에서 a가 더 작은 수 r로 바뀌면서 최대공약수를 구하는 것이 더 쉬워진 것이다. 예컨데 00,00과 20,000의 최대공약수를 구한다고 가정해보자. 00,00을 20,000으로 나누면 몫은 5, 나머지는 이다. 즉, gcd(0000, 20000) = gcd(20000, )이다. 00,00 과 20,000의 최대공약수를 구하는 것은 다소 힘든 일이지만, 20,000과 의 최대공약수 를 구하는 것은 비교할 수 없을 정도로 간편한 일이 되었다. 물론 이렇게 최대공약수를 구하려는 두 숫자가 계산하기 아주 좋게 주어지는 경 우는 드물다. 또한 a를 r로 바꾼다 하더라도, r이 여전히 아주아주 큰 수 일 경우를 배제할 순 없다. 하지만, 너무 걱정할 필요는 없다. 왜냐하면 a, b를 b, r로 바꿨듯, 다시 한번 b, r을 더 작고 간편한 수로 바꿀 수 있기 때문이다. b > r라고 했으니, 이번엔 b 를 r로 나눠주는 것이다. 그랬을 때 몫을 p, 나머지를 s라고 가정하면, 이번엔 다음과 같은 식을 얻을 수 있다. b = rp + s. 여기서 다시한번 위의 정리를 이용해주면, gcd(b, r) = gcd(r, s)가 된다. 고로, gcd(a, b) 97

10 는 gcd(r, s)로 훨씬 더 간편하게 될 수 있다. 이 뿐만이 아니다. r, s를 더 작고 간편한 수로 계속해서 바꿔나갈 수 있다. 한쪽 숫자가 0이 될 때 까지 말이다. 0이면 어떻게 되냐고? 걱정할 필요 없다. 임의의 0이 아닌 숫자 n에 대해서 gcd(n, 0) = n이다. 왜 냐하면, 0은 어떤 수로도 나뉠 수 있기 때문이다. 0을 0으로 나누면 몫은 0 나머지도 0, 00으로 나눠도 몫은 0, 나머지는 0. 즉 몇이든 상관없이 0은 항상 나뉠 것이다. a의 최대약수는 a자기 자신이니, gcd(a, 0) = a가 된다.2 이번엔 한번 유클리드 호제법을 사용해서 아주 큰 두 수의 최대공약수를 계산해 보도록 하자. 452,302,94와 30,029,53의 최대공약수를 계산해보자.(나눗셈 계산은 계산기를 사용하였다.) = = = = = = = = = = = =

11 그러므로 gcd( , ) = gcd( , ) = gcd(224735, ) = gcd(559983, 8222) = gcd(8222, 3585) = gcd(3585, 577) = gcd(577, 954) = gcd(954, 29) = gcd(29, 5) = gcd(5, 27) = gcd(27, 24) = gcd(24, 3) = gcd(3, 0) = 3 물론 계산과정이 다소 번거로운 것은 사실이지만, 각각의 숫자를 일일이 소인수 분해 하는 것보다 훨씬 더 효과적이다. 제 2장: 소수편에서 소개된 에라토스테네스의 체를 사용하면 를 소인수분해 하는데에는 보다 작거나 같은 소수로 일일이 나누어주어야 하는데, 소수정리를 사용하면, 이보다 작거나 같은 소수의 개수는 약 234개나 있다. 이를 컴퓨터없이 계산하는 건 불가능이라도 봐도 무방하나, 반면에 유클리드의 호제법은 컴퓨터가 없어도 다소 시간은 걸릴지 몰라도 충분히 계산할 수 있는 수준이다. 유클리드의 호제법을 약간 변형시키면, 다음과 같은 정리를 얻을 수 있다. 정리 4.3. 임의의 자연수 a, b에 대해 k = gcd(a, b)라고 한다면, ax + by = k를 만족 시키는 정수 x, y가 존재한다. 이것이 어째서 호제법으로부터 당연히 유도되는 것일까? 계산하기 쉬운 예제를 통해 한번 살펴보도록 하자. 일단 호제법을 사용해서 5과 8의 최대공약수를 계산해 보자. 5 = = = 보다시피 5과 8의 최대공약수는 3이다. 그렇다면 이제 위의 정리를 이용해서 이 99

12 연산을 다시 표현해보자. 첫번째 연산인 5 = 를 다음과 같이 다시 써주자. 5 = 다소 당연한 말이지만, 5는 5x + 8y의 형식으로 써줄 수 있다. 여기서 x = 이며 y = 2이다. 이번엔 8 = 5 + 3을 다음과 같이 써보자. 3 = 8 5. 하지만 5 = 5 + ( 2) 8로 표현이 가능하니, 5를 해당 식으로 고쳐써보자. 3 = 8 + ( ) ( 5 + ( 2) 8) = 8 + ( ) = ( ) 즉 최대공약수 3은 5x+8y의 형식으로 써줄 수 있으며, 해당 정수는 x = 과 y = 3 이다. 마찬가지로, 앞서 호제법 알고리즘의 예로 사용했던 , 의 최 대공약수를 위의 식의 형태로 쓰면 다음과 같다. 3 = ( ) 그리고 이 경우 x = 이고, y = 이다. 임의의 자연수 a, b에 대해서 gcd(a, b) = k라고 두었을 때 ax + by = k를 만족하는 x, y가 존재한다. 여기서 다음과 같은 정리가 유도된다. 정리 4.4. 임의의 자연수 a, b에 대해서 ax + by는 항상 gcd(a, b)의 배수이다. 예컨데 0과 25의 예를 들면, gcd(0, 25)는 5이다. 그렇다면 임의의 정수 x, y에 대해서 0x + 25y는 항상 5의 배수일 수밖에 없다. 5의 배수가 아닌 수가 나올 수 없다. 예컨데 3의 배수가 나온다고 가정하면 다음과 같은 문제가 생긴다. 0i + 25j = 3을 만족시켜주는 정수해 i, j가 있을 것이고, i와 j를 두배씩 해주면 0(2i) + 25(2j) = 을 만족시켜주는 정수해 2i와 2j가 있다는 의미이다. 이를 각각 a, b라고 치환해보자. 그렇다면, 0x + 25y = 5를 만족하는 값 x, y와 0a + 25b = 을 만족하는 값 a, b가 00

13 있다는 의미가 된다. 이는 (0a+25b) (0x+25y) = 0(a x)+25(b y) = 5 = 을 만족시켜주는 정수 a x와 b y가 있다는 의미이니, 둘의 최대공약수는 5가 아니라 이 되어버리는 불상사가 생겨버린다.3 즉, 임의의 자연수 a, b에 대해서 gcd(a, b) = k라고 둔다면, ax + by는 항상 k의 배수여야 한다. 다시말해, ax + by가 가질 수 있는 최소 자연수 값이 바로 gcd(a, b)라는 의미이다. 이 아이디어를 조금 확장시키면 다음과 같은 정리를 유도할 수 있다. 정리 4.5. 임의의 자연수 a, b에 대해서 ax+by = c를 만족하는 x, y가 있다면, gcd(a, b) 는 c를 나눌 수 있다. 또한, gcd(a, b)가 c를 나눈다면, ax + by = c를 만족시키는 x, y 가 있다. 이 정리를 이용해 다시 원래의 문제로 돌아가보자. 언제 식 ax = b (mod n)을 만족하는 x값이 존재하냐 의 문제로 말이다. 일단 식 ax b (mod n)는 n (ax b)로 다시 쓸 수 있다. 다시말해, 임의의 정수 y 에 대하여 ax b = ny이며, 혹자는 ax + ny = b라고 표현이 가능하다. 눈에 좀 익숙한 식이지 않은가? 바로 방금 전 정리에서 본 식이다. 단, 이번 경우에는 b의 자리에 n이, n의 자리에 b가 있다는 차이가 있지만 말이다.4 ax + ny = b라는 식을 만족하는 정수 x, y가 존재하려면, b는 gcd(a, n)의 배수여야 한다. 만약에 b가 gcd(a, n)의 배수가 아니라면, 해당 식을 만족시키는 정수 x, y는 없을 것이고, 그러므로 ax b (mod n)을 만족시키는 정수 x또한 없을 것이다. 다소 자잘한 연산이 많아 생략하도록 하겠다만, 만약 b가 gcd(a, n)의 배수라면 ax b (mod n)을 만족시키는 x값의 개수는 gcd(a, n)과 같다. 한번 이것이 참인지 약간의 대수학장에서 다뤄진 예제들을 다시 살펴보자. 3x (mod 9)를 만족시키는 x의 개수는 3개이다. 3x 7 (mod 9)를 만족시키는 x는 없다. 2x (mod 4)를 만족시키는 x의 개수는 2개이다. 4x (mod 7)를 만족시키는 x의 개수는 개이다. 0

14 첫번째 예제는 gcd(3, 9) = 3이고 3 이니, 식을 만족시키는 x값이 존재하며, 그 개수는 3개이다. 두번째 예제에서는 3-7이니, 식을 만족시키는 x값은 있을 수 없 다. 세번째 예제에서는 gcd(2, 4) = 2이고, 2 이니, 식을 만족시키는 x값은 2개다. 마지막의 경우는 gcd(4, 7) = 이고 이니, 식을 만족시키는 x값은 개이다. 여기서 마지막 경우를 조금 더 집중해서 살펴보자. ax b (mod n)의 식에서 만약 gcd(a, n) = 이라면, b가 몇이든 상관없이 항상 b이다. 물론 b가 n보다 작아야겠 지만, 그렇다는 가정하에서는 해당 식을 만족시키는 x값이 무조건 하나씩 존재한다는 의미이다. 4.5 오일러 φ 함수 8세기의 가장 위대했던 수학자를 고르라면 누구를 댈 수 있을까? 필자는 개인적으 로 오일러라고 생각한다. 그는 말년에 시각을 잃었음에도 일평생 수학 뿐만 아니라 물리학, 천문학, 항해학등 여러 분야에 걸쳐 800편이 넘는 논문을 편찬해왔다. 오일러 혼자서 쓴 논문이 8세기에 출고된 논문의 25%를 이룬다는 사실만을 보더라도 그가 얼마나 위대했던 학자인지 알 수 있다.5 그가 수학에 끼친 영향이 어찌나 지대한지, 그의 이름을 딴 가설, 공식, 등식, 수, 함수, 정리, 법칙들만 나열해도 수십에 이른다. 물론 그 모두를 소개하는 건 필자 본인에게는 즐거운 일이겠지만, 독자들에게는 그 것만큼 끔찍한 고문도 없을 것이라 판단되기에, 그 중 단 하나인 오일러의 φ함수를 소개해볼까 한다. φ는 영어 알파벳 f에 해당하는 그리스어 알파벳으로, 피(phi)라고 부른다. 그래서 φ함수를 주로 오일러 피 함수라 부른다. 소수계량함수와 마찬가지로, 오일러 피 함수, φ의 정의역은 자연수 N에만 한정된다.7 오일러 피 함수의 정의는 다음과 같다. φ(n)은 n이하의 서로소의 개수를 말한다. 서로소란, gcd(a, b) = 을 만족시키는 두 수 a, b를 말한다. 예컨데, φ(0)은 0 이하 의 자연수 중 0과 서로소인, 다시말해 0과의 최대공약수가 인 자연수의 개수이며, 해당 조건을 만족하는 자연수는, 3, 7, 9, 이렇게 네개가 있다. 그러므로 φ(0) = 4 이다. 아래 표는 n이 20까지의 φ(n)값이다. 02

15 n φ(n) n φ(n) n φ(n) n φ(n) 표 4.4: n이 20 이하일 때의 φ(n)값들 표를 보니 소수계량함수 이상으로 값이 뒤죽박죽이다. 적어도 소수계량함수 π는 n 이 커지면 커질수록 π(n)역시 커진다는 성질이 있었는데, φ(n)는 어째 숫자가 커졌다 작아졌다 내 친구 보거스마냥 천방지축이다. φ(n)을 예측할 수 있는 방법은 정녕 없는 것일까? 한번 φ(n)가 가지고 있는 성질을 차근차근 살표보자. 일단 n이 2보다 크면, φ(n)이 항상 짝수다. 항상 그럴까? 항상 그렇다. 그 이유는 다음과 같다. 일단 n이 2보다 큰 자연수라고 가정해보자. φ(n)은 gcd(x, n) = 을 만 족하는 n이하의 자연수 x의 개수라고 하였다. 예컨데 g n에 대해서 gcd(g, n) = 이라고 가정해보자. 유클리드 호제법을 사용하면, 이는 gx + ny = 을 만족시키는 정수해 a, b가 존재한다는 의미이다. 위 식을 약간 고쳐보자. gx0 + ny0 = = g( x0 ) + ny0 = = g( x0 ) + n( x0 + y0 + x0 ) = = g( x0 ) + n( x0 ) + n(y0 + x0 ) = = (n g)( x0 ) + n(y0 + x0 ) =. 이것이 무엇을 의미하냐, gx + ny = 을 만족시키는 정수해 x0, y0 가 있다면 (n g)x + ny = 또한 만족시키는 정수해가 있다는 의미이다. 그 정수해는 x0 과 y0 + x0 이고 말이다. 어찌됬든 해당 값이 인 정수해가 있다는 의미이니 gcd(n g, n) = 이란 의미이다. 다시 말해 2보다 큰 자연수 n에 대해서, g와 n이 서로소라면 n g와 n또한 서로소 이다. n이 2보다 크다면, g와 n이 서로소일 때, g가 n g와 같은 값일 수가 없다.8 고로 g와 n g을 짝지어 셀 수 있고, 그러므로 n보다 작은 서로소의 개수는 2의 배수여야 한다. 즉, n 3이라면 φ(n)은 항상 짝수다. 03

16 이 증명이 n = 의 경우와 n = 2의 경우에는 통용하지 않는 이유는 다음과 같다. 일단 은 항상 다른 수와 서로소라는 사실을 주목해주길 바란다.9 g = 이라고 둘 때, n = 인 경우는 n g = 0이 되어버린다. φ(n)의 정의를 gcd(x, n) = 을 만족하는 n 이하의 자연수 x의 개수라고 하였다. 하지만 0은 자연수가 아니므로, 이 경우 g와 n g 를 짝지을 수 없다. n = 2인 경우는 g = n g이므로 g와 n g를 짝지을 수 없다.(이를 짝짓는다면 g = 를 두번 세어주는 셈이다.) 그러므로 n 2라면 해당 짝수법칙이 성립하지 않는다. 이번에는 n이 소수인 경우들을 살펴보자. n이 소수라면, k n을 만족시켜주는 k가 k = 이거나 k = n, 이렇게 두 경우밖에 없다고 했었다. 즉, n보다 작은 모든 자연수 g에 대해서 gcd(n, g) = 이다. n보다 작은 자연수의 개수는, 2,, n 로 총 n 이니, φ(n) = n 이 된다. 다시 위의 표를 살펴보면 φ(5) = 4, φ(7) =, φ() = 0 등을 확인할 수 있을 것이다. n이 2보다 크다면 φ(n)이 짝수라는 것과 n이 소수라면 φ(n) = n 이란 사실은 잘 알았다. 하지만, 여전히 합성수 n에 대해서 φ(n)은 예측하기 어렵다. 예측하기 어 려운게 당연하다. n의 소수인 약수, 이른바 소인수를 p, p2,, pk 라고 할 때, φ(n)은 다음과 같기 때문이다. k Y =n φ(n) = n p p2 pk pi i= 잠시만, φ(n)은 n이하의 n과 서로소인 숫자들의 개수라 하였다. 하지만 φ(n)을 구하는 공식에 분수의 곱셈이 나온다. 위의 공식대로 계산했는데 서로소의 개수 를 구하는 과정에서 분수값이 나오는 불상사가 있지는 않을까? 좋은 걱정이다. 하지만, 너무 걱 정할 필요는 없다. 왜냐하면 저 곱셈의 분모에 있는 숫자들은 모두 n의 소인수로, n을 나눠줄 수 있는 수들이다. 그러므로 저 값이 분수가 나오는 일은 결단코 없다.20 위의 식을 이용해서 φ(00)을 계산해본다고 가정해보자. 00을 나눠주는 소인수는 2와 5가 있기 때문에 φ(00) = = = 40이다.2 물론 해당 식의 증명을 선보일 수 있다면 좋겠다만, 아쉽게도 그 증명을 위해서는 다른 두 가지 정리와 증명을 선보여야 한다. 허나, 정수론편의 메인 디쉬는 φ(n)의 식을 증명하는 것이 아니기 때문에, 해당 증명은 과감히 생략하도록 하겠다.(증명과정을 정 원한다면 각주를 참고하길 바란다.)22 04

17 그럼 이 메인디쉬 가 아닌 φ(n)함수로 무엇을 할 것이냐? 바로 우리의 첫번째 메인 코스인 페르마의 소정리와 오일러의 정리를 선보일 것이다 4. 페르마의 소정리와 오일러의 정리 수학자 페르마는 자신의 정리를 증명하지 않은 채 내놓는, 이른 바 매너없는 수학자 였다. 대표적인 예를 들라면 페르마의 소정리, 페르마 수의 소수성, 페르마의 마지막 정리가 있다. 페르마의 마지막 정리는 유명한 일화로 아마 수학과 출신이 아닌 학생들도 종종 들 어봤을 것이다. 페르마가 디오판토스의 산술이라는 책 한 귀퉁이에 어떤 정리를 적고, 그 아래 다음과 같은 글을 남겼다는 이야기다. (상략)...나는 이것을 경이로운 방법으로 증명하였으나, 책의 여백이 충분 하지 않아 옮기지는 않는다. - 피에르 드 페르마(Pierre de Fermat) 원래대로라면 수학에서는 증명되지 않은 것들은 모두 가설이나 추측이라 명명해야 되는데, 어째선지 수학자들은 이를 마지막 정리 라고 명명했다.23 이 마지막 이라 는 드라마틱한 작명 센스 덕에 해당 난제는 수학계 뿐만 아니라 일반인들에게도 다소 귀에 익숙한 이야기가 되었다. n 페르마 수의 소수성 정리에서 페르마는 또 증명없이 n이 자연수일 때, 22 + 의 꼴의 숫자들은 모두 소수라고 주장했었다. 우습게도 그의 주장은 n = 5인 경우에서 부터 무너지며, 이는 페르마가 n = 4까지의 경우만 살펴보고 소수라고 주장했었다는 n 것을 의미한다. 더 나아가, n 5인 모든 자연수에 대해서 22 + 은 항상 소수가 아니다라는 것이 증명되었다.24 페르마의 소정리 역시 아무런 증명 없이 주장되어졌다. 해당 정리는 다음과 같다. 정리 4.. 페르마의 소정리: p가 소수고 a와 p가 서로소라면, ap (mod p)이다. 과연 그럴까? 한번 예제를 통해서 맞는지 살펴보자. 일단 소수 p와 p와 서로소인 자연수 a를 골라야 한다. 소수로 은 어떨까? 그리고 a는 p와 서로소여야 한다는 조 건이 있다. 하지만, p가 소수라면 p를 나누는 수는 항상 과 p이다. 즉, gcd(a, p)는 이거나 p가 될 수 있는데, p가 될 경우는 p a를 만족해야한다. 다시말해, p - a면, 혹은 05

18 a가 p의 배수가 아니라면, a는 p와 항상 서로소라는 것이다. p를 로 골랐으니 a는 의 배수만 아니면 된다. a를 에서 0까지두어 각각의 값을 확인해보도록 하자. a a0 a0 (mod ) 2, ,049 4,048,57 5 9,75,25 0,4, ,475,249 8,073,74, ,48,784,40 0 0,000,000,000 보다시피 a가 의 배수가 아닌 수라면 a0 (mod )이 항상 이라는 값이 나온다.25 어째서 그럴까? 증명을 남기지 않은 페르마는 그 이유를 알 도리가 없었다. 이 법칙이 왜 소수인 p에만 해당하는지도 말이다. 이 법칙이 소정리 라고 불리는 이유는 오일러가 증명해보인 정리의 전초전 격이 기 때문이다. 오일러는 p가 소수가 아니라 합성수여도, 위와 같은 성질이 항상 성립할 수 있음을 보였다. 오일러의 정리는 다음과 같다. 정리 4.7. 오일러의 정리: gcd(a, n) = 이라면 aφ(n) (mod n)이다. 일단 이 법칙이 페르마의 소정리의 확장인 이유를 설명해보겠다. 일단 둘의 기본 조건은 같다. 페르마의 소정리에서는 a와 p가, 오일러의 정리에서는 a와 n이 서로소 여야한다는 조건 말이다. 해당 조건하에, 오일러의 정리에서 n이 소수라고 가정하고 φ(n)을 구해보자. φ(n)은 n이하의 자연수 중 n과 서로소인 숫자의 개수였다. 만약 n 이 소수라면, n을 나누는 수는 과 n 자기자신밖에 없다. 그러므로 n보다 작은 모든 자연수 x에 대해서 gcd(n, x) = 이다. 그러므로, φ(n) = n 이다. 즉, n이 소수인 경우에서는 aφ(n) = an (mod n)으로 페르마의 소정리와 정확히 일치한다. 오일러의 정리가 더 훌륭한 정리인 이유는 n이 합성수인 경우에도 해당 법칙이 성 립한다는 것을 보였다. 물론 n이 합성수라면 φ(n)은 n 이 아니다. 그 점을 유의하며 예제를 하나 살펴보도록 해보자. 0

19 일단 n이 합성수여도 된다는 조건이 있으니 a를 고르는 과정에서 신중해야 한다. n이 소수인 경우는 a가 단순히 n의 배수만 아니면 되었지만, 이번엔 n이 합성수이니, 혹여나 a와 n이 약수를 공유하는 불상사가 없나 조심해야 한다. a를 4로, n을 5로 둬보는 건 어떨까? gcd(4, 5) = 이니 일단 기본조건엔 부합한 숫자들이다. 다음으로 해야할 것은 φ(5)의 값을 구하는 것이다. 물론 숫자가 작으니 일일이 서 로스의 개수를 세보는 것도 좋은 방법이지만, 기왕에 φ(n)을 구하는 공식도 배웠겠다, 공식을 사용해서 그 값을 구해보도록 해보자. 일단 5의 소인수를 모두 나열해보면, 5는 3과 5로 나뉜다. 그러므로 φ(5)를 구하는 공식은 다음과 같다. 2 4 = 5 = 8. φ(5) = 원래의 식으로 돌아와보자. 4φ(5) = 48 = 553이다. 553을 5로 나눠주면, 나 머지가 이다. (553 = ) 그러므로, 4φ(5) (mod 5)이 성립한다. 이런 현상이 도대체 왜 일어나는 걸까? 막연히 정수론 테크닉만을 고집해서 증명 하기는 어려운 문제다. 오일러는 해당 증명을 정수론이 아닌 전혀 다른 분야를 사용해 증명했다. 이 증명이 얼마나 우아하고 아름다운지, 필자도 처음으로 그 증명을 정수론 수업에서 접했을 때 캬! 하고 감탄이 절로 나왔다.2 기왕에 이렇게 된 것, 여기서 또 하나 이 책의 비밀을 밝혀야겠다. 왜 소수와 정수론이 이렇게 밀접한 관련이 있는데 그 사이에 구태여 제 3장: 군론편을 끼워 넣었는지 말이다. 바로 이 정리를 선보이기 위해서 군론을 소개해준 것이다. 오일러가 사용한 방법은 다름아닌 군론이었다. Proof. 곱셈 군 (Z/0Z) 를 기억하는가? 해당 군은 0과 서로소인 0보다 작은 자연 수만을 포함하는, 곱셈의 연산을 가진 군이었다. 해당 군의 원소로는, 3, 7, 그리고 9 가 있었다. 임의의 자연수 n에 대해서 (Z/nZ) 곱셈군은 n과 서로소인 n보다 작은 자연수를 포함한다. 즉, 이 군의 크기는 φ(n)이다. 그리고 앞서 gcd(a, n) = 이라 정의하였으니, a역시 이 군에 포함되어 있을 것이다. 이제 군 (Z/nZ) 의 원소를 x, x2,, xφ(n) 이라고 둬보자. 이 값들을 모두 곱하면 몇이 나올지는 모르지만 어쨌든 (Z/nZ) 의 원소일 것이다.27 이번엔 함수 f : (Z/nZ) (Z/nZ) 를 정의해보자. f (x) = ax라는 함수이다. f (x ) = ax 이고, f (x2 ) = ax2 이다. 이 함수는 단사이다. 왜냐하면 f (x) f (y) (mod n)이라고 가정하면 ax ay (mod n)이다. 즉, n a(x y)인데, gcd(a, n) = 07

20 이라 하였으니, n (x y)여야 한다. 즉 x y (mod n)이며, 이는 이 함수가 단사라는 것을 의미한다.28 또한 이 함수는 전사이다. (Z/nZ) 에 있는 임의의 원소 y에 대해서 f (x) y (mod n)을 만족시켜주는 x값이 항상 존재하기 때문이다. f (x) = ax y (mod n)을 만족시켜주는 x가 존재하는 이유는 gcd(a, n) = 이기 때문에, y가 몇이든 간에 항상 해당 식을 만족하는 x가 한 개 있다는 것을 의미한다.(유클리드 호제법 장을 참조하라.) 즉 f (x) = ax는 (Z/nZ) 의 원소들을 (Z/nZ) 의 다른 원소들로 보내주는 훌륭한 전단사 함수이다. 이제 axi 를 x0i 라고 다시 표현해보자. 그렇다면 ax, ax2,, axφ(n) 은 x0, x02,, x0φ (n)으로 표현이 가능하며 이 모든 원소들은 (Z/nZ) 군을 이룬다. 다시말 해 x0, x02,, x0φ (n)을 곱하면 x, x2,, xφ(n) 을 곱한 값과 같다.(둘은 단순히 곱하는 순서를 바꿔준 것에 불과하다.) 즉 다음과 같은 식이 성립한다. x x2 xφ(n) x0 x02 x0φ (n) (mod n) ax ax2 axφ(n) aφ(n) x x2 xφ(n) (mod n) (mod n) 이제 x x2 xφ(n) 를 k로, aφ(n) 을 y로 치환하자. k는 (Z/nZ) 의 원소이니 n과 서로소 이다. 그렇다면 다음과 같은 식이 유도된다. ky k (mod n). gcd(k, n) = 이니 해당 방정식을 만족하는 y값은 오로지 하나이며, 그 값은 y (mod n)이다. 그러므로 aφ(n) (mod n)이다. 4.7 닫는 글 수는 실존하지 않는다. 그것은, 추상적 아이디어에 불과하다. 하지만, 그만큼 친숙하고 익숙한 추상적 개념이 또 있을까. 그 개념이 헤아림에서 시작되어 이제는 문명 사회를 떠받치는 거대한 기둥이 되었으니, 흥미롭지 않을 수 없다. 08

21 그 뿐만이 아니다. 수의 유용함 이라는 특성은 수가 가진 수많은 특성들 중 단 하나에 불과하다. 예컨데 그 특성들 중 가장 중요한 것을 골라보라 한다면, 필자는 망설임없이 신비로움 을 고를 것이다. 수는 단순히 유용한 개념에 그치는 것이 아니 다. 이제는 수라는 것이 우리에게 익숙해질 대로 익숙해졌지만, 여전히 우리는 수에 대해서 모르는 것이 많음을 인정해야만 한다. 09

22 Notes to chapter 4. 여기서 어디에나 라는 표현을 조금 더 정확히 서술하면 유리수집합은 조밀집합 이라는 의미이다. 이에 대한 설명으로는 약간의 집합론이 필요하지만, 집합론을 피해 설명해보자면, 아무리 작은 구간 (a, b)에도 무한히 많은 유리수가 포함되어있다는 의 미이다. 예컨데 0.4보다 크고 0.보다 작은 유리수는 무수히 많지만, 그 안에 포함된 정수는 하나도 없다. 2. 다시한번 강조하지만, 정수 i, j이다. 0이어도 되며, 음수여도 된다 = 8 ( 4) + ( )이니 나머지가 이지 않느냐고 주장할 수도 있다. 하지만 2 (mod 8)이니, 사실상 답으로는 동일하다. 왜 2 (mod 8)이냐, 두 수의 차이는 8이며 이는 8로 나뉘는 숫자이기 때문이다. 4. 나눗셈이 늘 말썽이다. 0으로 나누는 것도 그러했고 지금 이 경우도 말이다. 5. mod n의 모듈로 연산은 모든 값을 0보다 크거나 같고 n보다 작은 자연수로 환원 시킨다는 의미이다. 해당 식에 있는 모든 값들은 제 3장: 군론편에 소개되었던 Z/nZ 군에 있는 원소로 환원이 가능하다.. 앞서 말했듯, 모듈로 연산에서는 나눗셈이 금지되어 있기에 양 변에 3을 나누면 x 2 (mod 9)에요 라는 논리를 들 수는 없다. 단순히 대입했는데 명백하게 답이니 x = 2다라는 무책임한 설명밖에 들 수 없겠다. 7. 각각의 수를 소인수분해 해본 결과 4,502,42은 였고, 24,00,592는 이었다. 즉 둘의 최대공약수는 이다. 8. 증명을 해보고 싶다면 k n을 n = kj의 꼴로 바꿔준 뒤 연산을 진행해보면 쉽게 알 수 있다. 9. 두 집합 A와 B가 동일하다는 의미는 A의 모든 원소가 B에 있고, B의 모든 원소가 A에 있다는 의미이다. 그러므로 A의 가장 큰 원소는 B의 가장 큰 원소와 같을 것이다. 0. A이며 B면 C다. 라는 문장이 참이라고 가정해보자. 조건절 B를 결과절에 가지고 온 A이며 B면 B이며 C이다. 라는 문장 역시 참이 된다. 예컨데, 사람이며 남자인 생물은 죽는다. 라는 문장은 참이다. 즉, 사람이며 남자인 생물은 남자이며 죽는다. 라는 문장 역시 논리학적으로는 참인 문장이다.. 애초에 a, b가 둘 다 0이 아닌 이상, 둘 다 0이 되는 경우는 절대 있을 수 없다. 계속 해서 알고리즘을 진행하다보면 한쪽만 0이 되는 경우가 무조건적으로 있을 것이다. 2. 물론 a보다 더 큰 수 b또한 0을 나눠주지만 a를 나눠주진 못하니 공약수가 아니다. 0

23 3. ax+by가 이 나오면 gcd(a, b)가 이냐의 대한 답은, 간략히 서술하면 다음과 같다. ax+by가 가질 수 있는 최소 자연수 값 이 gcd(a, b)값이기 때문이다. 만약 ax+by = 이라면, 보다 더 작은 자연수는 존재하기 않기 때문에 자연스레 gcd(a, b) = 이 된다. 위의 경우 gcd(0, 25) = 5라고 하였으니, 0x + 25y가 가질 수 있는 최소 자연수값은 5이다. 4. 만약 이렇게 알파벳이 바뀌는 경우가 싫다면, 임의로 n과 b를 바꿔 써주어도 괜 찮다. 단, 이 경우 ax b (mod n)이 아니라, ax n (mod b)로 써주어야 겠지만 말이다 위키피디아 한 페이지가 그의 이름을 딴 것들의 리스트이다. 해당 페이지의 url은 다 음과 같다: Euler 7. 이러한 함수들을 수론적 함수 라고 부른다. 8. g = n g라고 가정하면, n = 2g가 된다. 그러므로 g n이며, 이는 gcd(g, n) = g 를 유도한다. 즉, n이 2보다 크다면, g와 n g는 항상 별개의 두 숫자이다. 9. 그 이유는 을 나눌 수 있는 최대약수는 이다. 그러므로, gcd(, n)은 최대 일 수 밖에 없다. 이 아니라면 그 숫자는 을 나눌 수 없으니 과 n의 공약수가 될 수 없는 처지이다. 20. 만약 분수가 나왔다면 p,, pk 중 n의 소인수가 아닌 숫자가 있다는 의미이다. 2. 의심많은 독자들을 위해 00과 서로소인 00보다 작은 수를 나열해보면 다음과 같다:, 3, 7, 9,, 3, 7, 9, 9, 93, 97, 99. 0의 자리가 한번씩 바뀔 때 마다 4개의 서로소가 존재하니 총 40개가 맞다. 22. 각주를 참고하는 당신과 같은 열정적인 독자에게 찬사를 보낸다. 해당 증명을 보 이기 위해 필요한 두 가지 정리는 첫번째로, a와 b가 서로소라면 φ(ab) = φ(a)φ(b)라는 곱셈법칙이고, 두번째는 소수 p와 자연수 k에 대해서 φ(pk ) = pk pk 라는 법칙이다. 첫번째 법칙은 제 2장에 소개되었던 곱셈군 (Z/abZ) 과 곱셈군의 직접곱인 (Z/aZ) (Z/bZ) 를 연결하는 전단사함수를 보임으로서 (Z/abZ) = (Z/aZ) (Z/bZ) 를 보여주는 것이다. 임의의 n에 대해서 (Z/nZ) = φ(n)이기 때문에, 위의 관계식은 φ(ab) = φ(a)φ(b)를 유도한다. 두번째는 pk 보다 작지만 pk 와 서로소인 숫자들은 모두 p의 배수라는 점을 착안한 정리이다. pk 와 서로소가 아닌 숫자들은 p, 2p, 3p,, pk 로 총 pk 개이니, pk 와 서로소인 숫자들은 pk pk 개가 되는 것이다. pk pk 을

24 pk ( p )로 표현이 가능하단 사실을 주목한 채, 원래의 정리의 증명으로 돌아와보자. n을 소인수분해 해준 형식을 pe pe22 pekk 라고 한다면, φ(n) = φ(pe )φ(pe22 ) φ(pekk ) 이며, 이 값은 pe pe22 pekk ( p )( p2 ) ( pk )이다. pe pe22 pekk = n이라 하였으니, 원래의 식이 자동으로 유도된다. 23. 필자 본인의 생각으로는 아마 순진한 수학자들이 페르마가 진짜로 증명했다고 생각했기에 정리라고 이름 붙인 모양이다. 24. Ribenboim, P. Fermat Numbers and Numbers k 2n ±. 2. and 5.7 in The New Book of Prime Number Records. New York: Springer-Verlag, pp and , 저 값들이 진짜 일까? 의심이 드는 독자들을 위해서 어떤 숫자가 로 나뉘는 지 안나뉘는지 쉽게 알아낼 수 있는 법칙 하나를 이 자리에서 공개해보겠다. 어떤 수 abcde가 로 나뉘는지 판별하는 방법은 a b + c d + e가 의 배수인지 확인해보는 것이다.(0 역시 의 배수라고 생각한다.) 만약 의 배수라면 해당 수는 로 나뉘는 것이고, 의 배수가 아니라면 해당 수는 로 나뉘지 않는다. 이제 이 사실을 가지고 50 이 진짜로 50 (mod )인지 확인해보겠다. 이는, (50 )인지 확인해 주겠다는 의미와 같다. 50 = 97524인데, 각 자리 수를 교차로 더했다 빼주면 = 인데, 은 의 배수이니, (50 )이다. 즉, 50 (mod )이다. 시간이 많은 독자분들은 다른 값들도 모드 일 때 과 같은지 한번 확인해보기를 권유해본다. 2. 이후 친구들의 증언으로는 필자가 수업도중에 맥주를 마시는 줄 알았다고 한다. 27. 군은 연산에 닫혀있다. 라는 연산자를 가지고 있는 군이 있다고 가정하자. a, b가 그 군의 임의의 원소라면 a b역시 그 군에 포함된 원소여야 한다. 28. 원래의 단사를 보여주는 조건은 f (x) = f (y)면, x = y이다 를 보여주는 것이지 만, 이 연산은 모듈로 연산이니 f (x) f (y) (mod n) 이면 x y (mod n)이다를 보여주면 된다. 2