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판, 김응태, 박승안, 경문사