위수 = p-1을 잘 써먹어야 한다.p가 홀수인 소수이고 g가 법 p에 대한 원시근이라고 하자. g^k가 법 p에 대해서 이차잉여이기 위한 필요충분조건은 k가 짝수라는 것을 증명하여라. ( g^k=QR k = 2t라고 하자.g^k = QR 이라는 것은 g^k ≡ x^2 (mod p)인 x가 존재한다는 뜻이다.g^t ≡ g^2t ≡ (g^t)^2 (mod p)이므로x = g^t로 존재하므로 참이다. (=>) g^k=QR => k=짝수 홀수, 짝수 조건이 더 다루기 쉬우므로, 대우명제를 이용하면,k=홀수 => g^k = NR을 증명하면 된다. k = 2t + 1이라 하자p = 홀수 소수, gcd(g, p) = 1 이므로 오일러 판별법에 의해,(g^k)^((p-1)/2) ≡ (g/p) (mod p)≡ g^(p..

a가 법 p에 대한 삼차잉여(cubic residue modulo p)라함은, a가 법 p로 어떤 세제곱수와 합동이라는 의미이다. p ≡ 2 (mod 3)일 때, {1, 2, ..., p-1}이 삼차잉여가 됨을 증명하라.p = 3k + 2 인 소수일 때페르마의 소정리에 의해 gcd(a, p) = 1인 a에 대해 a^(p-1) ≡ a^(3k+1) ≡ 1 (mod p) a^p ≡ a^(3k+2) ≡ a (mod p)가 만족한다. 이 두 합동방정식을 곱하면,a^((3k+1) + (3k+2)) ≡ a^3(2k+1) ≡ a (mod p)≡ (a^(2k+1))^3 ≡ a (mod p) 즉, gcd(a, p) = 1인 모든 a는 삼차잉여가 된다.p는 소수이므로, gcd({1, 2, ..., p-1}, p)..

펠 방정식 x^2 − 11y^2 = 1의 모든 해는 10 + 3√11을 거듭제곱하여 얻을 수 있음을 증명하여라. 무한강하법 증명 삼각-사각수를 증명할 때 썼던 무한강하법으로 증명해보자음수해는 양수해에 -만 붙이면 되므로 양수해에 대해서만 증명하면 된다. 임의의 해 u, v가 있다고 하자.만약 u = 10이면? => (10, 3)으로 참 만약 u > 10 이라면?어떤 수 s, t에 대해u + v√11 = (10 + 3√11)*(s+t√11) 로 나눌 수 있다.이때 s가 다음 조건을 만족하면 무한강하법을 쓸 수 있다.s, t가 양의 정수인가?정수 증명(10 + 3√11)*(s+t√11) = (10s + 33t) + (3s + 10t)√11즉, u = 10s - 33t, v = 3s + 10t식을 정리하면 s..

정수론 17 의 보조정리$$\sum_{k=1}^P{\lfloor{\frac{ka}{p} }\rfloor} \equiv \mu(a, p) \space (mod \ 2) $$얘는 p가 홀수 소수이고 a가 홀수일 때만 성립한다.따라서 a가 짝수 버전도 증명해보자.p는 홀수인 소수이고, P = (p-1)/2이라 하자. 또한 a는 p로 나누어지지 않는 짝수인 정수라고 하자. 다음 식을 보여라: 시그마 1~P (⌊ka/p⌋) ≡ (p^2−1)/8 + µ(a, p) (mod 2).먼저 ⌊kap⌋를 정리해보자.ka = p*q + r 이라고 하자 {0ka/p = q + r/p⌊ka/p⌋ = r >= 0: q r 즉, 나머지가 음수가 나오는 개수 (= µ의 정의) 만큼 -1 해주면 된다.따라서 $$\sum_{k..

이차방정식의 해가 존재하려면b^2 - 4ac 가 p의 이차잉여이다.a의 역원이 존재한다 (즉, gcd(a, p)= 1 또는 p가 a를 나누지 않음둘이 필요충분조건이다.p를 홀수인 소수이고 gcd(a, p) = 1이라 하자. 이차 합동식 ax^2 +bx+c ≡ 0 (mod p)의 해가 존재할 필요충분조건은 b^2 − 4ac가 0이거나 p의 이차잉여임을 보여라.이차합동방정식 ax^2 + bx + c ≡ 0 (mod p)를(b^2 - 4ac) = ■^2 (mod p) 꼴로 변형해보자.양 변에 4a를 곱해주면,4a^2x^2 + 4abx + 4ac≡ (2ax + b)^2 - b^2 + 4ac≡ 0 (mod p) (=>) 해를 가짐 => b^2 - 4ac 가 0 또는 이차잉여해 k가 존재한다면,b^2 - 4ac ≡..

ϕ = em(a)k + r이라고 하고위수의 성질로 r이 0임을 보이자-> 위수가 ■을 나누는가에서도 응용 가능서로소인 정수 a와 m에 대해서 a^e ≡ 1 (mod m)을 만족하는 가장 작은 지수 e ≥ 1을 em(a)라고 정의하고 법 m에 대한 a의 위수(order of a modulo m)라고 부른다. em(a)가 항상 ϕ(m)의 약수임을 증명하여라.ϕ(m) = em(a)k + r 라 두자.{0 r = 0임을 보이면 e | ϕ(m)를 보일 수 있다. gcd(a, m) = 1 이므로, 오일러 공식에 의해,a^ϕ(m) ≡ a^(em(a) * k + r) ≡ 1 (mod m)이때, 위수의 정의에 의해 a^em(a) ≡ 1 (mod m) 이므로,a^em(a) * k ≡ (a^em(a))^k ≡ 1^k ≡ 1..

(a / (어떤식)) 꼴의 르장드르 기호에서(어떤 식) ≡ ■ (mod 4)를 연산해서 뒤집어주고 계산해준다! 모든 n에 대해 4^n ≡ 4 (mod 12)임을 보이고, 이를 이용하여 3은 2^2n + 1 꼴의 모든 소수의 이차비잉여임을 증명하여라. 또한 3이 2^p − 1 꼴(p는 홀수인 소수)의 모든 소수의 이차비잉여임을 증명하여라 1. 4^n ≡ 4 (mod 12)귀납법을 이용한 증명n = 1 ?4 ≡ 4 (mod 12) 참n = k에서 참이라고 가정할 때 n = k+1 ?4^k ≡ 4 (mod 12) 라고 가정하자.4^(k+1) ≡ 4 * 4^k≡ 4 * 4 ≡ 16 ≡ 4 (mod 12)이므로 참 2. 3은 2^2n + 1 꼴의 모든 소수의 이차비잉여?(3 / 2^2n+1) = -1 임을 보이면..

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..