정수론, 그 열두 번째 이야기 | 소수와 등차수열

 

우리는 앞선 글에서 일반적인 소수에 대한 이야기를 다뤘다. 그러나 이 글에서는 "특정한 규칙"의 소수들에 대해 알아보려고 한다. 우선 다음과 같은 간단한 정리를 하나 보자.

 

두 개 이상의 $4n + 1$ 꼴 정수의 곱은 여전히 $4n + 1$ 꼴이다.

 

Proof :

어떤 두 정수 $k, k'$ 에 대해 $k = 4n + 1,\;k' = 4m +1$ 이라 하자. 단, $n, m\in \mathbb{Z}$ 이다. 이 때, $$kk' = \left ( 4n + 1 \right ) \left ( 4m + 1 \right ) = 16nm + 4n + 4m + 1 = 4 \left (4nm + n + m \right ) + 1$$ 이므로 주어진 명제가 증명된다.

 

우리는 위의 정리를 통해 아래의 "특정한 규칙"의 소수의 특징을 하나 찾을 수 있다.

 

$4n + 3$ 꼴 소수는 무한히 많다.

 

Proof :

귀류법을 사용하여, $4n + 3$ 꼴 소수가 유한하게 존재한다고 가정하자. 

그러면 그것들을 $q_1 q_2 \cdots q_s$ 라고 표현할 수 있다.

 

이 때, 정수 $N = 4q_1 q_2 \cdots q_s -1 = 4\left (q_1q_2 \cdots q_s -1 \right) + 3$ 을 생각해보자.

 

이 때 $N > 1$ 이므로 산술의 기본정리에 의해 $N$ 을 나누는 소수 $p$ 가 존재한다.

그런데 $N$ 을 나누는 소수 $p$ 가 모두 $4n +1$ 꼴이라면, 그들을 모두 곱한 $N$ 또한 $4n +1 $ 꼴이어야 한다.

 

즉, $N$ 을 나누는 $4n + 3$ 꼴 소수가 적어도 하나 존재한다. 그것을 $q$ 라고 하자.

 

그런데 $q$ 는 $q_1q_2\cdots q_s$ 중 하나이므로 $q\mid q_1q_2\cdots q_s$ 이고,

$q \mid N$ 이므로, $q \mid \left ( 4 \left (q_1q_2\cdots q_s \right) - N \right ) = 1$ 이 되어 $q \mid 1$ 이므로 모순이다.

 

즉, 처음의 가정이 잘못되었고, $4n + 3$ 꼴 소수는 무한하게 존재한다.

 

 

위의 명제가 증명된 이후에 우리는 "$4n + 1$ 꼴 소수 또한 무한히 많은가" 생각을 해볼 수 있다.

그러나 이것의 증명은 위의 증명에 비해 수학적 도구가 조금 더 필요하므로 차후에 다루기로 한다.

 

하지만 우리가 이 정리를 알고있다면, 저러한 꼴의 소수가 무한한가에 대한 질문은 쉽게 해결할 수 있다.

 

$a, b$ 가 서로소인 자연수라고 하자. 이 때, 다음 수열은 무한히 많은 소수를 포함한다. $$a,\;a+b,\;a+2b,\;a+3b,\;\cdots$$

 

이는 디리클레 정리라고 하는데, 이를 통해 우리는 "특정한 규칙"의 소수에 대해 무한한지를 알 수 있다.

 

이 정리의 증명은 꽤 깊은 수준의 정수론을 요구할 뿐더러 상당히 길이가 있으므로, 

이에 대한 증명은 기회가 된다면 다루도록 하겠다.

 

그러나 우리는 소수가 포함되는 등차수열에 대해 한 가지 성질은 쉽게 알 수 있다.

 

유한개의 합성수만을 포함하는 등차수열은 존재할 수 없다.

 

Proof :

초항이 $a$, 공차가 $b$ 인 등차수열의 모든 항이 소수라고 가정하자.

그러므로 $a + nb = p$ 인 소수 $p$ 가 존재한다. 이제 $k = 1,2,3,\cdots$ 에 대해 $n_k = n + kp$ 라 하자.

