Processing math: 40%

정수론 47

[정수론](-)[(어떤 식)의 이차잉여인가?]

(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)를 xk+ykD =(x1+y1D)k 로 구할 수 있다.펠 방정식 정리에 의하면, 제일 작은 해만 구하면 나머지 해를 알 수 있다고 한다.근데 손으로 구하기엔 너무 노가다임...-> 컴공 식으로 해결해보자 (x1+y1D)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형식]

디리클레의 디오판토스 근사형식 - 제 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..

[정수론](-)[X^k ≡ 1 (mod p)의 해의 갯수]

해의 갯수를 판정하는 문제?-> 정확한 해의 갯수와 비교! 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가 완전제곱수가 아닌 이유?]

펠 방정식은 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 ..

728x90
반응형