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

르장드르 기호p = 홀수 소수일때합동으로 계산(kp+r/p) = (r/p)(a/p) = (a-p/p)이건 특히 큰 수에서 인수분해가 힘들 때 숫자를 줄일 수 있다.제곱은 언제나 1(a^2/p) = (a/p)*(a/p)이므로(a/p)값에 상관 없이 항상 값이 1이 나온다.이차상호법칙이차상호법칙 - 1홀수 소수 p에 대해 (-1/p)는p ≡ 1 (mod 4) 일때 1p ≡ 3 (mod 4) 일때 -1이차상호법칙 - 2홀수 소수 p에 대해 (2/p)는p ≡ 1 or 7 (mod 8) 일때 1p ≡ 3 or 5 (mod 8) 일때 -1이차상호법칙 - 3홀수 소수 p, q에 대해 (q/p)는p ≡ 1 (mod 4) or q ≡ 1 (mod 4) 일때 (p/q)p, q ≡ 3 (mod 4) 일때 -(p/q) 야코비..

1. 관찰로 규칙성 찾기그냥 맨바닥 부터 시작하니까 규칙이 감이 안 잡히는데일단 작은 수에 대해서 몇개만 (p로 표현된 식)에 p를 넣어보자.짝수인지 홀수인지, 몇의 배수인지 보는 게 좋다.이때 edge case로 2를 조심해야 한다.2. mod로 정수 집합 분할하기일단 edge case인 2를 처리했다면 mod로 정수들의 집합을 나눠보자.(집합론에선 동치관계가 분할을 형성한다고 배운다.따라서 mod m에 대해 0~m-1에 있는 각각의 case 모음집의 합은 정수 집합과 같다.)2를 제외한 p는 모두 홀수이므로 만약 mod 3에 대해 분할하면p = 3k+1 or 3k+2 or 3 꼴이다.그 다음 각각의 경우에 대해 합성수인지 소수인지 판별하면 된다. 예) 소수 p가 5 이상일 때 p^2+2가 합성수임을 ..

임의의 원시 피타고라스 세 수 (a, b, c)가 있다. 이때 다음을 보여라a or b가 3의 배수인가?언제 a, b, c가 5의 배수인가?a or b가 3의 배수인가?정수 집합을 mod 3의 동치관계로 분할해보자.즉, a, b, c = 3k, 3k+1, 3k+2 꼴이다. (k=정수)만약 a, b 모두 3의 배수가 아니라면?a, b = 3k+1 or 3k+2 꼴이다.a^2 + b^2 = c^2에서 mod 3을 보기 위해 (3k+1)^2, (3k+2)^2에 대한 mod 3을 봐보자.(3k+1)^2 ≡ 3(3k^2+2k)+1 ≡ 1 (mod 3)(3k+2)^2 ≡ 3(3k^2+4k+1)+1 ≡ 1 (mod 3)따라서 a^2+b^2 ≡ 2 (mod 3)일 수밖에 없다.그러나, c가 될 수 있는 3k, 3k+1..

p ≡ 5 (mod 6) 꼴의 소수가 무한함을 보여라.p = 6k + 5꼴의 소수가 유한하다 가정하자.그리고 이 꼴의 모든 소수를 모은 집합 R을 정의한다.R = {p | p = 6k+5, p=소수, k=정수} = {5, p1, p2, ..., pr}그리고 어떤 수 A = 6*(p1*p2*...*pr) + 5라고 정의한다. A = 소수?A는 R에 없는 새로운 6k+5꼴의 소수이므로R이 모든 6k+5꼴의 모음이라는 가정에 모순됨 A = 합성수?산술의 기본정리에 의해 A는 소수들의 곱으로 나타낼 수 있다.A = 6*(p1*p2*...*pr) + 5 = q1*q2*...*qs여기서 소수 q와 합동일 수 있는 것들을 찾아보자. q ≡ 0 (mod 6) -> q=6k 꼴이므로 소수가 아니라 안됨 q ≡ ..