$$a + n_k b = a + \left (n + kp\right ) b = \left (a + nb \right ) + kpb = p + kpb = p \left (1 + kb \right )$$ 이므로, 이러한 수열은 항상 무한히 많은 합성수를 포함한다.

 

 

또한, 유한개의 연속한 소수를 포함하는 등차수열에 대해서는 아래와 같은 성질이 존재함을 보일 수 있다.

 

아래와 같은 등차수열의 연속한 $n$ 개 항이 소수라고 하자. (단, $n > 2$ 인 자연수) $$p,\;p+d,\;p+2d,\;\cdots,\;p +\left (n-1\right) d$$     이 수열의 공차 $d$ 는 $n$ 보다 작은 모든 소수로 나누어진다.

 

Proof :

어떤 소수 $q < n$ 에 대해, $q \nmid d$ 라고 가정하고 모순을 이끌어내자.

 

우선, 다음 등차수열 $p,\;p+d,\;p+2d,\;\cdots,\;p+\left (q -1\right) d$ 의 각 항을 $q$ 로 나눈 나머지를 보자.

 

만약 $0\leq j\leq k\leq q-1$ 인 정수 $j, k$ 가 존재하여 $p + jd$ 와 $p + kd$ 가 $q$ 로 나눈 나머지가 같다면,

$q$ 는 그 둘의 차를 나누게 되므로 $q \mid \left (k - j \right ) d$ 인데

$q \nmid d$ 라고 가정하였으므로 $gcd \left ( q, d \right ) = 1$ 이다. 따라서 유클리드 보조정리에 의해 $q \mid \left (k - j \right )$ 이다.

 

그런데 이는 $k - j \leq q -1$ 이고 $j \neq k$ 에서 모순이다.

 

따라서 $p,\;p+d,\;p+2d,\;\cdots,\;p+\left (q -1\right) d$ 를 $q$ 로 나눈 나머지는 $0, 1, 2, \cdots, q-1$ 에 대응된다.

 

그러므로 $0 \leq t \leq q-1$ 인 어떤 정수 $t$ 에 대해 $q \mid p + td$ 가 성립한다.

 

만약 $p < n$ 이라면, 처음 등차수열에는 $p + pd = p \left ( 1 + d \right )$ 가 포함되므로 $p \geq n$ 이다.

그런데 $q < n \leq p \leq p + td$ 이고 $q \mid p + td$ 이므로, $p + td$ 는 합성수이다.

 

따라서 처음의 가정이 모순이 되고 공차 $d$ 는 $n$ 보다 작은 모든 소수로 나누어진다.

 

 

또한 우리는 등차수열 뿐만이 아니라, 어떠한 정수계수 다항식도 소수만을 만들 수 없음을 보일 수 있다.

 

어떤 함수 $f \left(n\right) = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_2 n^2 + a_1 n + a_0$ 가 있을 때,      (단, $a_0, a_1, \cdots, a_k$ 는 정수이고 $a_k \neq 0$)      임의의 자연수 $n$ 에 대해 $f\left(n\right)$ 가 모두 소수가 될 수는 없다.

 

Proof :

어떤 상수 $n_0$ 에 대해, $f\left(n_0\right) = p$ 인 소수 $p$ 가 존재한다.

 

임의의 정수 $t$ 에 대해, 다음과 같은 식을 보자. $$f \left (n_0 + tp\right) = a_k \left(n_0 + tp \right )^k + \cdots + a_1 \left (n_0 + tp \right ) + a_0$$ $$=\left (a_k n_0^k + a_1n_0 + a_0\right) + p Q\left (t \right )$$ $$=f\left (n_0 \right) + p Q \left ( t \right )= p + p Q \left (t \right ) = p \left (1 + Q \left ( t \right ) \right )$$ 여기서 $Q \left (t \right )$ 는 $t$ 에 대한 정수계수 다항식이다. 위의 식에서 $p \mid f \left (n_0 + tp \right )$ 이다.

 

따라서 $f\left (n \right )$ 가 모두 소수이려면 $f\left (n_0 + tp \right ) = p$ 가 성립해야 하는데

$f \left ( n_0 + tp \right ) - p = 0$ 은 $k$ 차 방정식이므로 무한히 많은 근을 가질 수 없다.

 

따라서 이는 모순이고, $f \left ( n \right )$ 가 모두 소수가 될 수는 없다.