넘치게 채우기

카탈란 수(Catalan number)란, 이진 트리의 수를 셀 떼 등장하는 수열이다. 응용으로는, 올바른 괄호쌍 개수: 프로그래머스 올바른 괄호의 개수이진 트리의 수: 노드 n개를 가진 서로 다른 이진 탐색 트리(BST)의 수다각형의 삼각분할: n+2변짜리의 다각형을 삼각형으로 분할하는 경우의 수  https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

산술기하 평균 부등식(arithmetic - geometric mean inequality)이란, 산술평균과 기하평균 사이에 성립하는 부등식이다. 임의의 음수가 아닌 실수들에 대하여, 그 산술 평균은 그 기하 평균보다 크거나 같으며, 정확히 모든 실수들이 같은 경우에만 두 평균이 같다.   $$ \frac{a_1 + a_2 + ... + a_{n-1} + a_n}{n}= \sqrt{a_1 \times a_2 \times ... \times a_{n-1} \times a_n} ^\frac{1}{n}​ $$ 이는 경제학, 컴퓨터과학, 통계학 등, 실생활에 유용하게 쓰이는 부등식이다.

만일 m이 a-b를 나눌 때, a와 b가 모듈러 m에 대해 합동이다. 특히, a를 m으로 나눈 나머지가 r이면, a와 r는 모듈러 m에 대해 합동이다. 이떄, 나머지 r은 0 = 1이고 gcd(a, m) = g를 만족한다고 하자. 만일 g !| b이면, 합동방정식 은 해를 가지지 않는다. 만일 g | b이면, 합동방정식 정확히 g개의 서로 다른 해를 가진다. 모든 해를 찾으려면, 우선 일차방정식 au + mv = g의 해 (u0, v0)을 찾는다. x0 = cu/g가 의 해가 되고, 모든 합동이 아닌 해는 과 같이 나타낼 수 있다. 주의 선형 합동방정식 정리에서 가장 중요한 경우는 gcd(a, m) = 1인 경우이다. 이 경우, 합동방정식은 단 하나의 해를 가진다. 고차 합동방정식 고차 합동방정식도 수론..

2 이상의 정수 p의 약수가 1과 p 뿐일 때, p를 소수(prime number)라고 부른다. 2 이상의 소수가 아닌 수를 합성수(composite number)라고 부른다. 소수 p가 곱 ab를 나눈다고 가정하자. 그러면 p는 a를 나누거나, b를 나눈다. (또는 a와 b 모두 나눈다.) 증명) p가 곱 ab를 나눈다고 하자. 만일 p가 a를 나눈다면 증명이 끝나므로, 나누지 않는다고 가정하면, gcd(p, a)가 어떤 수인지 생각해야 한다. 이 수는 p를 나누므로, 1 또는 p이다. p가 a를 나누지 않으므로, p는 1이다. 6장의 정리를 이용하여, px + ay = 1에서 양변에 b를 곱한다. pbx + aby = b pbx는 p로 나누어지고, p가 ab를 나누므로, aby 역시 p로 나누어진다...

두 개의 정수 a, b가 주어졌을 때, a의 배수와 b의 배수로 만들 수 있는 수를 모두 찾아보자. 다시말해, ax + by에서 x와 y에 대입해 만들 수 있는 수를 찾아보자. a=42, b = 30으로 해보자. x = -3 x = -2 x = -1 x = 0 x = 1 x = 2 x = 3 y = -3 -216 -174 -132 -90 -48 -6 36 y = -2 -186 -144 -102 -60 -18 24 66 y = -1 -156 -114 -72 -30 12 54 96 0 -126 -84 -42 0 42 84 126 y = 1 -96 -54 -12 30 72 114 156 y = 2 -66 -24 18 60 102 144 186 y = 3 -36 6 48 90 132 174 216 표의 수들이 ..

