반응형 정수론(Number Theory)12 정수론의 합동에서 동치류들의 연산 여태까지 합동에 관한 뼈대가 되는 개념들을 모두 다루었습니다. 이번 글부터는 본격적으로 대수학을 하기 위해 $\mathbb{Z}_n$ 과 $\mathbb{Z}_n^*$ 을 다루는 과정에서 필요한 동치류들의 연산에 대해 정리할 것입니다. 이미 배웠던 내용, 특히 합동의 연산 성질을 바탕으로 약간만 확장하는 것이기 때문에 그리 어렵지 않을 것입니다. 그러나 결론적으로 보면, 합동식 $ax\equiv b \;(\text{mod}\; n)$ 와 같은 식에서 사실 해는 무수히 많아 동치류들로 적는다는 점을 고려할 때, $\mathbb{Z}$ 를 $\mathbb{Z}_n$ 으로 줄여서 생각하더라도 그러한 합동의 개념 본질이 달라지는 것은 아니기 때문에 사실 합동의 연산 관계들은 자연스럽게 동치류에서도 성립할 것임.. 2024. 6. 29. 합동방정식(congruence equation) 이번 주제는 정수론에서 합동에 대한 개념을 바탕으로 합동방정식의 해를 찾는 일입니다. 이 작업은 일차적으로 정수론에서 1차 선형 디오판토스 방정식에 대해 알고 있어야만 이해할 수 있습니다. 하지만 합동방정식을 조금 더 풍부하게 이해하기 위해서는 선형대수학의 방정식 논리를 알고 있는 것이 좋기는 합니다. 일반적인 연립방정식과 다른 점은 합동방정식이 미분방정식에서처럼 해의 개수가 단 하나로 떨어지지 않는다는 점입니다. 이는 동치류가 품고 있는 무수히 많은 원소들이 모두 해가 될 수 있다는 사실에 기반하고 있습니다. 또한 해의 꼴을 보면, 디오판토스 방정식처럼 합동방정식은 선형대수학에서 연립방정식의 해의 논리와 유사한 점이 많습니다. 방정식은 근본적으로 대수적인 관점이 녹아 들어있기 때문입니다. 만일 선.. 2024. 6. 27. 1차 선형 디오판토스 방정식(Linear first-order Diophantine equation) 디오판토스는 고대 그리스의 수학자로, 이집트 알렉산드리아 출신이며 정수론과 방정식을 연구하였다고 알려져 있습니다. 그의 이름을 따 만들어진 디오판토스 방정식은 정수론을 공부하면 꼭 한 번쯤은 들어봤을 것입니다. 디오판토스 방정식은 정수해만을 다루며, 해법이 아주 어렵지 않아 사실 중고등학교 수학 정도만으로도 해를 찾는 것이 가능합니다. 그리고 여러 매체에서 그것의 응용을 재미난 수수께끼로 둔갑시켜 사용되고는 합니다. 라라 크로프트를 주인공으로 하는 시리즈는 제가 매우 좋아하는 게임 중 하나입니다. 제가 어렸을 시절 툼레이더 클래식(1,2,3,4,5(연대기)) 를 즐겨 했었던 기억이 있는데, 당시 너무 어려워서 끝까지 깨지 못했습니다. 툼레이더 시리즈는 고도의 컨트롤 피지컬과 경로 기억성, 귀류법적 사.. 2024. 6. 25. 합동의 연산성질(Operations on congruence in the Number Theory) 합동의 대한 기초 개념을 학습하고 나서는 합동 관계에서 덧셈, 뺄셈, 곱셈, 나눗셈을 하는 방법을 익혀야 합니다. 이 개념은 정수론뿐만 아니라 대수학의 군론을 시작할 때 반드시 필요하므로 이번 글의 중요성을 또 한번 강조해도 지나치지 않습니다. 1. 합동의 기본 연산 1) 덧셈과 곱셈의 기본 연산 정리($N.T$) 3.6) 두 합동식은 연결해서 양변 각각 덧셈과 곱셈이 가능$a\equiv b\;(\text{mod}\; n)$ 이고 $c\equiv d\;(\text{mod}\; n)$ 이라고 하자. 그러면 다음이 성립한다.① $a+c=b+d\;(\text{mod}\; n)$② $ac=bd\;(\text{mod}\; n)$따름정리($N.T$) 3.6.1)$a\equiv b\;(\text{mod}\; n)$ .. 2024. 6. 24. 정수론에서의 법 $n$ 에 대한 잉여류(residue class in the Number theory) 잉여류는 대수학의 시작, 즉 군론에 입문할 때 반드시 알아야 하는 정수론의 개념입니다. 저는 정수론의 기초를 잘 모른 채 대수학 공부를 시작했었는데, 그 때문에 정말 골머리를 앓았던 기억이 생생합니다. 그런데 군론을 공부하고 나서 정수론의 개념 중 단 한가지만 제가 제대로 알고 넘어갔다면, 하는 후회가 남는 것이 바로 합동과 이 잉여류의 개념입니다. 달리 말하자면 여러분이 만일 정수론에 대한 빠삭한 학습 없이 대수학을 공부해야 한다면 합동과 잉여류에 대한 개념은 반드시 알아야 한다는 것입니다. 왜냐하면 군론을 다룰 때는 순환군과 더불어 $\mathbb{Z}_n$ 을 알아야 하고, 이것이 나중에 몫 군 $\mathbb{Z} / n\mathbb{Z}$ 과 동형(isomorphic)이라는 것을 보이게 되는데 .. 2024. 1. 29. 유클리드 호제법, 유클리드 알고리즘(Euclid algorithms) 유클리드 호제법은 지금 고교 교육과정에 포함되어 있지 않지만 알고 있을 때 복잡한 문제를 해결하는데 약간의 도움이 되는 경우도 있습니다. 유클리드 호제법은 고대 그리스 수학자 유클리드(Euclid)가 만든 것이며, 그의 책에서 두 정수의 최대공약수를 찾는 알고리즘 중 하나입니다. 최대공약수를 찾을 때 두 수의 크기가 매우 커지게 되는 경우에는 더 이상 직관적으로 또는 암산으로 최대공약수를 찾기가 어려워지기 때문에, 나눗셈 알고리즘을 통해 수를 충분히 줄이면서 유클리드 호제법을 사용하면 답을 구할 수 있게 됩니다.1. 유클리드 호제법과 보조정리 유클리드 호제법을 증명하기 위해 유클리드 보조정리를 보이고 가는 것이 좋습니다. 사실 내용은 별 거 없고 지극히 당연한 내용입니다. 보조정리($N.T$) 1.1) .. 2024. 1. 19. 정수에서 서로소의 의미(relatively prime in the Number theory) '서로소'라는 말은 수학에서 크게 보았을 때 집합 관계 또는 정수론에서 사용하는 용어입니다. 이들은 각각 교집합을 가지지 않는 관계 혹은 최대공약수가 1임을 의미하는 말에 해당하는데, 한국어에서는 모두 '서로소'라고 표현하나 영어 표현은 살짝 다릅니다. 집합에서의 서로소 개념은 'mutally disjoint' 에 가깝고, 정수론에서의 서로소 즉 최대공약수가 1인 고나계는 'relatively prime' 이라고 표현합니다. 여기서는 후자의 개념에 대한 소개입니다. 1. 서로소 정의($N.T$) 1-7) 정수론에서 서로소적어도 둘 중 하나의 정수가 0이 아닌 $a,b\in\mathbb{Z}$ 에 대하여, $\gcd (a,b)=1$ 을 만족하면 두 수는 '서로소(relatively prime)'이라고 한다.. 2024. 1. 18. 베주 항등식(Bezout's identity) 베주 항등식은 나눗셈 정리와 최대공약수 개념을 활용하여 증명할 수 있고, 추후 유클리드 호제법을 증명하기 위한 도구적 역할을 합니다. 정리($N.T$) 1.5) 베주 항등식$a,b \in\mathbb{Z}-\{ 0 \}$ 일 때,$$ax+by=\gcd(a,b)=g$$ 를 만족하는 어떤 두 정수 $x,y\in\mathbb{Z}$ 가 항상 존재한다. 즉, 임의의 영이 아닌 두 정수의 최대공약수는 그 두 정수의 어떤 선형결합 표현으로 반드시 나타낼 수 있다.증명) $X=\left\{ax+by\mid x,y\in\mathbb{Z}\;,\; ax+by \geq 1 \right\}$ 라 하자. 여기서 $ax+by \geq 1$ 이라는 것은 곧 $ax+by$ 가 $0$ 보다 큰 정수라는 뜻이다. 그러면 $x=a$.. 2024. 1. 18. 정수론에서 합동(Congruence) 정수론에서 합동 개념은 수학적으로 매우 중요할 뿐더러 일상 생활의 여러 문제에 대입하여 활용될 수 있습니다. 아주 큰 수의 마지막 자리수를 찾는다거나, 아주 큰 수가 적당히 작은 수로 나누어 떨어지는지 등의 문제, 또는 과거 몇 년 몇 월 며칠이 어떤 요일이었는지를 알아내는데도 사용될 수 있습니다. 이는, 결국 숫자의 비슷한 구조가 계속 '반복'된다는 점을 합동 개념을 통해 하나로 묶어 생각하는 것이기 때문입니다. 합동관계는 동치관계의 한 예시로 집합론에서 등장했던 적이 있고, 이후 추상대수학을 공부할 때 매우 매우 많이 등장합니다. 부득이하게 정수론을 제대로 학습하지 못했다고 하더라도, 대수학을 공부하기 위해서 정수론의 합동 개념은 반드시 필요한 도구입니다. 숫자가 가진 어떠한 성질이 계속 반복된다.. 2024. 1. 10. 나눗셈 정리(Division theorem) 중고교 수학에서 젯수와 피젯수를 몫과 나머지에 관한 식으로 정리한 적이 있습니다. 이제 그 정리가 왜 성립하고, 유일하게 존재하는지를 증명하여 확실히 옳음을 확인해 보겠습니다. 1. 나눗셈 정리 정리($N.T$) 1.4 [나눗셈 정리(Division Theorem)] 임의의 두 정수 $a,b\;(b\ge 1)$ 이 주어졌을 때, 다음의 등식을 만족하는 유일한 정수 $q$ 와 $r$ 이 존재한다. 이들을 각각 '몫(quotient)'과 '나머지(remainder)'이라 부른다. $$a=bq+r\;\;\;\;\; (0\leq r < b)$$ 이 관계를 나눗셈 과정으로 생각하면, $a$ 는 나누어지는 수이니 '피젯수'이고, $b$ 는 나누는 수이니 '젯수'라 한다. 증명) 존재성과 유일성을 각각 순서대로 증명.. 2023. 2. 17. 최대공약수(Greatest common divisor) 약수와 배수, 나눗셈, 나누어 떨어짐에 대해 학습하였다면 최대공약수를 다루지 않을 수가 없습니다. 정수론에서 최대공약수 개념은 무진장 중요하고 빈번히 등장합니다. 1. 최대공약수 1) 공약수 정의($N.T$) 1.4) 공약수 $d\in\mathbb{Z}$ 가 두 정수 $m,n$ 의 '공약수(common divisor)'라는 것은 $d\mid m$ 이고 $d\mid n$ 인 것이다. 공약수의 개념은 별로 새롭거나 어려울 것이 없습니다. 2) 최대공약수 정의($N.T$) 1.5) 최대공약수 자연수 $g$ 가 0이 아닌 두 정수 $a,b$ 의 '최대공약수(greatest common divisor)'라는 것은 다음 세 조건과 필요충분조건이다. ① $g\geq 1$ ② $g\mid a$ 이고 $g\mid b$ .. 2023. 2. 5. 나눗셈과 나누어 떨어짐(Divisibility) 정수론은 영어로 직역하면 '수 이론(Number Theory)'에 해당합니다. 숫자를 연구하는 분야라는 것인데 음수의 경우 양수에 단지 부호만을 바꾸어 준 것에 해당하고, 양수에서 가장 가지런한 숫자들을 모은 것이 자연수에 해당합니다. 그런데 자연수들은 모두 소수와 합성수로 나눌 수 있지요. 그래서 정수론은 사실상 정수 집합을 들여다보되, 구체적으로 들어가면 정수 전체에 대해 골고루 관심을 가지고 있다기보다는 소수와 그들의 연산에 주목하고 있는 분야라고 보면 좋습니다. 정수론에 포함되는 수학 개념들은 중학교 수준에서부터 상당히 많이 등장하며 소수에 관련된 것은 무엇이든 거의 다 정수론의 분야라고 볼 수가 있습니다. 친숙한 개념들을 조금 더 정교하게 다듬어가는 과정들이 등장할 것이기에, 정수론의 기본적 개.. 2023. 2. 5. 이전 1 다음 반응형
