소수(Prime number)

정의1

임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해

$p / n \in \mathbb{Z}$이면 $n = 1$ 또는 $n = p$가 되는 $p \ge 2$인 양의 정수 $p \in \mathbb{Z}^+$를 소수로 정의한다.

소수가 아니고 $1$보다 큰 양의 정수를 합성수(composite number)로 정의한다.

 

 

 

정리1

$p \in \mathbb{Z}^+$가 소수일때 임의의 정수 $a, b \in \mathbb{Z}$에 대해 $(a\cdot b) / p \in \mathbb{Z}$이면 $a / p \in \mathbb{Z}$이거나 $b / p \in \mathbb{Z}$이다.

증명

$(a\cdot b) / p \in \mathbb{Z}$일때 $a / p \notin \mathbb{Z}$이고 $b / p \notin \mathbb{Z}$라 가정하면

$p$가 소수이므로 $p / d \in \mathbb{Z}$인 양의 정수 $d \in \mathbb{Z}^+$은 $d = 1$이거나 $d = p$인데

$a / p \notin \mathbb{Z}$이므로 $\gcd(a,p)$ $ = 1$이고 유클리드 보조정리로 $b / p \in \mathbb{Z}$가 되어 모순이다.

따라서 $(a\cdot b) / p \in \mathbb{Z}$이면 $a / p \in \mathbb{Z}$이거나 $b / p \in \mathbb{Z}$이다.

 

 

 

정리2

$p \in \mathbb{Z}^+$가 소수일때 다음이 성립한다.

1. 임의의 정수 $a_1, a_2, \cdots, a_n \in \mathbb{Z}$에 대해

$(a_1\cdot a_2 \cdot \; \cdots \; \cdot a_n ) / p\in \mathbb{Z}$이면 $a_m / p\in \mathbb{Z}$가 되는 $m = 1,2,\cdots, n$이 존재한다.

2. 임의의 소수 $q_1, q_2, \cdots , q_n \in \mathbb{Z}^+$에 대해

$(q_1\cdot q_2 \cdot \; \cdots \; \cdot q_n ) / p\in \mathbb{Z}$이면 $p = q_m$가 되는 $m = 1,2,\cdots, n$이 존재한다.

3. $q \in \mathbb{Z}^+$가 $p \ne q$인 소수이면 $\gcd(p,q)$ $ = 1$이다.

증명

1.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일때는 자명하게 성립한다.

모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립한다고 가정하고

임의의 정수 $a_1, a_2, \cdots, a_k, a_{k+1} \in \mathbb{Z}$에 대해 $(a_1\cdot a_2 \cdot \; \cdots \; \cdot a_k \cdot a_{k+1} ) / p\in \mathbb{Z}$이면

위 정리로 $(a_1\cdot a_2 \cdot \; \cdots \; \cdot a_k ) / p\in \mathbb{Z}$이거나 $a_{k+1}/ p\in \mathbb{Z}$이다.

따라서 $a_{k+1}/ p\in \mathbb{Z}$이면 정리가 성립하고 $ a_{k+1}/ p \notin \mathbb{Z}$이면 $(a_1\cdot a_2 \cdot \; \cdots \; \cdot a_k ) / p\in \mathbb{Z}$이므로

귀납가정으로 $a_i / p\in \mathbb{Z}$인 $i = 1,2,\cdots, k$가 존재하여 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

2.

1번으로 $q_m / p\in \mathbb{Z}$인 $m = 1,2,\cdots, n$이 존재하고 $q_m$이 소수이므로 $p = 1$ 또는 $p = q_m$인데

$p$가 소수이므로 $p \ne 1$이 되어 $p = q_m$이다.

3.

$\gcd(p,q) = d \in \mathbb{Z}^+$이면

$p / d \in \mathbb{Z}$와 $q / d \in \mathbb{Z}$가 성립하고 $p,q \in \mathbb{Z}^+$가 소수이므로 $d = 1$ 또는 $d = p$ 또는 $d = q$이다.