인 정수 m과 n이 있다고 해보자. 만일 n이 m의 배수라면, n=mk를 만족한다면, 'm이 n을 나눈다'라고 한다. 만일 m이 n을 나누면 우리는 m|n이라고 쓴다. n을 나누는 수를 n의 약수라고 부른다. 만일 우리가 두 개의 정수를 가지고 있다면, 우리는 이 두 정수를 모두 나누는 공약수(common divisor)를 찾을 수 있다. 모두 0은 아닌 두 수 a와 b의 최대공약수는 a와 b를 모두 나누는 수 중에서 가장 큰 수이다. 기호로는 gcd(a, b)로 표기한다. 만일 gcd(a, b) = 1일때, 우리는 'a와 b는 서로소이다'라고 한다. 최대공약수를 찾는 가장 효율적인 방법은 유클리드 호제법(Euclidian algorithm)이다. 이 방법은 나머지가 0이 되도록 나눗셈을 반복하는 것이다..

우리는 앞장에서 방정식 이 여러 개의 정수해를 갖는다는 것을 확인하였다. 그렇다면 지수가 2보다 큰 수일 경우에는 어떨까? 은 0이 아닌 정수해를 가질 수 있을까? 답은 '아니오'이다. 1673년즈음, 페르마는 지수가 4인 경우를 증명했고, 18세기와 19세기, 가우스와 오일러는 지수가 3인 경우를 증명했고, 디리클레와 르장드르는 지수가 5인 경우를 다루었다. 이는 페르마의 마지막 정리(Fermat's last theorem)으로 알려져 있다. 세제곱수를 두 개의 세제곱수로, 네제곱수를 두 개의 네제곱수로 쪼개는 것은 불가능하다. 혹은 일반적으로 n-제곱수를 두 개의 n-제곱수로 나누는 것은 불가능한 일이다. 나는 이에 대해 놀라운 증명을 발견했지만, 이를 남기기에는 여백이 부족하다. - 페르마 페르마의..

이전 장에서 다음 방정식의 모든 자연 수 해를 찾는 방법을 제시하였다: 이 등식의 양번을 c^2로 나누면 다음과 같다: 즉, 유리수 쌍 (a/c, b/c)는 다음 방정식의 해가 된다: 이는 (0, 0)을 중심으로 하는 단위원 C이다. 단위원 C의 기하적 성질을 이용하여 C위의 점들 중에서 xy좌표가 모두 유리수인 점을 찾아보자. 우선, (1, 0), (-1, 0), (0, 1), (0, -1)이 있다. 이 중에서 점 (-1, 0)을 지나고 기울기가 m인 직선 L을 생각해보자. 직선 L의 방정식은 다음과 같다: 원과 직선의 교점은 두 개이고, 하나는 (-1, 0)이다. 위의 두 식의 연립방정식을 풀면, 아래와 같다: 위 공식에 m=v/u를 대입하면 . 피타고라스 세 수를 얻을 수 있다.

피타고라스 세 수 (a, b, c)를 만족하는 자연수는 무한히 많은가? 답은 "그렇다"이다. 하나의 피타고라스 세 수(a, b, c)가 있다면, 적당한 수 d를 곱해보자. (da, db, dc)도 피타고라스 수가 된다. 원시 피타고라스 세 수(Primitive Ptyhagorean triple, PPT) 원시 피타고라스 세 수는 공약수를 가지지 않고, 를 만족하는 세 자연수 a, b, c이다. 예시) 3, 4, 5 5, 12, 13 8, 15, 17 7, 24, 25 20, 21, 29 ... a와 b중 하나는 짝수, 하나는 홀수이다. 또한, c는 항상 홀수인 것 같다. 이를 증명해보자. 증명) a와 b가 모두 짝수라고 하면, c도 짝수이다. 세 수 모두 짝수이면, 공약수가 2가 되므로 모두 짝수가 될 ..

수론이란, 자연수라 불리는 양의 정수의 집합에 대한 연구이다. 수론, 수학에서 필요한 문제풀이 과정 자료를 모아라. 보통 자료는 수치적이지만 추상적인 경우도 있다. 모은 자료를 조사하고 규칙성과 관련성을 찾아보아라. 규칙성 및 관련성을 설명하는 추측(conjecture)을 만들어보아라. 이런 추측은 보통 공식으로 나타낼 수 있다. 추가 자료를 모으고 새로운 정보가 추측에 부합하는지 확인하여 추측을 검증하여라. 추측이 참으로 보일 방법(증명)을 고안하라.