일정한 차이가 나는 소수

이 글에서는 일정한 차이가 나는 소수들에 대해 탐구하여 본다. 조금 더 자세히는 다음 성질을 증명한다.

소수 $p$와 자연수 $d$에 대해 $p$, $p+d$, $p+2d$, $\cdots$, $p+(n-1)d$가 모두 소수일 때 $d$는 $n$보다 작은 모든 소수들로 나누어 떨어진다.

---

증명의 방법

위의 명제를 귀류법으로 증명할 것이다. 즉, $q$가 $n$보다 작은 어떤 소수일 때, $d$가 $q$로 나누어 떨어지지 않는다고 가정해보자.

---

완전잉여계 증명

증명은 우선 $p$, $p+d$, $p+2d$ $\cdots$ $p+(q-1)d$가 $q$에 대한 완전잉여계임을 보임으로 시작한다. 이는 귀류법으로 증명할 수 있다.

만일 위의 소수들이 $q$에 대해 완전잉여계가 아니라면 $0 \leq i < j \leq q-1$인 정수 $i$와 $j$에 대해 $p+id \equiv p+jd \pmod{q}$이다. 다시 말해 $(p+id)-(p+jd)$는 $q$의 배수이며, 그럼 $(i-j)d$도 $q$의 배수인데, $q$와 $d$는 앞선 가정에서 서로소이므로 $i-j$가 $q$의 배수여야 한다. 하지만, $i-j \leq q-1$이므로 그럴 수는 없다. 따라서 $p$, $p+d$, $p+2d$ $\cdots$ $p+(q-1)d$가 $q$는 $q$에 대한 완전잉여계이다.

---

모순의 유도

$p$, $p+d$, $p+2d$ $\cdots$ $p+(q-1)d$는 $q$에 대한 완전잉여계이다. 따라서 $0 \leq t \leq q-1$인 정수 $t$에 대해 $q$의 배수인 $p+td$가 존재한다.

1. $p<n$이라면 $p+pd$는 $p$의 배수이며, 따라서 소수가 아니다. 즉, 모순이다.
2. $p \geq n$이라면 $q<n\leq p \leq p+td$이다. 여기서 $p+td$는 $q$보다 큰 $q$의 배수, 즉, 소수가 아니다. 따라서 모순이다.

위의 모든 모순은 $d$가 $q$로 나누어 떨어지지 않아서 $p$, $p+d$, $p+2d$ $\cdots$ $p+(q-1)d$가 $n$보다 작은 어떤 소수 $q$에 대한 완전잉여계가 되어서 발생되는 모순이다. 따라서 증명의 시작에 한 가정에는 모순이 있고, 결국 $d$는 $q$로 나누어 떨어져야 한다.

---

증명의 해석

$n$보다 작은 모든 소수에 대해 상술한 증명을 수행하면 결국 $d$는 $n$보다 작은 모든 소수들의 공배수가 된다. 따라서 다음과 같은 정리가 성립한다.

소수 $p$와 자연수 $d$에 대해 $p$, $p+d$, $p+2d$, $\cdots$, $p+(n-1)d$가 모두 소수일 때 $d$는 $n$ 이하의 모든 소수의 곱과 같다.