$d = p$이면 $q / p \in \mathbb{Z}$이고 2번으로 $p = q$가 되어 모순이고

$d = q$일때도 $p / q \in \mathbb{Z}$이고 2번으로 $q = p$가 되어 모순이므로 $d = 1$이다.

 

 

 

정리3(산술의 기본정리)

$n \ge 2$인 모든 양의 정수 $n \in \mathbb{Z}^+$에 대해 다음이 성립한다.

1. $n = p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r$이 되는 $r \in \mathbb{Z}^+$개의

$p_1 \le p_2 \le \cdots \le p_r$인 중복가능한 소수 $p_1, p_2,\cdots, p_r \in \mathbb{Z}^+$이 유일하게 존재한다.

2. $n = p_1^{m_1} \cdot p_2^{m_2} \cdot \; \cdots \; \cdot p_k^{m_k}$가 되는 $k \in \mathbb{Z}^+$개의

$p_1 < p_2 <\cdots < p_k$인 소수 $p_1, p_2,\cdots, p_k \in \mathbb{Z}^+$와 중복가능한 $m_1, m_2,\cdots, m_k \in \mathbb{Z}^+$가 유일하게 존재한다.

증명

1.

존재성

$n$이 소수이면 $n = n$이므로 정리가 성립한다.

$n$이 소수가 아니면 

$n / d\in \mathbb{Z}$가 성립하는 $d\ne 1$이고 $d \ne n$인 $d \in \mathbb{Z}^+$가 존재하므로 약수 정리로 $2 \le d \le n -1$이 되어

$d$들의 집합에 대한 정렬성으로 $n/ p_1\in \mathbb{Z}$이고 $2 \le p_1 \le n -1$인 최소 양의 정수 $p_1 \in \mathbb{Z}^+$이 존재한다.

또 $n / p_1\in \mathbb{Z}$이므로 $n = p_1\cdot n_1$이 되는 $n_1 \in \mathbb{Z}^+$이 존재하고 

$p_1$이 소수가 아니라고 가정하면

$p_1 / d_1\in \mathbb{Z}$이 성립하는 $d_1 \ne 1$이고 $d_1 \ne p_1$인 $d_1 \in \mathbb{Z}^+$이 존재하여 약수 정리로 $d_1 < p_1$이고

$n = p_1 \cdot n_1 = d_1 \cdot q \cdot n_1$이 되는 $q \in \mathbb{Z}^+$가 존재하여 $n / d_1\in \mathbb{Z}$인데

$p_1$이 최소라는 가정에 모순이므로 $p_1$은 소수이다.

$n /p_1 \in \mathbb{Z}$인 소수 $p_1$에 대해 $n = p_1\cdot n_1$이므로 $n / n_1\in \mathbb{Z}$이고 약수 정리로 $n_1 \le n$이 되어

$n_1 = 1$이면 $n = p_1 \cdot n_1 = p_1 \cdot 1 = p_1$로 정리가 성립하고

$n_1 \ne 1$일때 $n = n_1$이라 가정하면

$p_1 > 1$이므로 $n = p_1 \cdot n_1 > 1\cdot n_1 = n$이 되어 모순이므로 $2 \le n_1 \le n-1$이다.

또 $n_1 / p_2\in \mathbb{Z}$인 가장 작은 $p_2 \in \mathbb{Z}^+$가 소수이면 $n_1 = p_2 \cdot n_2$이고 $n_2<n_1<n$인 $n_2 \in \mathbb{Z}^+$가 존재하여

$p_2 < p_1$이면 $n = p_1 \cdot n_1 = p_1 \cdot p_2 \cdot n_2$로 $n / p_2\in \mathbb{Z}$인데

$p_1$이 최소라 가정하였으므로 모순이 되어 $p_1\le p_2$이다.

