9. 원시근

9. 원시근

$n>1$, $\text{gcd}(a,\,n)=1$이라 하자. 법 $n$에 대한 $a$의 위수(order)를 $a^{r}\equiv1\,(\text{mod}\,n)$을 만족하는 가장 작은 $r\in\mathbb{N}$으로 정의한다.

참고: 오일러 정리에 의해 $n\geq1$이고 $\text{gcd}(a,\,n)=1$이면, $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이 성립한다.

법 $7$에 대한 $2$의 위수를 구하자. $$2^{1}\equiv2,\,2^{2}\equiv4,\,2^{3}\equiv1\,(\text{mod}\,7)$$ 이고, 오일러 정리에 의해 $2^{\phi(7)}=2^{6}\equiv1\,(\text{mod}\,7)$이다. 따라서 법 $7$에 대한 $2$의 위수는 $3$이고, 이때 $3<6=\phi(7)$이고 $3|\phi(7)$이다.

$a\equiv b\,(\text{mod}\,n)\,(\gcd{a,\,n}=1,\,\text{gcd}(b,\,n)=1)$이면, $a^{k}\equiv b^{k}\,(\text{mod}\,n)$이고, $\text{gcd}(a,\,n)=1$인 경우에만 $a$의 위수를 정의할 수 있다. 

(만약 $\text{gcd}(a,\,n)>1$이면, 합동식 $ax\equiv1\,(\text{mod}\,n)$의 해가 존재하지 않으므로 $a^{k}\equiv1\,(\text{mod}\,n)$이 성립하지 않는다.)

$k$를 법 $n$에 대한 $a$의 위수라고 하자. $a^{h}\equiv1\,(\text{mod}\,n)$일 필요충분조건은 $k|h$이다(특히 $k|\phi(n)$).

증명:

$(\Rightarrow)$: $a^{h}\equiv1\,(\text{mod}\,n)$이라 하자. 그러면 나눗셈 알고리즘으로부터 $h=qk+r\,(0\leq r\leq k-1)$이고 $$1\equiv a^{qk+r}\equiv(a^{k})^{q}a^{r}\equiv a^{r}\,(\text{mod}\,n)$$ 이므로 $r=0$($\because\,k$는 위수)이다.

$(\Leftarrow)$: 자명하다.

위 정리는 위수를 찾을 때, $\phi(n)$의 약수 안에서만 찾으면 됨을 뜻한다.

법 $13$에 대한 $2$의 위수를 찾자. $\phi(13)=12$이고 $12$의 약수는 $1,\,2,\,3,\,4,\,6,\,12$이므로 $$2^{1}\equiv2,\,2^{2}\equiv4,\,2^{3}\equiv8,\,2^{4}=16\equiv3,\,2^{6}\equiv12\equiv-1\,(\text{mod}\,13)$$ 이고 따라서 법 $13$에 대한 $2$의 위수는 $\phi(13)=12$이다.

$\phi(n)$의 약수 $d$에 대하여 $d$를 위수로 갖는 수 $a$가 존재하지 않을 수 있다. 예를 들어 $n=12$이면, $$\phi(12)=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=4$$ 이고, $4$의 약수는 $1,\,2,\,4$이다. $12$와 서로소이면서 작은 양의 정수는 $1,\,5,\,7,\,11$이고, $1^{2}\equiv5^{2}\equiv7^{2}\equiv11^{2}\,(\text{mod}\,12)$이고, 위수가 $4$인 $a$는 존재하지 않는다.

$k$를 법 $n$에 대한 $a$의 위수라고 하자. 그러면 $a^{i}\equiv a^{j}\,(\text{mod}\,n)$일 필요충분조건은 $i\equiv j\,(\text{mod}\,n)$이자.

증명:

$(\Rightarrow)$: $a^{i}\equiv a^{j}\,(\text{mod}\,n)$이라 하자. 일반성을 잃지 않고 $i\geq j$라고 할 수 있으며 $a^{i-j}\equiv1\,(\text{mod}\,n)$이므로 $k|i-j$이고 따라서 $i\equiv j\,(\text{mod}\,n)$이다.

