넘치게 채우기

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)을 만들어보아라. 이런 추측은 보통 공식으로 나타낼 수 있다. 추가 자료를 모으고 새로운 정보가 추측에 부합하는지 확인하여 추측을 검증하여라. 추측이 참으로 보일 방법(증명)을 고안하라.

https://leetcode.com/problems/integer-break/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 : 정수론, 수학 문제 난이도 : Medium 문제 Given an integer n, break it into the sum of k positive integers, where k >= 2, and..