다시 $n_2 = 1$이면 정리가 성립하고 $n_2 \ne 1$이면 위와 같은 과정을 반복하여 무한강하법에 모순이 되지 않도록

$1 = n_r < \cdots < n_2 < n_1 < n$인 $r \in \mathbb{Z}^+$이 존재하므로 $n = p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r \cdot n_{r} = p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r$이 되는

$r$개의 $p_1 \le p_2 \le \cdots \le p_r$인 소수 $p_1, p_2,\cdots, p_r \in \mathbb{Z}^+$가 존재한다.

유일성

$p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r = n = q_1 \cdot q_2 \cdot \; \cdots \; \cdot q_s$가 되는 $s$개의 $q_1 \le q_2 \le \cdots \le q_s$인 소수 $q_1, q_2,\cdots, q_s \in \mathbb{Z}^+$가 존재할때

일반성을 잃지 않고 $r\le s$라 가정하면

$( q_1 \cdot q_2 \cdot \; \cdots \; \cdot q_s) / p_1\in \mathbb{Z}$이므로 위 정리로 $p_1 = q_i$인 $i= 1,2,\cdots, s$이 존재하여 $q_1 \le q_i = p_1$이고

$(p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r )/ q_1 \in \mathbb{Z}$이므로 위 정리로 $q_1 = p_j$인 $j = 1,2,\cdots, r$가 존재하여 $p_1 \le p_j = q_1$이므로

$p_1 = q_1$이다.

비슷하게 $ p_2 \cdot \; \cdots \; \cdot p_r =  q_2 \cdot \; \cdots \; \cdot q_s$에 대해 $p_2 =q_2 $이고 위와 같은 과정을 반복할때

$r < s$라 가정하면 모든 $j = 1,2,\cdots, r$에 대해 $p_j = q_j$이고

$1 = q_{r+1}\cdot q_{r+2} \cdot \; \cdots \; \cdot q_s$이 되어 모든 $i= r+1,r+2,\cdots, s$에 대해 $1/ q_i\in \mathbb{Z}$이므로 약수 정리로 $q_i = 1$인데

$q_{r+1}, q_{r+2},\cdots , q_s \in \mathbb{Z}^+$는 소수이므로 모순이 되어 $r = s$이고 모든 $j = 1,2,\cdots, r$에 대해 $p_j = q_j$이다.

따라서 $n = p_1 \cdot p_2 \cdot \; \cdots \; \cdot p_r$이 되는 $p_1 \le p_2 \le \cdots \le p_r$인 소수 $p_1, p_2,\cdots, p_r \in \mathbb{Z}^+$은 유일하다.

2.

1번의 서로 같은 소수들을 모두 거듭제곱으로 표현하면 정리가 성립한다.

 

 

 

정리4

모든 소수들의 집합은 가산인 무한집합이다.

증명

모든 소수들의 집합이 $P$일때

소수는 모두 자연수이므로 $P \subseteq \mathbb{N}$이고 가산집합 정리로 가산이다.

$P$가 유한집합이라 가정할때 $n \in \mathbb{Z}^+$개의 원소가 존재하므로

모든 $i = 1,2,\cdots , n$에 대해 $p_i < p_{i+1}$가 되도록 $p_1 = 2, p_2 = 3, p_3 = 5, p_4= 7 ,\cdots, p_n \in P$을 정의하면

최소원소, 최대원소 정리로 $\min P = p_1$과 $\max P = p_n$이 존재하여

$p = p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n + 1$는 $\max P = p_n < p$이므로 $p \notin P$이다.

$p$는 소수가 아니고 소수는 $p_1 , p_2 ,\cdots, p_n \in P$뿐이므로 위 정리로 $p / p_i\in \mathbb{Z}$인 $i = 1,2,\cdots, n$가 존재하여

$p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n = p_i \cdot q_1$이고 $p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n + 1 =p = p_i \cdot q_2$인 $q_1, q_2 \in \mathbb{Z}^+$가 존재하는데