$(\Leftarrow)$: $i\equiv j\,(\text{mod}\,n)$이라 하면, $k|i-j$이고, 적당한 $q\in\mathbb{Z}$에 대하여 $i-j=qk$이므로 $$a^{i}\equiv a^{j+qk}\equiv a^{j}(a^{k})^{q}\equiv a^{j}\,(\text{mod}\,n)$$ 이다.

$k$를 법 $n$에 대한 $a$의 위수라고 하자. 그러면 $a,\,a^{2},\,\cdots,\,a^{k}$는 어느 두개도 서로 법 $n$에 대해 합동이 아니다.

증명: $a^{i}\equiv a^{j}\,(\text{mod}\,n)\,(1\leq i\leq j\leq k)$이라 하자. 그러면 $i\equiv j\,(\text{mod}\,n)$이고, 이 합동식은 $i=j$인 경우에 한해서만 성립한다. 그러므로 $a,\,a^{2},\,\cdots,\,a^{k}$는 어느 두개도 서로 법 $n$에 대해 합동이 아니다.

$k$를 법 $n$에 대한 $a$의 위수라고 하고 $h>0$이라 하자. 그러면 법 $n$에 대한 $a^{h}$의 계수는 $\displaystyle\frac{k}{\text{gcd}(h,\,k)}$이다.

증명: 법 $n$에 대한 $a^{h}$의 위수를 $r$이라고 하고 $d=\text{gcd}(h,\,k)$라 하자. 그러면 $h=h_{1}d$, $k=k_{1}d\,(\text{gcd}(h_{1},\,k_{1})=1)$이고 $$(a^{h})^{\frac{k}{h}}=(a^{h_{1}d})^{\frac{k}{d}}=(a^{k})^{h_{1}}\equiv(1)^{h_{1}}\equiv1\,(\text{mod}\,n)$$ 이므로 $\displaystyle r|\frac{k}{d}=k_{1}$이다.

$a^{hr}\equiv(a^{h})^{r}\equiv1\,(\text{mod}\,n)$이므로 $k|hr$이고, $dk_{1}|dh_{1}r$이므로 $k_{1}|h_{1}r$이고, $k_{1}|r$이다. 따라서 $r=k_{1}$이고, $$r=k_{1}=\frac{k}{d}=\frac{k}{\text{gcd}(h,\,k)}$$ 이다.

$\text{gcd}(a,\,n)=1$이고, $a$의 위수가 $\phi(n)$이면, $a$를 $n$의 원시근(primitive root)이라고 한다.

예를 들어 $3$은 $7$의 원시근이다. 그 이유는 $\phi(7)=6$이고, $$3^{1}\equiv3,\,3^{2}\equiv2,\,3^{3}\equiv6,\,3^{6}\equiv1\,(\text{mod}\,7)$$ 이기 때문이다.

$\text{gcd}(a,\,n)=1$, $\{a_{1},\,\cdots,\,a_{\phi(n)}\}$을 $n$과 서로소이고 $n$보다 작은 양의 정수라고 하자. $a$가 $n$의 원시근이면, $a,\,a^{2},\,\cdots,\,a^{\phi(n)}$은 어떤 순서로 $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}$과 법 $n$에 대해 합동이다.

증명: $\text{gcd}(a,\,n)=1$이므로 $\text{gcd}(a^{r},\,n)=1$이고, $a,\,a^{2},\,\cdots,\,a^{\phi(n)}$중 어느 두개도 서로 법 $n$에 대해 합동이 아니다. 따라서 $a^{r}$은 $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}$중 하나와 법 $n$에 대해 합동이다. 또한 $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}$중 어느 두개도 서로 법 $n$에 대해 합동이 아니다. 그러므로 $a^{r}$은 $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}$중 하나로 나타낼 수 있다.

$n$이 원시근을 가지면, 원시근은 총 $\phi(\phi(n))$개 가진다.

증명: $a$를 $n$의 원시근이라고 하자. 그러면 $n$의 또다른 원시근은 $a,\,a^{2},\,\cdots,\,a^{\phi(n)}$중 하나이고, $a^{h}$중 위수가 $\phi(n)$이려면 $\text{gcd}(h,\,\phi(n))=1$이어야 한다. 이러한 $h$는 $\phi(\phi(n))$개가 존재하고 따라서 원시근은 $\phi(\phi(n))$개 존재한다.

