원시근 (정수론)

정의

2 이상의 정수 \(m\)에 대해 \((g,m)=1\)이고 \(\operatorname{ord}_m g = \phi(m)\)인 정수 \(g\)가 존재할 때, \(g\)를 법 \(m\)에 대한 원시근(primitive root)이라고 한다. 이때 \(\operatorname{ord}\)는 위수를, \(\phi\)는 오일러 피 함수를 나타낸다.

존재성

법 \(m\)에 대한 원시근이 존재할 필요충분조건은 \(m\)이 2, 4, \(p^n\), \(2p^n\) 꼴인 것이다. 이때 \(p\)는 3 이상의 소수이고 \(n\)은 양의 정수이다.

실제로, \(m\)이 2이면, 1이 원시근, \(m\)이 4이면 3이 원시근이다. 이제 \(m\)이 3이상인 소수 \(p\)라 하자. \(p\)의 원시근이 존재함을 증명하기 위해선 약간의 사전 지식이 필요하다.

• 라그랑주의 정리: [math]\displaystyle{ f\left(x\right)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 }[/math]을 \(n\)차 다항식이라 하자 ([math]\displaystyle{ n\geq1,\,p\nmid a_n }[/math]). 그럼, [math]\displaystyle{ f\left(x\right)\equiv0\pmod p }[/math]는 아무리 많아야 \(n\)개의 서로 다른 근을 가진다.
  • 수학적 귀납법을 사용한다. [math]\displaystyle{ n=1 }[/math]이면, [math]\displaystyle{ f\left(x\right)=a_1x+a_0,\,p\nmid a_1 }[/math]이다. 이는 곧 [math]\displaystyle{ a_1x\equiv-a_0\pmod p }[/math]이고, [math]\displaystyle{ \gcd\left(a_1,p\right)=1 }[/math]이므로 이 합동식은 유일한 해를 가진다. 이제 이 명제가 \(n-1\)차 다항식에 대해 성립한다고 가정하자. 또한, [math]\displaystyle{ f\left(x\right) }[/math]를 최고 차항의 계수가 \(p\)로 나누어 떨어지지 않는 \(n\)차 다항식이라 가정하자. 만약 [math]\displaystyle{ f\left(x\right) }[/math]이 \(n+1\)개의 근, [math]\displaystyle{ c_0,c_1,\cdots,c_n }[/math]을 가진다고 가정하면, [math]\displaystyle{ f\left(c_k\right)\equiv0\pmod p,\,k=0,1,\cdots,n }[/math]이다. 그럼,[math]\displaystyle{ f\left(x\right)-f\left(c_0\right)=a_n\left(x^n-{c_0}^n\right)+a_{n-1}\left(x^{n-1}-{c_0}^{n-1}\right)+\cdots+a_1\left(x-c_0\right)=\left(x-c_0\right)g\left(x\right) }[/math]이다 ([math]\displaystyle{ g\left(x\right) }[/math]는 최고 차항의 계수가 \(a_n\)인 \(n-1\)차 다항식). 이제 \(k\)를 [math]\displaystyle{ 1\leq k\leq n }[/math]인 정수라 가정하자. 그럼, [math]\displaystyle{ f\left(c_k\right)\equiv f\left(c_0\right)\equiv0\pmod p }[/math]이고, [math]\displaystyle{ f\left(c_k\right)-f\left(c_0\right)\equiv\left(c_k-c_0\right)g\left(c_k\right)\equiv0\pmod p }[/math]이다. 이는 곧 \(c_k\)가 [math]\displaystyle{ g\left(x\right) }[/math]의 근임을 의미한다. 즉, [math]\displaystyle{ g\left(x\right) }[/math]는 \(n\)개의 근을 가진다. 그런데 이는 귀납 가정에 모순이다. 따라서 [math]\displaystyle{ f\left(x\right) }[/math]는 아무리 많아야 \(n\)개의 근을 가진다.
• \(p\)를 소수, \(d\)를 \(p-1\)의 약수라 가정하자. 그럼 [math]\displaystyle{ x^d-1 }[/math]는 법 \(p\)에 대해 \(d\)개의 근을 가진다.
  • [math]\displaystyle{ p-1=de }[/math]라 하자. 그럼, [math]\displaystyle{ x^{p-1}=\left(x^d-1\right)\left(x^{d\left(e-1\right)}+x^{d\left(e-2\right)}+\cdots+x^d+1\right)=\left(x^d-1\right)g\left(x\right) }[/math]이다. 페르마의 소정리에 의해 [math]\displaystyle{ x^{p-1}-1 }[/math]이 법 \(p\)에 대해 \(p-1\)개의 근을 가짐은 쉽게 보일 수 있다. 더욱이, 이 근은 [math]\displaystyle{ x^d-1 }[/math]의 근이거나 [math]\displaystyle{ g\left(x\right) }[/math]의 근이기도 하다. 라그랑주의 정리에 의해 [math]\displaystyle{ g\left(x\right) }[/math]는 최대 [math]\displaystyle{ d\left(e-1\right)=de-d=p-d-1 }[/math]개의 근을 가진다. 따라서, [math]\displaystyle{ x^d-1 }[/math]는 최소한 [math]\displaystyle{ \left(p-1\right)-\left(p-d-1\right)=d }[/math]개의 근을 가진다. 한편, 라그랑주의 정리에 의해 [math]\displaystyle{ x^d-1 }[/math]는 최대 \(d\)개의 근을 가진다. 따라서, [math]\displaystyle{ x^d-1 }[/math]는 정확히 \(d\)개의 근을 가진다.