$ 1= p - p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n = p_i \cdot q_2 - p_i \cdot q_1 = p_i \cdot (q_2 - q_1)$이 되어 

$1/ p_i\in \mathbb{Z}$이고 약수 정리로 $p_i = 1 < 2= p_1 = \min P$이므로 모순이다.

따라서 $P$는 무한집합이다.

 

 

 

정리5

순증가하는 소수열 $(p_n)_{n=1}^\infty$에 대해 $P = \{ p_n : n \in \mathbb{Z}^+ \}$가 모든 소수들의 집합일때 다음이 성립한다.

1. 모든 $n \in \mathbb{Z}^+$에 대해 $p_n < p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n + 1$이다.

2. $n \ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 $p_n \le p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} + 1$이다.

3. 모든 $n \in \mathbb{Z}^+$에 대해 $p_n \le 2^{2^{n-1}}$이다.

증명

1.

모든 $n \in \mathbb{Z}^+$에 대해 $ 2= p_1 < p_2 < \cdots < p_n$이므로 $p_n \le p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n < p_1\cdot p_2 \cdot \; \cdots \; \cdot p_n + 1$이다.

2.

$1\le n -1 $인 모든 $n \in \mathbb{Z}^+$에 대해 $2 = p_1 \le p_{n-1} < p_{n-1} +1 \le p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} + 1$이므로

위 정리로 $(p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} +1 ) / p_{k}\in \mathbb{Z}$가 되는 $k \in \mathbb{Z}^+$가 존재한다.

$k < n$이라 가정하면

$p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} +1  = p_k\cdot q_1$인 양의 정수 $q_1 \in \mathbb{Z}^+$가 존재하고

$p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1}  = p_k\cdot q_2$인 양의 정수 $q_2 \in \mathbb{Z}^+$가 존재하므로

$1 = p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} +1  - p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1}  = p_k\cdot (q_1-q_2)$가 되어 $1/p_k \in \mathbb{Z}$인데

$1/p_k \in \mathbb{Z}$이면 약수 정리로 $p_k = 1$이 되어 모순이다.

따라서 $(p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} +1 ) / p_{k}\in \mathbb{Z}$인 $k \in \mathbb{Z}^+$는 $n \le k$이고

$(p_n)$은 증가하므로 약수 정리로 $p_n\le p_k  \le p_1\cdot p_2 \cdot \; \cdots \; \cdot p_{n-1} + 1$이다.

3.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일때 $p_1 = 2 = 2^1 = 2^{2^0} =  2^{2^{1 - 1}} $이므로 성립한다.

모든 $k \in \mathbb{Z}^+$에 대해 $p_k \le 2^{2^{k-1}}$이라 가정하면

$2\le k+1$이므로 2번과 귀납가정으로

$\begin{align*} p_{k+1}  \le p_1\cdot p_2 \cdot \; \cdots \; \cdot p_k +1  \le 2^{2^0}\cdot 2^{2^1}\cdot \; \cdots \; \cdot 2^{2^{k-1}} +1 = 2^{2^0 + 2^1 + \cdots + 2^{k-1}} +1 \end{align*}$이고

급수정리로 $2^0 + 2^1 + \cdots + 2^{k-1} = \dfrac{1 - 2^k}{1 - 2} = 2^k -1$이므로 $p_{k+1} \le 2^{2^{(k +1)-1}}$이다.

따라서 모든 $n \in \mathbb{Z}^+$에 대해 $p_n \le 2^{2^{n-1}}$이다.

 

 

 

정리6(페르마[Fermat]의 소정리)

임의의 정수 $a \in \mathbb{Z}$와 $a / p\notin \mathbb{Z}$인 임의의 소수 $p \in \mathbb{Z}^+$에 대해 $a^{p-1} \equiv 1 \pmod{p}$이다.

증명

$p$를 나누는 수는 $1$과 $p$뿐이므로 $a / p\notin \mathbb{Z}$이면

