원시근 정리 증명

원시근 정리 증명

정의 1

$1 \le a \le p$ 가 $\text{ord}_{p} (a) = p-1$ 를 만족하면 법 $p$ 의 원시근이라 정의한다.


정리

모든 소수 $p$ 는 $\phi ( p - 1)$ 개의 원시근을 갖는다.


설명

$\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} $$ 을 생각해보면

이를 만족시키기 위해선 $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$ 를 이용해 얻은 것이다.


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)$ 개의 원시근을 갖는다.


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p213. ↩︎

댓글