• \(p\)를 소수, \(d\)를 \(p-1\)의 약수라 가정하자. 또한, [math]\displaystyle{ F\left(d\right) }[/math]를 \(p\)보다 작은 양의 정수 중에 위수가 \(d\)인 것의 개수라 하자. 그럼, [math]\displaystyle{ F\left(d\right)=0 }[/math]이거나 [math]\displaystyle{ F\left(d\right)=\phi\left(d\right) }[/math]이다 ([math]\displaystyle{ \phi\left(d\right) }[/math]는 오일러 피 함수).
  • 만약 [math]\displaystyle{ F\left(d\right)=0 }[/math]이면, 명제는 당연히 참이다. [math]\displaystyle{ F\left(d\right)\gt 0 }[/math]이라 가정하면, 적당한 정수 \(a\)에 대해 [math]\displaystyle{ \operatorname{ord}_pa=d }[/math]이다. 그럼, [math]\displaystyle{ A=\left\{a,a^2,\cdots,a^d\right\} }[/math]의 원소는 법 \(p\)에 대해 모두 다르다. 더욱이, [math]\displaystyle{ \left(a^k\right)^d\equiv\left(a^d\right)^k\equiv1^k\equiv1\pmod p }[/math]이므로, [math]\displaystyle{ a^k }[/math]는 [math]\displaystyle{ x^d\equiv1\pmod p }[/math]의 근이다. 위 정리에 의해 [math]\displaystyle{ x^d\equiv1\pmod p }[/math]를 만족하는 근은 정확히 \(d\)개 있고, \(A\)의 원소의 개수 역시 \(d\)이므로 \(A\)는 [math]\displaystyle{ x^d\equiv1\pmod p }[/math]의 모든 근을 포함하고 있다. 한편, [math]\displaystyle{ \operatorname{ord}_pa^k=\frac{\operatorname{ord}_pa}{\gcd\left(k,d\right)}=\frac{d}{\gcd\left(k,d\right)} }[/math]이고, [math]\displaystyle{ \gcd\left(k,d\right)=1 }[/math]일 때만 [math]\displaystyle{ \operatorname{ord}_pa^k=d }[/math]이 성립한다. 이를 만족하는 \(k\)의 개수는 [math]\displaystyle{ \phi\left(d\right) }[/math]개 이고, 이는 곧 [math]\displaystyle{ F\left(d\right)=\phi\left(d\right) }[/math]임을 보인다.
• 이제 위 정리의 따름정리가 \(p\)의 원시근의 존재를 보장해준다. [math]\displaystyle{ p-1\mid p-1 }[/math]이므로 위 정리에 의해 [math]\displaystyle{ \operatorname{ord}_pa=p-1 }[/math]를 만족하는 정수 \(a\)가 ([math]\displaystyle{ \phi\left(p-1\right) }[/math]개) 존재하기 때문.

이게 어딜봐서 약간의 사전 지식이냐.

\(p\)를 홀수인 소수, \(p\)의 원시근을 \(r\)이라 하자. 그럼, \(p^2\)의 원시근은 존재하며, \(r\), \(r+p\) 중 적어도 하나이다.