$a/d \in \mathbb{Z}$이고 $p/d \in \mathbb{Z}$인 $d \in \mathbb{Z}^+$는 $d = 1$이 되어 $\gcd(a,p)$ $= 1$이다.

$r\cdot a \equiv s\cdot a \pmod{p}$이고 $r\ne s$인 $r,s = 1,2,\cdots, p-1$가 존재한다고 가정하면

$\dfrac{p}{\gcd(a,p)} = p$에 대해 모듈로합동 정리로 $r \equiv s \pmod{p}$가 되어 모순이므로

$r\ne s$인 모든 $r,s = 1,2,\cdots, p-1$에 대해 $r\cdot a \not \equiv s\cdot a \pmod{p}$이다.

또 $r\cdot a \equiv 0 \pmod{p}$인 $r = 1,2,\cdots, p-1$이 존재한다고 가정하면

$\dfrac{p}{\gcd(a,p)} = p$에 대해 모듈로합동 정리로 $r \equiv 0 \pmod{p}$이 되어 모순이므로

모든 $r = 1,2,\cdots, p-1$에 대해 $r\cdot a \not \equiv 0 \pmod{p}$이다.

따라서 $r\ne s$인 모든 $r,s = 1,2,\cdots, p-1$에 대해

$r\cdot a \equiv i \pmod{p}$이고 $s \cdot a \equiv j \pmod{p}$인 $i,j = 1,2,\cdots, p-1$가 존재하고 $i\ne j$이므로

곱셈 정리로 $a\cdot 2a \cdot 3a \cdot \;\cdots \; \cdot (p-1)a \equiv 1\cdot 2\cdot 3 \cdot  \; \cdots \; \cdot (p-1) \pmod{p}$이 되어

$a^{p-1} \cdot $ $ (p-1)!$ $ \equiv (p-1)! \pmod{p}$이다.

또 $\gcd(1,p) = 1$이고 $\gcd(2,p) = 1$이고 $\cdots$ $\gcd(p-1,p) = 1$이므로 서로소 정리로 $\gcd((p-1)!, p) = 1$이 되어

$\dfrac{p}{\gcd((p-1)!,p)} = p$에 대해 모듈로합동 정리로 $a^{p-1} \equiv 1 \pmod{p}$이다.

 

 

 

정리7

임의의 정수 $a \in \mathbb{Z}$와 임의의 소수 $p \in \mathbb{Z}^+$에 대해 $a^{p} \equiv a \pmod{p}$이다.

증명

$a / p \in \mathbb{Z}$이면

$a \equiv 0 \pmod{p}$이므로 모듈로합동 정리로 $a^p \equiv 0^p \pmod{p}$이고 $a^p \equiv a \pmod{p}$이다.

$a / p\notin \mathbb{Z}$이면

페르마의 소정리로 $a^{p-1} \equiv 1 \pmod{p}$이므로 곱셈 정리로 $a^{p} \equiv a \pmod{p}$이다.

 

 

 

정리8

$p\ne q$인 임의의 소수 $p,q \in \mathbb{Z}^+$와 임의의 정수 $a \in \mathbb{Z}$에 대해

$a^{p} \equiv a \pmod{q}$이고 $a^{q} \equiv a \pmod{p}$이면 $a^{p\cdot q} \equiv a \pmod{p\cdot q}$이다.

증명

$a^{q} \equiv a \pmod{p}$이고 $a^q$에 대해 위 정리로 $(a^{q})^p \equiv a^q \pmod{p}$이므로 

$a^{p\cdot q} \equiv a \pmod{p}$가 되어 $(a^{p\cdot q} - a)/ p \in \mathbb{Z}$이다.

또 $a^{p} \equiv a \pmod{q}$이고 $a^p$에 대해 위 정리로 $(a^{p})^q \equiv a^p \pmod{q}$이므로 

$a^{p\cdot q} \equiv a \pmod{q}$가 되어 $(a^{p\cdot q} - a)/ q \in \mathbb{Z}$이다.

