원시근 정리 증명
정의 1
$1 \le a \le p$ 가 $\text{ord}_{p} (a) = p-1$ 를 만족하면 법 $p$ 의 원시근이라 정의한다.
- 위수 $\text{ord}_{p} (a) $ 는 $a^{e} \equiv 1 \pmod{p}$ 를 만족하는 가장 작은 자연수 $e$ 를 의미한다.
정리
모든 소수 $p$ 는 $\phi ( p - 1)$ 개의 원시근을 갖는다.
- $\phi$ 는 토션트 함수다.
설명
$\text{ord}_{p} (a) = p-1$ 를 만족하는 $a$ 를 원시근이라고 부르는 이유는 페르마의 소정리에 의해 $a^{p-1} \equiv 1 \pmod{ p }$ 이므로 $\text{ord}_{p} (a) \le p-1$ 임은 보장되어 있는데, 정확히 $\text{ord}_{p} (a) = p-1$ 이라면 $a$ 의 거듭제곱으로 $1$ 과 $p$ 사이의 모든 수를 나타낼 수 있기 때문이다.
예를 들어 $p=7$ 의 원시근 $a = 3$ 을 생각해보면 $$ \begin{align*} 1 \equiv & 3^{0} \pmod{ 7 } \\ 2 \equiv & 3^{2} \pmod{ 7 } \\ 3 \equiv & 3^{1} \pmod{ 7 } \\ 4 \equiv & 3^{4} \pmod{ 7 } \\ 5 \equiv & 3^{5} \pmod{ 7 } \\ 6 \equiv & 3^{3} \pmod{ 7 } \end{align*} $$
이번엔 $a$ 에 초점을 맞춰서 $p=7$ 을 생각해보면 $$ \begin{align*} 1^{1} \equiv & 1 \pmod{ 7 } \\ 2^{3} \equiv & 1 \pmod{ 7 } \\ 3^{6} \equiv & 1 \pmod{ 7 } \\ 4^{3} \equiv & 1 \pmod{ 7 } \\ 5^{6} \equiv & 1 \pmod{ 7 } \\ 6^{2} \equiv & 1 \pmod{ 7 } \end{align*} $$
여기서 $p=7$ 의 원시근은 $3,5$ 두 개로, $$ \phi (7-1) = \phi (6) = \phi (3) \phi (2) = (3-1)(2-1) = 2 $$ 와 같이 정확하게 맞아떨어짐을 확인할 수 있다. 한편 $\phi ( p - 1)$ 는 아무리 작아도 $1$ 이기 때문에, 정확한 갯수가 아니라 존재성만을 언급하는데에 써도 상관 없다. 이 토션트 함수 $\phi$ 는 갑자기 등장한 것 같아 보이겠지만 증명 과정에서 없어서는 안 될 핵심 요소다.
증명
Part 1.
위수의 성질에 따라 모든 $1 \le a \le (p-1)$ 에 대해 $\text{ord}_{p} (a) \mid (p-1)$이제 $(p-1)$ 을 나누는 모든 약수 $d$ 에 대해 함수 $\psi$ 를 $$ \psi ( d ) := \left| \left\{ a \ | \ 1 \le a < p \land \text{ord}_{p} (a) = d \right\} \right| $$ 와 같이 정의하자. 우리는 Part 4에서 이 $\psi$ 가 토션트 함수 $\phi$ 와 사실상 같은 함수임을 보일 것이다.
Part 2.
$(p-1)$ 을 나누는 약수를 $n$ 이라고 두면 $(p-1) = nk$ 이고, $\left( X^{p-1} - 1 \right)$ 을 인수분해하면
$$ \begin{align*} X^{p-1} - 1 =& X^{nk} - 1 \\ =& \left( X^{n} \right)^{k} - 1 \\ =& \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \end{align*} $$
이다. 페르마의 소정리에 의해 $$ X^{p-1} - 1 \equiv 0 \pmod{p} $$ 은 $X=1,2,\cdots,(p-1)$ 를 근으로 가지고, 합동방정식에 대한 대수학의 기본정리에 의해 $X^{n} -1 \equiv 0 \pmod{p}$ 은 많아도 $n$ 개의 근를 가지므로 $$ \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \equiv 0 \pmod{p} $$ 은 많아도 $n(k-1)$ 개의 근을 갖는다. 여기서 다시 한 번 $$ X^{p-1} - 1 \equiv \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \pmod{p} $$ 을 생각해보면
- 좌변에는 정확히 $(p-1) = nk$ 개의 근이 있고
- 우변에는 많아도 $n$ 개의 근과 많아도 $n(k-1)$ 개의 근이 존재한다.
이를 만족시키기 위해선 $X^{n} -1 \equiv 0 \pmod{p}$ 은 적어도 $n$ 개, 그러니까 정확히 $n$ 개의 근을 가져야한다. 요약해서, $n | (p-1)$ 이면 $$ X^{n} -1 \equiv 0 \pmod{p} $$ 은 $0 \le X < p$ 에서 정확히 $n$ 개의 해를 갖는다.
Part 3. $\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$
$n$ 의 모든 약수를 $d_{1} , \cdots , d_{r}$ 라고 나타내보자.
$n$ 의 약수 $d$ 가 $d = \text{ord}_{p} (a)$ 를 만족하면 위수의 정의에서 $$ a^{d} = a^{\text{ord}_{p} (a)} \equiv 1 \pmod{p} $$ 이다. 여기서 주어진 $d$ 에 대해 위 식을 만족시키는 $a$ 의 갯수는 $\psi (d)$ 가 된다.
그런데 $\displaystyle n = d \cdot \left( {{n} \over {d}} \right)$ 이므로, $$ a^{n} \equiv a^{d \cdot \left( {{n} \over {d}} \right)} \equiv 1^{ \left( {{n} \over {d}} \right)} \equiv 1 \pmod{p} $$ 이다. 즉 $\psi (d)$ 개의 $X = a$ 는 $X^{n} -1 \equiv 0 \pmod{p}$ 의 해가 된다.
정리하면 $X^{n} -1 \equiv 0 \pmod{p}$ 의 해의 갯수는 $$ \sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} ) $$ 과 같다. 위의 Part 2에서 $X^{n} -1 \equiv 0 \pmod{p}$ 의 해의 갯수가 $n$ 이라고 했으므로 $$ \sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} ) = n $$ 이고, 이는 토션트 합 공식과 유사하다.
Part 4. $\phi (n) = \psi (n)$
모든 자연수 $n$ 에 대해서 $\phi (n) = \psi (n)$ 이 성립함을 보이면 된다.
$\psi$ 에 대한 계산은 별다른 언급이 없는 한 $\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$ 를 이용해 얻은 것이다.
- Case 1. $n=1$
$\phi (1) = 1$ 이고 $\psi (1) = 1$ 이므로 $$\phi (1) = \psi (1)$$ - Case 2. 소수 $q$ 에 대해 $n=q$
$\phi (q) = q - 1$ 이고 $\psi (q) + \psi (1) = q$ 이므로 $$\phi (q) = q - 1 = \psi (q)$$ - Case 3. 소수 $q$ 에 대해 $n=q^2$
$q^2$ 의 약수는 $1, q, q^2$ 뿐이므로 $$\phi (q^2) + \phi (q) + 1 = q^{2} = \psi (q^2) + \psi (q) + 1$$ 이다. 양변에서 Case 1, 2의 결과대로 항을 소거하면 $$\phi (q^2) = \psi (q^2)$$ - Case 4. 서로 다른 소수 $q_{1}, q_{2}$ 에 대해 $n=q_{1} q_{2}$
$q_{1} q_{2}$ 의 약수는 $1, q_{1}, q_{2}, q_{1} q_{2}$ 뿐이므로 $$\phi ( q_{1} q_{2}) + \phi (q_{1}) + \phi (q_{2}) + 1 = q_{1} q_{2} = \psi ( q_{1} q_{2}) + \psi (q_{1} ) + \psi (q_{2} ) + 1$$ 이다. 양변에서 Case 1, 2의 결과대로 항을 소거하면 $$\phi ( q_{1} q_{2} ) = \psi ( q_{1} q_{2} )$$ - Otherwise.
그 외의 경우엔 Case 3, 4의 결과대로 항을 하나하나 쪼개면 $\phi (n) = \psi (n)$ 를 얻는다.
Part 5.
위의 Part 2, 3에서 우리는 $n | (p-1)$ 인 모든 $n$ 에 대해 $\text{ord}_{p} (a) = n$ 을 만족하는 $a$ 가 $\phi (n)$ 개만큼 존재함을 확인했다. 여기서 $k=1$, 즉 $n = p-1$ 이라고 하면 $\text{ord}_{p} (a) = p-1$ 이므로 $a$ 는 법 $p$ 의 원시근이 된다. 따라서 소수 $p$ 는 $\phi (p-1)$ 개의 원시근을 갖는다.
■
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p213. ↩︎