[정수론](-)[p가 소수일 때 (p로 표현된 식) 소수 판정]

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가 합성수임을 보여라
  p>=5 이므로 p != 2, 3
  따라서 p는 정수 k에 대해
      3k+1
      3k+2 꼴로 표현 가능하다.
  if (p == 3k+1) 라면
      p^2 ≡ 9k^2+6k+1 ≡ 3(3k^2+2k)+1 ≡ 1 (mod 3)
      p^2+2 ≡ 1+2 ≡ 3 ≡ 0 (mod 3)
      따라서 이 경우엔 3 | p^2+2이므로 합성수라 소수 안됨 (p^2+2 != 3)
  else if (p == 3k+2) 라면
      p^2 ≡ 9k^2+12k+4 ≡ 3(3k^2+4k+1)+1 ≡ 1 (mod 3)
      p^2+2 ≡ 1+2 ≡ 3 ≡ 0 (mod 3)
      따라서 이 경우도 3 | p^2+2이므로 합성수라 소수 안됨 (p^2+2 != 3)
  따라서 p>=5인 모든 정수 집합에서 p^2+2가 합성수이다.