따라서 $\gcd(p, q)$ $= 1$이므로 약수 정리로 $(a^{p\cdot q} - a)/ (p\cdot q) \in \mathbb{Z}$가 되어 $a^{p\cdot q} \equiv a \pmod{p\cdot q}$이다.

 

 

 

정리9

임의의 소수 $p \in \mathbb{Z}^+$와 $1\le a \le p-1$인 임의의 양의 정수 $a \in \mathbb{Z}^+$에 대해

$a^2 \equiv 1 \pmod{p}$이기 위한 필요충분조건은 $a = 1$이거나 $a = p - 1$인 것이다.

증명

$a = 1$이거나 $a = p - 1$이면

$a = 1$일때 $a^2 = 1$이고 $a = p-1$일때 $(p-1)^2 = p^2 - 2\cdot p + 1$이므로 $a^2 \equiv 1 \pmod{p}$이다.

역으로 $a^2 \equiv 1 \pmod{p}$이면

$(a-1)\cdot (a+1) = a^2 - 1= p\cdot q$인 $q \in \mathbb{Z}$가 존재하므로 $2\le a \le p-2$라 가정할때

$1\le a -1 \le p-3$이고 $3\le a +1 \le p-1$이므로 $\gcd(a-1, p)$ $ = 1 = \gcd(a+1, p)$가 되어

$(a-1)\cdot (a+1) \equiv 0 \pmod{p}$은

$\dfrac{p}{\gcd(a -1,p)} = p$에 대해 모듈로합동 정리로 $a+1 \equiv 0 \pmod{p}$이므로 모순이고

$\dfrac{p}{\gcd(a +1,p)} = p$에 대해 모듈로합동 정리로 $a-1 \equiv 0 \pmod{p}$이므로 모순이다.

따라서 $a = 1$이거나 $a = p - 1$이다.

 

 

 

정리10

$p > 2$인 임의의 소수 $p \in \mathbb{Z}^+$는 홀수이다.

증명

$p$가 짝수이면 $p / 2 \in \mathbb{Z}$이므로 소수임에 모순이 되어 $p$는 홀수이다.

 

 

 

정리11(윌슨[Wilson] 정리)

$p \ge 2$인 양의 정수 $p \in \mathbb{Z}^+$가 소수이기 위한 필요충분조건은 $(p-1)!$ $\equiv$ $ -1 \pmod{p}$인 것이다.

증명

$p \in \mathbb{Z}^+$가 소수일때

$p = 2$이면 $(2 -1)! - (-1) = 1 + 1 = 2 = 1\cdot 2$이므로 $(2-1)! \equiv -1 \pmod{2}$이다.

$p = 3$이면 $(3 -1)! - (-1) = 2 + 1 = 3 = 1\cdot 3$이므로 $(3 -1)! \equiv -1 \pmod{3}$이다.

$p > 3$이면 $p \ge 5$이고

임의의 $a = 1,2,3, \cdots, p-1$에 대해 $\gcd(a, p)$ $ = 1$이므로

선형합동 정리로 $a\cdot x \equiv 1 \pmod{p}$인 $x \in \mathbb{Z}$가 존재하고

$a\cdot x_0 \equiv 1 \pmod{p}$인 모든 $x_0 \in \mathbb{Z}$에 대해 $x \equiv x_0 \pmod{p}$이다.

또 $x \equiv 0 \pmod{p}$이면 $a\cdot x \equiv 0 \pmod{p}$이 되어 모순이므로

$a\cdot x \equiv 1 \pmod{p}$인 $x = 1,2,3, \cdots, p-1$가 존재한다.

$a \ne \overline{a}$인 $\overline{a} = 1,2,3, \cdots, p-1$에 대해 $\overline{a}\cdot \overline{x} \equiv 1 \pmod{p}$인 $\overline{x} = 1,2,3, \cdots, p-1$가 존재할때 $\overline{x} = x$라 가정하면

