[정수론](-)[6k+5 소수]

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 ≡ 1 (mod 6) -> ㄱㅊ
    q ≡ 2 (mod 6) -> q=6k + 2 꼴이므로 2만 되고 그 이상은 짝수라 안됨
    q ≡ 3 (mod 6) -> q=6k + 3 꼴이므로 3만 되고 그 이상은 3의 배수라 안됨
    q ≡ 4 (mod 6) -> 4 자체도 합성수고 그 이후도 짝수이므로 안됨
    q ≡ 5 (mod 6) -> ㄱㅊ
    따라서 mod 6에서 q가 소수가 되는 것은
    2, 3, 1 (mod 6), 5 (mod 6)이다.

  그러나, q가 A 약수인 조건이 남아있다.
  A = 6k+5 꼴이므로,

    2 -> 2∤A 이므로 q 안됨.
    3 -> 3∤A 이므로 q 안됨.
    따라서 q는 1 (mod 6), 5 (mod 6) 중 1개다.

  만약 모든 q가 1 (mod 6)라면

    q1\*q2\*...\*qs ≡ 1^s !≡ 5 (mod 6)이므로 A의 조건을 만족하지 않는다.
    따라서 q중 적어도 1개는 6k+5꼴이어야 한다.

  모든 p들은 5 (mod 6)이므로 A를 나누지 않는다.
  그러나, q|A이므로 q는 p들과 다른 새로운 6k+5꼴의 소수이다.
  q는 R에 속하지 않으므로 모순
  따라서 모든 경우에서 모순이므로,
  6k+5꼴의 소수는 무한하다.