정수론6 에라스토 테네스 체 [Sieve of Eratosthenes] 및 증명 이해하기 오늘은 특정 자연수 이하의 소수를 찾는 알고리즘인 에라스토테네스의 체, 그리고 여기에 활용되는 소수 관련 수학적 정의를 증명하는 시간을 가져 보겠습니다. 에라스토테네스의 체 [Sieve of Eratosthenes] 에라스토테네스의 체란 기계의 도움 없이 순수 손 계산을 사용하여 특정 자연수 이하의 소수를 구하는 유일한 알고리즘입니다. 에라스토테네스의 체를 설명하기 전에 다음 수학적 정의를 설명하겠습니다. n이 합성수라면 p | n, p 2022. 4. 21. [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. 한국수학올림피아드[KMO] 2018 중등부 12번 풀이 1번과 2번 식이 주어져 있고, 이 식들을 이용하여 a + b를 구하는 문제이다. 최대공약수와 최소공배수를 식으로 나타내고 정리해서 몇가지 Case로 나눠 추론하면 풀리는 문제이다. 두 양의 정수 a와 b를 다음과 같이 나타내보자 두 양의 정수 a와 b의 최대공약수를 d라고 정의하면, a = d * s b = d * t (s와 t는 Relatively Prime) 위와 같은 식을 세울 수가 있다. 위 값을 2번 식에 대입해 보자 ab + lcm(a,b) = 432이므로 ds * dt + dst = dst(d + 1) = d(d+1)st = 432이다 432를 소인수분해하면 d(d+1)st = 2*2*2*2*3*3*3 으로 나타낼 수 있다. 우리가 정리한 식을 다시 한번 자세히 보자 d(d+1)st = 2.. 2022. 4. 15. 국제수학올림피아드[IMO] 1959 1번 문제 풀이 다른 대회도 아니고 무려, 세계의 수학 천재들은 다 모인다는 국제 수학 올림피아드 문제이다. 하지만 문제의 난이도는 지금 기준으로는 굉장히 쉬운 문제이다. 기원전 300년 경에 이미 발견된 Euclidean algorithm을 이용하면 단 두 줄에도 풀이가 가능한 문제이기 때문이다. 문제풀이 (21n + 4) / (14n + 3)이 irreducible(기약분수)임을 증명하라고 한다. 그러면 gcd(21n+4,14n+3) = 1임을 보이면 되겠다. 어떤 두 정수의 gcd를 구할 때, 두 정수가 충분히 작다면 손으로 구할 수 있겠지만. 두 정수가 너무 클 경우엔 어떻게 할까? 예를들어 133118과 4528의 최대공약수를 곧바로 구할 수 있겠는가? 이럴 때는 Euclideam Algorithm(유클리드 호.. 2022. 4. 13. 이전 1 2 다음