$\gcd(x,p) = 1$이므로 $\dfrac{p}{\gcd(x,p)} = p$에 대해 모듈로합동 정리로 $a \equiv \overline{a} \pmod{p}$가 되어 모순이므로

$a \ne \overline{a}$이면 $x \ne \overline{x}$이다.

또 위 정리로 $a = x$이기 위한 필요충분조건은 $a = 1$이거나 $a = p - 1$이므로

$a = 2,3, \cdots, p-2$이면 $x = 2,3, \cdots, p-2$이고 $a\ne x$이다.

$\{2,3, \cdots, p-2 \}$의 원소개수 $p-3$은 위 정리와 홀짝정리로 짝수이므로 $m =\dfrac{p-3}{2}$은 양의 정수가 되어

$a_1\cdot x_1 \equiv 1 \pmod{p}$이고 $a_2\cdot x_2 \equiv 1 \pmod{p}$이고 $\cdots$ $a_m \cdot x_m \equiv 1 \pmod{p}$인

$\{2,3, \cdots, p-2 \} = \{ a_1, x_1, a_2, x_2,\cdots, a_m, x_m \}$이 존재한다.

따라서 $(p-2)! = 2\cdot 3 \cdot \; \cdots \; \cdot (p -2) = a_1\cdot x_1 \cdot a_2\cdot x_2 \cdot \; \cdots \; \cdot a_m\cdot x_m$이므로

모듈러합동 정리로 $(p-2)! \equiv 1 \pmod{p}$이고 $p -1 \equiv -1 \pmod{p}$이므로 $(p-1)! \equiv -1 \pmod{p}$이다.

 

역으로 $(p-1)! \equiv -1 \pmod{p}$이고 $p \ge 2$인 $p \in \mathbb{Z}^+$가 존재할때 $p$가 소수가 아니라고 가정하면

$p / d \in \mathbb{Z}$이고 $d \ne 1$와 $d \ne p$를 만족하는 $d \in \mathbb{Z}^+$가 존재하여 약수 정리로 $2\le d \le p-1$이고

$(p-1)! = 2\cdot 3 \cdot \; \cdots \; \cdot (p-1)$이므로 $(p-1)! / d \in \mathbb{Z}$가 되어 $(p-1)! = d\cdot q_1$인 $q_1 \in \mathbb{Z}^+$이 존재한다.

또 $(p-1)! \equiv -1 \pmod{p}$이므로 $((p-1)! + 1) / p \in \mathbb{Z}$이고

$p / d \in \mathbb{Z}$이므로 약수 정리로 $((p-1)! + 1) / d \in \mathbb{Z}$가 되어 $(p-1)! +1= d\cdot q_2$인 $q_2 \in \mathbb{Z}^+$가 존재하는데

$1 = (p-1)! +1 - (p-1)! = d\cdot (q_2 - q_1)$이므로 $1/d \in \mathbb{Z}$이고 약수 정리로 $d = 1$이 되어 모순이다.

따라서 $(p-1)! \equiv -1 \pmod{p}$이고 $p \ge 2$인 $p \in \mathbb{Z}^+$는 소수이다.

 

 

 

정리12

$p > 2$인 소수 $p \in \mathbb{Z}^+$에 대해

$x^2 + 1 \equiv 0 \pmod{p}$인 $x \in \mathbb{Z}$가 존재하기 위한 필요충분조건은 $p \equiv 1 \pmod{4}$인 것이다.

증명

$x^2 + 1 \equiv 0 \pmod{p}$인 $x \in \mathbb{Z}$가 존재할때

$x^2 \equiv -1 \pmod{p} $이고 $x / p \in \mathbb{Z}$이면 $x \equiv 0 \pmod{p}$이므로 $x^2 \equiv 0 \pmod{p}$으로 모순이 되어

$x / p \notin \mathbb{Z}$이고 $p$가 소수이므로 페르마의 소정리로 $x^{p-1} = 1\pmod{p}$이다.