• 먼저, [math]\displaystyle{ \operatorname{ord}_pr=\phi\left(p\right)=p-1 }[/math]이다. [math]\displaystyle{ n=\operatorname{ord}_{p^2}r }[/math]이라 하자. 그럼, [math]\displaystyle{ n\mid\phi\left(p^2\right)=p^2-p=p\left(p-1\right) }[/math]이고, [math]\displaystyle{ r^n\equiv1\pmod{p^2} }[/math]이다. 합동식에서 [math]\displaystyle{ p^2\mid r^n-1 }[/math]임을 알 수 있고, 이는 곧 [math]\displaystyle{ p\mid r^n-1 }[/math], 혹은 [math]\displaystyle{ r^n\equiv1\pmod p }[/math]를 의미한다. 즉, [math]\displaystyle{ \operatorname{ord}_pr\mid n }[/math], 혹은 [math]\displaystyle{ p-1\mid n }[/math]. 따라서, [math]\displaystyle{ p-1\mid n\mid p\left(p-1\right) }[/math]이고, \(p\)가 소수이므로 이게 가능한 \(n\)은 \(p-1\)이나 [math]\displaystyle{ p\left(p-1\right) }[/math]의 두 경우 뿐이다. 만약 후자일 경우, \(r\)은 \(p^2\)의 원시근이 된다. 이제 전자라 가정하자. \(s=r+p\)라 하면, [math]\displaystyle{ s\equiv r\pmod p }[/math]이므로, [math]\displaystyle{ \operatorname{ord}_ps=p-1 }[/math]이다. 그럼, 똑같은 논리에 의해 [math]\displaystyle{ \operatorname{ord}_{p^2}s }[/math]는 \(p-1\)이거나 [math]\displaystyle{ p\left(p-1\right) }[/math]이다. [math]\displaystyle{ s^{p-1}\equiv\left(r+p\right)^{p-1}\equiv r^{p-1}+\left(p-1\right)pr^{p-2}\pmod{p^2} }[/math]인데, [math]\displaystyle{ \operatorname{ord}_{p^2}r=n=p-1 }[/math]이므로 [math]\displaystyle{ r^{n-1}\equiv1\pmod{p^2} }[/math]이다. 따라서, [math]\displaystyle{ s^{p-1}\equiv1-p\left(p-1\right)r^{p-2}\equiv1-pr^{p-2}\pmod{p^2} }[/math]. 만약 [math]\displaystyle{ 1-pr^{p-2}\equiv1\pmod{p^2} }[/math]이면, [math]\displaystyle{ p^2\mid r^{p-2} }[/math]이고, 따라서 [math]\displaystyle{ p\mid r^{p-2} }[/math]이다. 이는 \(r\)이 \(p\)의 원시근이라는 사실에 모순이므로, [math]\displaystyle{ s^{p-1}\not\equiv1\pmod{p^2} }[/math]이다. 따라서, [math]\displaystyle{ \operatorname{ord}_{p^2}s=p\left(p-1\right) }[/math]이고, 증명하고자 하는 바가 증명되었다.
  • 만약 \(r\)이 \(p^2\)의 원시근임을 보였다 하자. 그렇다고해서 \(r+p\)가 \(p^2\)의 원시근이 아니라고는 말할 수 없다. 더욱이, \(r\)의 위수는 \(p-1\)이거나 [math]\displaystyle{ p\left(p-1\right) }[/math] 중 하나라는 사실도 알 수 있다.

성질

법 \(m\)에 대한 원시근 \(g\)가 존재할 때,

• \(g^i\equiv 1 \pmod m\)일 필요충분조건은 \(\phi(m) \mid i\)인 것이다.
  • 위수의 성질에 의해 [math]\displaystyle{ \operatorname{ord}_m g=\phi\left(m\right)\mid i }[/math]이다. 역으로, [math]\displaystyle{ \phi\left(m\right)\mid i }[/math]이면 적당한 정수 \(k\)에 대해 [math]\displaystyle{ i=\phi\left(m\right)k }[/math]이고, 오일러의 정리에 의해 [math]\displaystyle{ g^{\phi\left(m\right)}\equiv1\pmod m }[/math]이므로 원하는 결과를 얻는다.
• \(g^i \equiv g^j \pmod m\)일 필요충분조건은 \(i \equiv j \pmod{\phi(m)}\)인 것이다.
  • 위수의 성질에 의해 \(g^i \equiv g^j \pmod m\)일 필요충분조건은 \(i \equiv j \pmod{\operatorname{ord}_m g}\)다. 그런데 \(g\)의 위수가 [math]\displaystyle{ \phi\left(m\right) }[/math]이므로 원하는 결과를 얻는다.
• \(\operatorname{ord}_m g^k = \dfrac{\phi(m)}{(k,\phi(m))}\)
  • 위수의 성질에 의해 [math]\displaystyle{ \operatorname{ord}_m g^k=\frac{\operatorname{ord}_m g}{\gcd\left(k,\operatorname{ord}_m g\right)} }[/math]이다. 그런데 \(g\)의 위수가 [math]\displaystyle{ \phi\left(m\right) }[/math]이므로 원하는 결과를 얻는다.
• 법 \(m\)에 대한 원시근은 \(\phi(\phi(m))\)개 존재한다.
  • \(g\)가 원시근이라면, [math]\displaystyle{ \left\{g^1,g^2,\cdots,g^{\phi\left(m\right)}\right\} }[/math]은 기약잉여계를 구성한다. 이는 곧 법 \(m\)에 대한 모든 원시근이 저 안에 포함된다는 소리이고, 바로 윗 성질에 의해 [math]\displaystyle{ \operatorname{ord}_m g^k=\phi\left(m\right) }[/math]을 만족하는 지수 \(k\)는 [math]\displaystyle{ \gcd\left(k,\phi\left(m\right)\right)=1 }[/math]을 만족한다. 곧, 이러한 \(k\)의 개수는 [math]\displaystyle{ \phi\left(\phi\left(m\right)\right) }[/math]개 존재하고, 이는 모든 원시근의 개수와 같다.