해의 갯수를 판정하는 문제?-> 정확한 해의 갯수와 비교! k가 p-1의 약수이면 합동식 x^k ≡ 1 (mod p)가 법 p에 대해서정확히 k개의 서로 다른 해를 가진다는 것을 증명하여라. (단, p는 소수이다) p-1 = kt {t = 정수} 라고 하자. X^(p-1) ≡ 1 (mod p)의 해의 갯수를 살펴보자. p=소수이므로, 페르마의 소정리에 의해, gcd(X, p) = 1인 X에서 항상 X^(p-1) ≡ 1 (mod p)를 만족한다. 즉, X = {1, 2, ..., p-1}에 대해 페르마의 소정리가 항상 만족한다.따라서 X^(p-1) ≡ 1 (mod p) 해의 갯수는 정확히 p-1개이다 X^(p-1) - 1≡ 0 (mod p)로 바꾸고 식을 전개하면X^(p-1) - 1 ≡ (..

피타고라스 세 수 정리1 보다 크고 서로소인 홀수 s>t가 주어진다면 a=st, b=(s^2-t^2)/2, c=(s^2+t^2)/2 으로 원시 피타고라스 세 수가 만들어진다.그리고 모든 원시피타고라스 세수는 이 꼴로 생성될 수 있다.유클리드 호제법: gcd 빠르게 구하기예) gcd(36, 132)132 = 36 * 3 + 2436 = 24 * 1 + 1224 = 12 * 2 + 0gcd(36, 132) = 12선형방정식 정리a, b는 0이 아닌 정수, g = gcd(a, b)일때,ax+by=g는 항상 정수해 (x, y)을 가지며, 유클리드 호제법으로 찾을 수 있다.이때 모든 정수해는 (x+(bk/g), y-(ak/g)) (k는 임의의 정수)소수의 가약성p|a1*a2*...*an 이면 p는 a중 적어도 1..

서로소인 정수 a와 m에 대해서 a^e ≡ 1 (mod m)을 만족하는 가장 작은 지수 e ≥ 1을 em(a)라고 정의한다a가 m과 n 모두와 서로소이고 gcd(m, n) = 1이라고할 때, emn(a)를 em(a)와 en(a)를 이용하여 나타내어라 위수의 성질에 의해 a^em ≡ 1 (mod m) a^en ≡ 1 (mod n) a^emn ≡ 1 (mod mn) a^■ ≡ 1 (mod m), a^■ ≡ 1 (mod n)꼴로 만들어서 합치고 싶으므로,em, en의 최소공배수 lcm을 잡는다.em * p = en * q = lcm(em, en) a^lcm(em, en) ≡ a^(em * p) ≡ (a^em)^p ≡ 1^p ≡ 1 (mod m) a^lcm(em, en) ≡ a^(en..

펠 방정식은 D가 완전제곱수가 아닌 양의 정수일 때 방정식 x^2−Dy^2 = 1을 말한다.D가 완전제곱수가 아닌 이유를 설명하여라.D = A^2이면 방정식 x^2 − A^2y^2 = 1의 정수해에 대하여 설명할 수 있는가?D = A^2라고 하자. {A > 0}이때 펠 방정식을 인수분해할 수 있다.x^2 − A^2y^2 = (x - Ay)(x + Ay) = 1x, y, A 는 정수이므로, x - Ay, x + Ay도 정수이다.즉, 식을 만족하는 경우의 수는 x - Ay = 1, x + Ay = 1 x - Ay = -1, x + Ay = -1x - Ay = 1, x + Ay = 1두 식을 정리하면x = 1, y = 0 밖에 안나옴x - Ay = -1, x + Ay = -1두 식을 정리하면x = ..

-> 지수에서 합동은 p-1이다.즉, 지표 합동연산은 p-1에서 하고다시 돌아올 때는 p로 복귀!주의mod N -> mod n은 가능하다 (n|N)예) 9 ≡ 5 (mod 4) -> 9 ≡ 5 (mod 2)예) 18 ≡ 2 (mod 16) -> 18 ≡ 2 (mod 4)따라서 mod p에서 합동이면 mod p-1에서도 합동이다.만약 한두번 계산할 거면 그냥 푸는게 낫지만,여러번 특정 mod에 대해 풀거면 지표의 표를 만들고 구하면 빠르게 구할 수 있다.지표의 정의와 연산법칙을 잘 활용하자.$$g^{{I}(a)} \equiv a \ (mod \ p)$$지표의 연산법칙곱셈법칙: I(a) + I(b) ≡ I(ab) (mod p-1)거듭제곱 법칙: I(a^k) ≡ kI(a) (mod p-1) 예) mod 37에..