$p > 2$이므로 위 정리와 홀짝정리로 $p -1$은 짝수이므로 $\dfrac{p-1}{2}$는 양의 정수가 되어

모듈러합동 정리로 $(x^{2})^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}} \pmod{p}$이고

$\dfrac{p-1}{2}$가 홀수이면 $\begin{align*} 1 & \equiv x^{p-1} \pmod{p} \\ & \equiv (x^2)^\frac{p-1}{2} \pmod{p} \\ & \equiv (-1)^\frac{p-1}{2} \pmod{p}  \end{align*}$ 이므로  $1 \equiv -1 \pmod{p}$이 되어 $(1-(-1))/p \in \mathbb{Z}$이고

약수 정리로 $p \le2$이므로 $p > 2$에 모순이다.

따라서 $\dfrac{p-1}{2}$는 짝수이고 $\dfrac{p-1}{2} = 2\cdot k$인 $k \in \mathbb{Z}^+$가 존재하여 $p -1 = 4\cdot k $이므로 $p \equiv 1 \pmod{4}$이다.

역으로 $p \equiv 1 \pmod{4}$이면

$p -1 = 4\cdot k $인 $k \in \mathbb{Z}^+$가 존재하므로 $\dfrac{p-1}{2} = 2\cdot k$이고 $p+1 = 4\cdot k +2 = 2\cdot (2\cdot k+1)$이 되어

$\dfrac{p+1}{2} = 2\cdot k +1 = \dfrac{p-1}{2} +1$이고 $p - \dfrac{p-1}{2} = \dfrac{2\cdot p - p +1}{2} = \dfrac{p+1}{2}$이므로

$\begin{align*} (p-1)! & = 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2}\cdot \left (\frac{p-1}{2} +1 \right )\cdot \;\cdots \; \cdot (p-2)\cdot (p-1) \\[0.5em] & = 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2}\cdot \frac{p+1}{2} \cdot \;\cdots \; \cdot (p-2)\cdot (p-1) \\[0.5em] & = 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2}\cdot \left ( p - \frac{p-1}{2} \right ) \cdot \;\cdots \; \cdot (p-2)\cdot (p-1) \text{ 이다.} \end{align*}$

따라서 $p - 1 \equiv -1 \pmod{p}$이고 $p - 2 \equiv -2 \pmod{p}$이고 $\cdots$ $p - \dfrac{p-1}{2} \equiv -\dfrac{p-1}{2} \pmod{p}$이므로

$\begin{align*} (p-1)! & \equiv 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2}\cdot \left ( p -\frac{p-1}{2} \right) \cdot \;\cdots \; \cdot (p-2)\cdot (p-1) \pmod{p} \\[0.5em] & \equiv 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2}\cdot \left( -\frac{p-1}{2} \right) \cdot \;\cdots \; \cdot (-2)\cdot (-1) \pmod{p} \\[0.5em] & \equiv (-1)^\frac{p-1}{2} \cdot \left ( 1\cdot 2 \cdot \; \cdots \; \cdot \frac{p-1}{2} \right )^2 \pmod{p} \\[0.5em] & \equiv (-1)^\frac{p-1}{2}\cdot \left ( \left ( \frac{p-1}{2} \right )! \right )^2 \pmod{p} \text{ 이고} \end{align*}$

윌슨정리로 $(p-1)! \equiv -1 \pmod{p}$이므로 $ -1 \equiv (-1)^\frac{p-1}{2}\cdot \left ( \left ( \dfrac{p-1}{2} \right )! \right )^2 \pmod{p} $가 되어

$\dfrac{p-1}{2} = 2\cdot k$가 짝수임에 따라 $\left ( \left ( \dfrac{p-1}{2} \right )! \right )^2 +1 \equiv 0 \pmod{p} $이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/54#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/54#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

David M. Burton - Elementary Number Theory - 9780073383149