응

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

위수 = 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 ≡..