$a=2,\,n=9$라 하자. $\displaystyle\phi(9)=\phi(3^{2})=9\left(1-\frac{1}{3}\right)=6$이고 $$2^{2}\equiv2,\,2^{2}\equiv4,\,2^{3}\equiv8,\,2^{4}=16\equiv7,\,2^{5}=32\equiv5,\,2^{6}\equiv10\equiv1\,(\text{mod}\,9)$$ 이므로 $2$는 $9$의 원시근이다. $\phi(\phi(9))=\phi(6)=\phi(2)\phi(3)=2$이므로 $9$는 원시근을 $2$개 가지며, $2$가 $9$의 원시근이므로 또 다른 원시근은 $5$이다.(참고: $7^{1}\equiv7,\,7^{2}\equiv4,\,7^{3}\equiv28\equiv1\,(\text{mod}\,9)$, $2^{6}\equiv2^{12}\equiv2^{18}\cdots\equiv2^{30}\equiv1\,(\text{mod}\,9)$)

소수의 원시근

라그랑주 정리(Lagrange's theorem)

$p$를 소수, $f(x)=a_{n}x^{n}+\cdots+a_{1}x+a_{0}\,(a_{n}\not\equiv0\,(\text{mod}\,p,\,a_{k}\in\mathbb{Z}))$라 하자. 그러면 합동식 $f(x)\equiv0\,(\text{mod}\,p)$는 법 $p$에 대해 서로 합동이 아닌 해를 최대 $n$개 갖는다.

증명: $f(x)$의 차수 $n$에 대한 귀납법으로 증명하자.

$n=1$이면, $f(x)=a_{1}x+a_{0}\,(a_{1}\not\equiv0\,(\text{mod}\,p))$이고 $\text{gcd}(a_{1},\,p)=1$이므로 $a_{1}x+a_{0}\equiv0\,(\text{mod}\,p)$이고 따라서 합동식 $a_{1}x\equiv a_{0}\,(\text{mod}\,p)$는 법 $p$에 대해 유일한 해를 갖는다.

귀납적으로 $n=k-1$일 때 성립한다고 가정하자. $f$의 차수가 $k$일 때, 합동식 $f(x)\equiv0\,(\text{mod}\,p)$의 해가 존재하지 않으면, 증명이 끝난다.

$f(x)\equiv0\,(\text{mod}\,p)$가 해 $x\equiv a\,(\text{mod}\,p)$를 가지면, $f(x)=(x-a)q(x)+r$일 때, $$0\equiv f(a)\equiv(a-a)q(a)+r\equiv r\,(\text{mod}\,p)$$ 이고, $b$를 $a$와 또다른 해라고 하면 $$0\equiv f(b)\equiv(b-a)q(b)$$ 이고 $a\neq b$이므로 $q(b)\equiv0\,(\text{mod}\,n)$이다. 이것은 $f(x)\equiv0\,(\text{mod}\,p)$의 $a$가 아닌 해들이 합동식 $q(x)\equiv0\,(\text{mod}\,p)$을 만족해야 함을 뜻하고, 이 합동식의 해는 최대 $k-1$개이므로 따라서 합동식 $f(x)\equiv0\,(\text{mod}\,p)$는 최대 $k$개의 해를 갖는다.

$p$가 소수이고 $d|p-1$이면, 합동식 $x^{d}-1\equiv0\,(\text{mod}\,p)$는 정확히 $d$개의 해를 갖는다.

증명: $d|p-1$이므로 $p-1=dk$이고, $$\begin{align*}x^{p-1}-1&=(x^{d})^{k}-1\\&=(x^{d}-1)(1+x^{d}+\cdots+x^{(k-1)d})\\&=(x^{d}-1)f(x)\,(f(x)=x^{d(k-1)}+x^{d(k-2)}+\cdots+x^{d}+1)\end{align*}$$ 이다. $f(x)$의 차수가 $d(k-1)=p-1-d$이므로 라그랑주 정리에 의해 합동식 $f(x)\equiv0\,(\text{mod}\,p)$는 최대 $p-1-d$개의 해를 갖는다.

페르마의 정리에 의해 $x^{p-1}-1\equiv0\,(\text{mod}\,p)$이므로, 이 합동식은 $p-1$개의 해 $1,\,2,\,\cdots,\,p-1$를 갖는다.

$x^{p-1}-1\equiv0\,(\text{mod}\,p)$의 해이고 $f(x)\equiv0\,(\text{mod}\,p)$의 해가 아니면 $x^{d}-1\equiv0\,(\text{mod}\,p)$의 해가 됨을 보이자. $a$를 합동식 $x^{p-1}-1\equiv0\,(\text{mod}\,p)$의 해이면, $f(x)\equiv0\,(\text{mod})\,p$의 해가 아니고, $0\equiv a^{p-1}-1\equiv(a^{d}-1)f(a)\,(\text{mod}\,p)$이므로 $a^{d}-1\equiv0\,(\text{mod}\,p)$이다. 그러면 $x^{d}-1\equiv0\,(\text{mod}\,p)$는 적어도 $p-1-(p-1-d)=d$개의 해를 갖고, 라그랑주 정리에 의해 최대 $d$개의 해를 가지므로 따라서 정확히 $d$개의 해를 가진다.

소수 $p$에 대하여 $p$는 $\phi(p-1)$개의 원시근을 갖는다.

증명: $\psi(d)$를 $1$부터 $p-1$중 위수가 $d$인 정수의 개수라고 하면, $\psi(d)=\phi(d)$가 성립함을 보인다.

$\psi(d)\neq0$이면, $\psi(d)=\phi(d)$가 성립함을 보이자.

위수가 $d$인 정수가 존재하면 $a_{1},\,\cdots,\,a_{d}$중 어느 두개도 법 $p$에 대해 서로 합동이 아니다. 그러므로 이 수들은 합동식 $x^{d}-1\equiv0\,(\text{mod}\,p)$의 해이고 $a,\,a^{2},\,\cdots,\,a^{d}$는 합동식 $x^{d}\equiv0\,(\text{mod}\,p)$의 해이다.

따라서 위수가 $d$인 정수는 $a_{1},\,\cdots,\,a_{d}$중 어느 하나와 합동이고, $a^{h}$중에서 위수가 $p-1$인 것은 모두 $\phi(d)$개이므로 $\psi(d)=\phi(d)$이다.

$\psi(d)=\phi(d)$가 성립함을 보이자.

$\displaystyle\sum_{d|p-1}{\psi(d)}=p-1$($\because$ 위수 $d$는 반드시 $p-1$을 나눈다)이므로 $\displaystyle\sum_{d|n}{\phi(d)}=n$이고, $\displaystyle\sum_{d|p-1}{\psi(d)}=\sum_{d|p-1}{\phi(d)}$이다. $d|p-1$가 존재해서 $\psi(d)=0$이면, $\displaystyle\sum_{d|p-1}{\psi(d)}<\sum_{d|p-1}{\phi(d)}$가 되는데 이는 모순이다. 그러므로 모든 $d$에 대하여 $d|p-1$이고 $\psi(d)\neq0$이므로 따라서 $\psi(d)=\phi(d)$이다.

법 $31$에 대해 위수가 $6$인 정수를 구하자. $\phi(31)=30$, $6|30$이므로 $\phi(\phi(31))=\phi(30)=8$이고, $30$의 약수는 $1,\,2,\,3,\,5,\,6,\,10,\,15,\,30$이고 $2^{5}\equiv1\,(\text{mod}\,31)$이므로, $2$는 $31$의 원시근이 아니다. 반면 $3^{30}\equiv1\,(\text{mod}\,31)$이므로 $3$은 $31$의 원시근이다.

$3^{h}$의 계수가 $6$일 필요충분조건은 $\displaystyle6=\frac{30}{\text{gcd}(h,\,30)}$이고, $\text{gcd}(h,\,30)=5$이어야 한다. 그러면 $h=5,\,25$이고, $$\begin{align*}3^{5}&\equiv27\cdot9\equiv(-4)\cdot9=-36\equiv26\,(\text{mod}\,31)\\3^{25}&\equiv(3^{5})^{5}\equiv(26)^{5}\equiv(-5)^{5}\equiv(-125)\cdot25\equiv(-1)\cdot25\equiv6\,(\text{mod}\,31)\end{align*}$$ 이므로 법 $31$에 대해 위수가 $6$인 정수는 $6,\,26$이다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill

정수론 8판, 김응태, 박승안, 경문사