[정수론](10)[무한소수정리]

무한소수정리

소수는 무한히 많다

• 증명
  만약 소수가 유한하고 유한개의 소수 집합 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가 무한히 많다.
예) 4a+3꼴의 소수, 5a+3꼴의 소수는 무한히 많다.
이거 증명은 복소해석학까지 사용하므로 너무 어려워서 걍 결과만 알고 간다.
물론 개개의 4a+3, 6a+5꼴의 소수가 무한함은 나도 증명 가능하다.

6k+5 꼴의 소수 무한함 증명 참고