무한소수정리소수는 무한히 많다증명만약 소수가 유한하고 유한개의 소수 집합 R = {p1, p2, ..., pr}이 있다 가정A = p1*p2*...*pr + 1이라는 수를 잡으면만약 A = 소수?A는 R에 없는 소수이므로 모순 발생만약 A = 합성수?소수의 가약성에 의헤 A는 소수의 곱으로 표현 가능하다.이때 A를 나누는 가장 작은 소수를 q라 한다면 만약 q = pi라면 q|pi, q|A => q|1이어야 하는데 불가능 따라서 q != pi이걸 모든 p에 대해 반복한다면 모든 p가 q와 다른 수라는 걸 알 수 있다.따라서 q는 R에 없는 새로운 수 이므로 모순 발생디리클레의 등차수열 정리gcd(a, m) = 1인 정수 a, m이 있을 때, p ≡ a (mod m)인 소수 p가 무한히 많다...

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

정수론 수업을 듣고 흥미로운 문제를 들었다.n차 합동방정식은 n개의 서로 다른 해를 가지는데 왜 RSA는 복호화가 잘 되는가?이거에 대해 알아본 결과.A를 특정 값으로 제한해서 복호화가 망가지는 걸 억제하는 것이였다. A값의 제한으로 여러 해 나오지 않게 하기m = pq (p, q는 소수)gcd(ϕ(m), k) = 1 에서 암호화는 c ≡ a^k (mod m) 이다.당연히 c는 양수(암호문은 항상 양수만 생각)이고 m에 대해 유일하다. 그럼 문제의 복호화는?x ≡ c^u ≡ a (mod m) 이다.이때 gcd(ϕ(m), k) = 1 이므로 선형방정식의 정리에 의해ku-ϕ(m)v = 1에서 해 ui, vi를 구할 수 있고 식을 변형하면 ku ≡ 1 mod(ϕ(m))이다.gcd(ϕ(m), k) = 1이므로 ..