Mathmatics/Number Theory11 에라스토 테네스 체 [Sieve of Eratosthenes] 및 증명 이해하기 오늘은 특정 자연수 이하의 소수를 찾는 알고리즘인 에라스토테네스의 체, 그리고 여기에 활용되는 소수 관련 수학적 정의를 증명하는 시간을 가져 보겠습니다. 에라스토테네스의 체 [Sieve of Eratosthenes] 에라스토테네스의 체란 기계의 도움 없이 순수 손 계산을 사용하여 특정 자연수 이하의 소수를 구하는 유일한 알고리즘입니다. 에라스토테네스의 체를 설명하기 전에 다음 수학적 정의를 설명하겠습니다. n이 합성수라면 p | n, p 2022. 4. 21. Bezout's Identity(베주 항등식) 증명 완벽 이해 오늘은 Bezout's Identity의 증명을 완벽하게 이해 하는 시간을 가져 보겠습니다. 베주의 항등식이란? 베주의 항등식의 내용은 다음과 같습니다. 저번에 방정식의 정수해만을 고려하는 부정 방정식의 해법인 1차 Diopantine Equation에 관하여 포스팅을 한 바 있습니다. 해당 방정식의 정수쌍 (x,y)의 해가 존재할 필요충분조건에 관한 증명을 할 때 Bezout's Identity가 사용이 되었습니다. ax + by = gcd(a,b) 라는 형태의 방정식이 있을 때, 이를 만족시키는 정수쌍 x,y가 반드시 존재한다는 정리입니다. 증명을 해보도록 하겠습니다. 베주의 항등식 증명 "위 식을 만족시키는 정수쌍 x와 y가 존재한다"와 같은 어떤 대상에 대한 존재성을 증명하고자 할 때에는 집합을 .. 2022. 4. 21. 조화수(Harmonic Number)는 자연수가 될 수 없음을 증명하기 조화수란 무엇인가? 조화수가 대체 무엇일까요? 임의의 양의 정수 n에 대하여 n번째 Harmonic Number Hn은 다음과 같이 정의됩니다. Hn = 1+1/2+1/3+...+1/n으로 정의되는 수를 n번째 조화수 라고 합니다. 오늘은 임의의 자연수 n에 대하여 Hn은 절대 자연수가 될 수 없음을 증명하도록 하겠습니다. 조화수는 자연수가 될 수 없음 일단 자연수 M을 다음과 같이 정의해 봅시다. M = lcm(1,2,3,4,...,n) (M은 1부터 n까지의 모든 정수에 대한 최소공배수) 그러면 1부터 n까지의 모든 정수 k에 대하여 k * ak = M을 만족시키는 정수 ak가 반드시 존재합니다. 그러면 Hn을 다음과 같은 식으로 바꿀 수가 있습니다. 여기서 M은 반드시 짝수입니다. 왜 그럴까요? 아.. 2022. 4. 19. [Euclid's theorem] 소수의 무한성 이해하기 쉽게 증명하기 소수는 무수히 많다 Euclid's theorem 유클리드의 정리 소수(1과 자기 자신으로밖에 나누어 떨어지지 않는 수)는 무한히 존재한다는 정리입니다. 소수를 한번 나열해 볼까요? 2,3,5,7,11,13,17,19,23...... 소수는 끝없이 나열할 수 있으며, 그 개수는 무한입니다. 소수가 무한 개라는 것을 과연 어떻게 증명할 수 있을까요? 후술할 산술의 기본정리(Fundamental Theorem of Arithmetic)와 수학적 귀류법(Proof of contradiction)을 이용하여 직관적이고 쉬운 방법으로 증명할 수 있습니다. 듣자마자 패닉이 옵니다. 하지만 내용을 들여다보면 별볼일 없으므로 저의 논리를 그대로 따라오시기만 하면 자동으로 증명이 됩니다. 산술의 기본정리(Fundamen.. 2022. 4. 18. 이전 1 2 3 다음
