mod D를 취하고 QR문제로 바꾸자만약 mod D에서 해가 없으면 펠 방정식의 해는 없음 방정식에 대하여, 양의 정수해 (x, y)를구하거나 혹은 왜 해가 존재하지 않는지 설명하여라.(a) x^2 − 11y^2 = 7(b) x^2 − 11y^2 = 433x^2 − 11y^2 = 7만약 x^2 − 11y^2 = 7 의 해가 존재한다면x^2 − 11y^2 ≡ 7 (mod 11) 또한 참일 것이다.즉, 대우명제를 취하면,x^2 − 11y^2 !≡ 7 (mod 11) => x^2 − 11y^2 = 7 의 해가 존재안함x^2 − 11y^2 ≡ x^2 ≡ 7 (mod 11)그러나, 7은 mod 11에서 NR이므로식을 만족하는 x는 존재하지 않는다.따라서 해가 없음x^2 − 11y^2 = 433x^2 − 11y^2..

펠 방정식 정리항상 양의 정수해를 가짐해 (x1, y1)이 가장 작은 정수해라면?모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다.펠 방정식 정리에 의하면, 제일 작은 해만 구하면 나머지 해를 알 수 있다고 한다.근데 손으로 구하기엔 너무 노가다임...-> 컴공 식으로 해결해보자 $(x_1+y_1\sqrt{D})^k$에서 어떻게 계수만 뽑아낼 수 있을까?바로 이항정리를 응용하면 된다.$$(x_1+y_1\sqrt{D})^k = \sum_{k=0}^{n}{{n \choose k}\space x_1^{n-k}\space {(\sqrt{D}y_1)}^{k}}$$로 표현할 수 있고, k에 따라 $\sqrt{D}$가 나오는지 여부가 갈린다 ..

디리클레의 디오판토스 근사형식 - 제 2형식: a > 0 인 무리수 a에 대해 | x - ya | 보여야 할 것이 총 3가지로 어떤 해 x, y가 | x - ya | x, y가 무한히 많이 나오는가? x, y가 양의 정수인가?x, y가 | x - ya | 적당히 큰 수 Y에 대해0a, 1a, ..., Ya를 정수부 N, 소수부 F로 나눠보자단, N >= 0, 0 0a = N0 + F0 1a = N1 + F1 ... Ya = NY + FY이떄 비둘기를 F로 두자. -> Y+1개그리고 0~1을 Y등분한 구간을 비둘기 집으로 두면 -> Y개비둘기 집의 원리에 의해 적어도 2개의 비둘기가 같은 집에 있다.즉, Fm, Fn이 같은 구간에 들어있다.즉, | Fm - F..

해의 갯수를 판정하는 문제?-> 정확한 해의 갯수와 비교! 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에..

따로 삽입, 삭제가 필요하진 않으므로,기존의 linked list로 트리를 구현하는게 아니라 배열로 구현한다!-> 빠르고 가벼움 기본 골조인덱스 i의 부모를 저장하는 parent 배열과어떤 집합의 rank를 저장하는 rank 배열을 가지고 구현한다 rank는 root일때만 쓰이므로 그것만 잘 업뎃해주면 됨#define MAX_SIZE 10000int parent[MAX_SIZE];int rank[MAX_SIZE];//자기 자신만 원소로 갖는 트리 생성void init_set(int n){ for (int i = 0; i find최대 O(n)으로 재귀적으로 root를 찾는다.int find(int x){ if (parent[x] != x){ //대표 노드가 나올때까지 탐색 p..

주어진 정수 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 ..