주어진 정수 n이 카마이클 수이고, 소수 p는 n의 약수라 하자. p − 1이 n − 1을 나눈다는 사실을 증명하여라. 또한, p − 1이 사실은 더 작은 수인 n/p − 1을 나눔을 증명하여라. p − 1이 n − 1을 나눈다는 사실을 증명 카마이클 수의 성질에 의해 gcd(a, n) = 1에 대해a^(n-1) ≡ 1 (mod n)=> a^(n-1) ≡ 1 (mod p) mod small은 언제나 성립p는 소수이므로, 원시근 g가 존재하고 a = g라고 두자.g^(n-1) ≡ 1 (mod p)g에서 위수 e = p-1이고,위수의 나눔성질에 의해 e | n-1이다.즉, p-1 | n-1이다. p − 1이 n/p − 1을 나눔을 증명 n = pm이라고 하자.n/p - 1 = m - 1이다.위에서 p-1 ..

피보나치 수열F1 = 1, F2 = 1이고Fn = Fn-1 + Fn-2 인 재귀식을 가지는 선형점화수열성질커지는 비율이 약 1.61803... 정도Fn 이 약 kFn-1 이라고 하자. 이 k를 구해보자.Fn-1 ~ kFn-2, Fn ~ kFn-1 ~ k^2 Fn-2즉, 점화식을 대략적으로 다시 표현하면k^2 Fn-2 = kFn-2 + Fn-2F>0이므로 양변을 Fn-2로 약분한다면,k^2 = a + 1근의 공식을 이용하면$$k = \frac{1+\sqrt{5}}{2}\space or \space \frac{1-\sqrt{5}}{2}$$피보나치 수는 점점 커지는 수열이므로,(1+root(5)) / 2 = 약 1.6180339887498948.... 비네의 공식$a = \frac{1+\sqrt{5}}{2}\..

이항정리이항계수와 이항정리 이항계수n개 중 k개를 뽑는 경우의 수nCk = {n(n-1)(...)(n-k+1)} / {k!}= n! / { (n-k)! k! } 이항계수 덧셈공식nC(k-1) + nCk = (n+1)Ck증명 직접 이항계수 계산해보기 (A+B)^(n+1) = (A+B)^n * (A+B)이용하기 조합론적 접근1~n+1의 수 중 k개를 뽑는다고 하자.그냥 1~n+1 까지 뽑는 경우의 수= n+1이 포함된 경우의 수 + n+1이 포함되지 않은 경우의 수 로나누어질 수 있다.즉, (n+1)Ck = nC(k-1) + nCk 이항정리너무 유명한 거라 적기만 함...$$(A+B)^{n} = \sum_{k=0}^{n}{ {n\choose k}A^{n-k}B^k }$$ ..

이번엔해 (x1, y1)이 가장 작은 정수해라면 모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다.를 증명해보자.2. 모든해를 구할 수 있는지 증명(x1, y1)이 가장 작은 양의 정수해고, (a, b)를 x^2 - Dy^2 = 1의 임의의 양의 정수해라 하자.그리고 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 에서 나온 값이라 하자.이때 [[23 정수론 정리]]에서 보인 것처럼 xk, yk는 펠 방정식의 새로운 해다.그리고 z = x1 + y1$\sqrt{D}$ , r = a + b$\sqrt{D}$ 라고 두자.이때 모든 (a, b)가 (xk, yk)로만 나올 수 있으면 정리가 증명된다..

|$x-y\sqrt{D} \ |이를 이용해서 펠 방정식 정리를 증명해보자.펠 방정식 정리D가 제곱수가 아닌 양의 정수일 때 펠 방정식 x^2-Dy^2 = 1에 대해,항상 양의 정수해를 가짐해 (x1, y1)이 가장 작은 정수해라면?모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다. 1. 양의 정수해를 가짐의 증명 디리클레의 디오판토스 근사정리 제 1형식에 따르면|$x-y\sqrt{D} \ |즉, $-\frac{1}{y} 양변에 y$\sqrt{D}$를 더하면 x + y$\sqrt{D}$ 정리하자면, x + y$\sqrt{D}$ 양변에 x-y$\sqrt{D}$를 곱하고, 근사정리 제 1형식을 이용하면,x^2 - Dy^2 즉, 양의 정수해 ..