목록수학 (21)
넘치게 채우기
만일 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-제곱수로 나누는 것은 불가능한 일이다. 나는 이에 대해 놀라운 증명을 발견했지만, 이를 남기기에는 여백이 부족하다. - 페르마 페르마의..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/eAIfhq/btsFygaMA4O/SsLRXBwsRVKoG0UPbynuPK/img.png)
이전 장에서 다음 방정식의 모든 자연 수 해를 찾는 방법을 제시하였다: 이 등식의 양번을 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)을 만들어보아라. 이런 추측은 보통 공식으로 나타낼 수 있다. 추가 자료를 모으고 새로운 정보가 추측에 부합하는지 확인하여 추측을 검증하여라. 추측이 참으로 보일 방법(증명)을 고안하라.
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/qIx3G/btsD5zhTqY8/KI5ojnWxWEkmEJL4TKvKZk/img.png)
마호니언 숫자의 삼각형(또는 마호니언 삼각형)의 수들은 ∏(𝑖=0..𝑛−1)(1+𝑥+...+𝑥𝑖)를 전개했을 때의 각 계수이다. 코시 곱에 의해서 1부터 n까지의 순열에서 K번의 역전이 일어난 순열의 개수임이 증명된다. k는 해당하는 순열을 increasing order로 만들기 위한 버블정렬의 스왑 횟수와도 같다. 삼각형은 좌우대칭의 형태를 가진다. 순열의 무질서도와 정규 분포에도 관련이 있다. 공식 T(n, k)를 1부터 n까지의 순열에서 K번의 역전이 일어난 순열의 개수라고 하였을 때, 다음이 성립한다. T(1, 0) = 1, T(n, k) = 0 for n n*(n-1)/2. T(n, k) = Sum_{j=0..n-1} T(n-1, k-j) 정리하면, T(n, k)..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/rayyD/btsDngRyLCv/42692PujVkKvE8BqBecbuK/img.png)
선형변환의 정의 V와 W가 벡터공간이고, u, v가 V에 속하며 a가 실수인 경우, V로부터 W로가는 함수 L이 아래 2가지를 만족할 때, 선형변환(linear transformation)또는 선형사상(linear mapping)이라고 한다. L: V->W L(u+v) = L(u) + L(v) L(au) = aL(u) 특히 V = W일 경우에는 선형변환 L을 V상에서의 선형연산자(linear operator)라고 한다. L(x) = 2x는 선형변환인가? L(x+y) = 3(x+y) =3x+3y =L(x)+L(y) L(ax) = 3(ax) =a(3x) =aL(x) 선형변환이다. 함수와 선형변환 집합 X에서 집합 Y로의 관계의 부분집합으로써, 집합 X의 모든 원소 x가 집합 Y에 있는 원소 중 한 개와 관계..