반응형 정수론(Number Theory)/나눗셈 이론6 유클리드 호제법, 유클리드 알고리즘(Euclid algorithms) 유클리드 호제법은 지금 고교 교육과정에 포함되어 있지 않지만 알고 있을 때 복잡한 문제를 해결하는데 약간의 도움이 되는 경우도 있습니다. 유클리드 호제법은 고대 그리스 수학자 유클리드(Euclid)가 만든 것이며, 그의 책에서 두 정수의 최대공약수를 찾는 알고리즘 중 하나입니다. 최대공약수를 찾을 때 두 수의 크기가 매우 커지게 되는 경우에는 더 이상 직관적으로 또는 암산으로 최대공약수를 찾기가 어려워지기 때문에, 나눗셈 알고리즘을 통해 수를 충분히 줄이면서 유클리드 호제법을 사용하면 답을 구할 수 있게 됩니다. 1. 유클리드 호제법과 보조정리 유클리드 호제법을 증명하기 위해 유클리드 보조정리를 보이고 가는 것이 좋습니다. 사실 내용은 별 거 없고 지극히 당연한 내용입니다. 정리($N.T$) 1.8 $a.. 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. 나눗셈 정리(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 다음 반응형
