원시근 (정수론)

정의

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

존재성

법 [math]\displaystyle{ m }[/math]에 대한 원시근이 존재할 필요충분조건은 [math]\displaystyle{ m }[/math]이 2, 4, [math]\displaystyle{ p^k }[/math], [math]\displaystyle{ 2p^k }[/math] 꼴인 것이다. 이때 [math]\displaystyle{ p }[/math]는 3 이상의 소수이고 [math]\displaystyle{ k }[/math]은 양의 정수이다.

[math]\displaystyle{ m=p }[/math]일 때

약간의 사전 지식이 필요하다.

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

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

• 지나가던 행인 : 위의 "만약 [math]\displaystyle{ F\left(d\right)=0 }[/math]이면, 명제는 당연히 참이다." 는 [math]\displaystyle{ \sum_{d\mid p-1}\phi\left(d\right)=p-1 }[/math] 때문인듯.

[math]\displaystyle{ m=p^2 }[/math]일 때

[math]\displaystyle{ p }[/math]를 홀수인 소수, [math]\displaystyle{ p }[/math]의 원시근을 [math]\displaystyle{ r }[/math]이라 하자. 그럼, [math]\displaystyle{ p^2 }[/math]의 원시근은 존재하며, [math]\displaystyle{ r }[/math], [math]\displaystyle{ r+p }[/math] 중 적어도 하나이다.

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

[math]\displaystyle{ m=p^k }[/math]일 때

[math]\displaystyle{ p }[/math]를 홀수인 소수, [math]\displaystyle{ r }[/math]을 [math]\displaystyle{ p }[/math]와 [math]\displaystyle{ p^2 }[/math]의 원시근이라 하자. 그럼 [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ p^k,\,k\in\mathbb{Z}^+ }[/math]의 원시근이다.

• 수학적 귀납법을 사용하여 [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}\not\equiv1\pmod{p^k} }[/math]임을 먼저 보일 것이다. [math]\displaystyle{ k=2 }[/math]일 때, [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ p^2 }[/math]의 원시근이므로, [math]\displaystyle{ r^{p-1}\not\equiv\pmod{p^2} }[/math]이다. 이제 적당한 [math]\displaystyle{ k\geq2 }[/math]에 대해 [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}\not\equiv1\pmod{p^k} }[/math]라 가정하자. [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ p }[/math]의 원시근이므로, [math]\displaystyle{ \gcd\left(r,p\right)=1 }[/math]이고, 따라서 [math]\displaystyle{ \gcd\left(r,p^{k-1}\right)=1 }[/math]이다. 그러므로 오일러의 정리에 의해, [math]\displaystyle{ r^{\phi\left(p^k-1\right)}\equiv1\pmod{p^{k-1}} }[/math]이다. 즉, [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}\equiv1\pmod{p^{k-1}} }[/math]. 이 합동식을 디오판토스 방정식으로 풀어쓰면 [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}=1+dp^{k-1} }[/math]이다. 만약 [math]\displaystyle{ d\mid p }[/math]이면 [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}\equiv1\pmod{p^k} }[/math]이 되고, 이는 귀납 가정에 모순이므로 [math]\displaystyle{ d\not\mid p }[/math]이다. 그럼, 이항정리에 의해 [math]\displaystyle{ \left(r^{p^{k-2}\left(p-1\right)}\right)^p=\left(1+dp^{k-1}\right)^p=1+pdp^{k-1}+\binom{p}{2}\left(dp^{k-1}\right)^2+\cdots+\left(dp^{k-1}\right)^p }[/math]이다. 4번째 항부터는 [math]\displaystyle{ \left(p^{k-1}\right)^3 }[/math]을 가지고 있고, [math]\displaystyle{ 3k-3\geq k+1 }[/math]이므로 저 항들은 법 [math]\displaystyle{ p^{k+1} }[/math]에 대해 0과 합동이다. 또한, [math]\displaystyle{ \binom{p}{2}\left(dp^{k-1}\right)^2=\frac{p-1}{2}d^2p^{2k-1} }[/math]이고, [math]\displaystyle{ 2k-1\geq k+1 }[/math]이므로 이 항 역시 법 [math]\displaystyle{ p^{k+1} }[/math]에 대해 0과 합동이다. 따라서, [math]\displaystyle{ d\not\mid p }[/math]이므로 [math]\displaystyle{ r^{p^{k-1}\left(p-1\right)}\equiv1+dp^k\not\equiv1\pmod{p^{k+1}} }[/math]이다. 수학적 귀납법에 의해 증명하고자 하는 바가 증명되었다.
• [math]\displaystyle{ n=\operatorname{ord}_{p^k}r }[/math]이라 하자. 그럼, [math]\displaystyle{ n\mid\phi\left(p^k\right)=p^{k-1}\left(p-1\right) }[/math]이고, [math]\displaystyle{ r^n\equiv1\pmod{p^k} }[/math]이다. 이는 곧 [math]\displaystyle{ r^n\equiv1\pmod p }[/math]이고, [math]\displaystyle{ \operatorname{ord}_pr\mid n }[/math]이다. 따라서, [math]\displaystyle{ p-1\mid n\mid p^{k-1}\left(p-1\right) }[/math]이고, [math]\displaystyle{ n=p^t\left(p-1\right),\,0\leq t\leq k-1 }[/math]이다. 만약 [math]\displaystyle{ t\leq k-2 }[/math]이면, [math]\displaystyle{ r^{p^{k-2}\left(p-1\right)}\equiv\left(r^{p^t\left(p-1\right)}\right)^{p^{k-2-t}}\equiv1\pmod{p^k} }[/math]이고, 이는 위에서 증명한 명제에 반한다. 즉, [math]\displaystyle{ t=k-1 }[/math]이어야만 한다. [math]\displaystyle{ n=p^{k-1}\left(p-1\right)=\phi\left(p^k\right) }[/math].
  • [math]\displaystyle{ r,\,r+p }[/math]중 적어도 하나는 [math]\displaystyle{ p,\,p^2 }[/math]의 원시근이므로, [math]\displaystyle{ p^k }[/math]의 원시근은 반드시 존재한다.

[math]\displaystyle{ m=2^k }[/math]일 때

[math]\displaystyle{ m=2 }[/math]이면, 1이 원시근이다. 만약 [math]\displaystyle{ m=2^2=4 }[/math]이면, 3이 원시근이다. [math]\displaystyle{ k\geq3 }[/math]일 때, [math]\displaystyle{ 2^k }[/math]의 원시근은 존재하지 않는다. 좀 더 자세하게 설명하면, [math]\displaystyle{ a }[/math]이 홀수인 정수이면, [math]\displaystyle{ a^{\frac{\phi\left(2^k\right)}{2}}\equiv1\pmod{2^k} }[/math]이다.

• 먼저, [math]\displaystyle{ \phi\left(2^k\right)=2^k-2^{k-1}=2^{k-1} }[/math]이다. [math]\displaystyle{ k=3 }[/math]일 때, [math]\displaystyle{ a^2-1=\left(a-1\right)\left(a+1\right)=\left(2l+1-1\right)\left(2l+1+1\right)=4l\left(l+1\right) }[/math]이고, 연속한 두 수 중 하나는 짝수이므로 [math]\displaystyle{ 8\mid4l\left(l+1\right) }[/math]이다. 따라서, [math]\displaystyle{ a^2\equiv1\pmod8 }[/math] 이제 적당한 정수 [math]\displaystyle{ k\geq3 }[/math]에 대해 [math]\displaystyle{ a^{2^{k-2}}\equiv1\pmod{2^k} }[/math]라 가정하자. 이를 디오판토스 방정식으로 나타내면, [math]\displaystyle{ a^{2^{k-2}}=1+d2^k }[/math]이고, 양변을 제곱하면, [math]\displaystyle{ a^{2^{k-1}}=\left(1+d2^k\right)^2=1+d2^{k+1}+d^22^{2k} }[/math]이다. 한편, [math]\displaystyle{ k\geq3 }[/math]이므로, [math]\displaystyle{ 2k\geq k+1 }[/math]이고, 따라서 [math]\displaystyle{ 1+d2^{k+1}+d^22^{2k}\equiv1\pmod{2^{k+1}} }[/math]이다. 수학적 귀납법에 이해 증명하고자 하는 바가 증명되었다.
• [math]\displaystyle{ 2^k }[/math]의 원시근이 존재한다면, 그 원시근은 [math]\displaystyle{ 2^k }[/math]와 서로소여야 한다. 이는 곧 그 원시근이 홀수임을 의미하고, 위 명제에 의해 그 홀수의 위수는 [math]\displaystyle{ \phi\left(2^k\right) }[/math]보다 반드시 작다. 이는 곧 [math]\displaystyle{ 2^k }[/math]의 원시근이 존재하지 않음을 의미한다.

그럼 어떤 수에 대해 위수가 [math]\displaystyle{ \phi\left(2^k\right)/2=2^{k-2} }[/math]냐고 물을 수 있는데, 5는 3이상의 [math]\displaystyle{ k }[/math]에 대해 항상 저 위수를 가진다. 증명은 비슷하므로 직접 해보자.

두 개 이상의 소인수를 가진 경우

[math]\displaystyle{ m={p_1}^{t_1}{p_2}^{t_2}\cdots{p_k}^{t_k} }[/math]라 하자 (단, [math]\displaystyle{ k\geq2 }[/math]). [math]\displaystyle{ r }[/math]을 [math]\displaystyle{ m }[/math]의 한 원시근이라 가정하면, [math]\displaystyle{ \gcd\left(r,m\right)=1,\,\operatorname{ord}_mr=\phi\left(m\right) }[/math]이다. 또한, [math]\displaystyle{ \gcd\left(r,{p_i}^{t_i}\right)=1 }[/math]이다. 그럼, 오일러의 정리에 의해, [math]\displaystyle{ r^{\phi\left({p_i}^{t_i}\right)}\equiv1\pmod{{p_i}^{t_i}} }[/math]이다. 이제, [math]\displaystyle{ u=\operatorname{lcm}\left[\phi\left({p_1}^{t_1}\right),\phi\left({p_2}^{t_2}\right),\cdots,\phi\left({p_k}^{t_k}\right)\right] }[/math]이라 하자. 먼저, 모든 [math]\displaystyle{ i }[/math]에 대해 [math]\displaystyle{ \phi\left({p_i}^{t_i}\right)\mid u }[/math]이다. 곧, [math]\displaystyle{ r^u\equiv1\pmod{{p_i}^{t_i}} }[/math]이고, [math]\displaystyle{ {p_i}^{t_i}\mid r^u-1 }[/math]이다. 그런데 [math]\displaystyle{ p_i }[/math]는 전부 소수이므로, [math]\displaystyle{ {p_1}^{t_1}{p_2}^{t_2}\cdots{p_k}^{t_k}=m\mid r^u-1 }[/math]이다. 따라서, [math]\displaystyle{ r^u\equiv1\pmod m }[/math]. 위수의 성질에 의해, [math]\displaystyle{ \operatorname{ord}_mr=\phi\left(n\right)\mid u }[/math]. 그런데, 오일러 피 함수는 곱셈적 함수이므로, [math]\displaystyle{ \phi\left(m\right)=\phi\left({p_1}^{t_1}\right)\phi\left({p_2}^{t_2}\right)\cdots\phi\left({p_k}^{t_k}\right)\geq\operatorname{lcm}\left[\phi\left({p_1}^{t_1}\right),\phi\left({p_2}^{t_2}\right),\cdots,\phi\left({p_k}^{t_k}\right)\right]=u }[/math]이다. 즉, [math]\displaystyle{ \phi\left(m\right)=u }[/math]이어야 하고, 이는 곧 모든 [math]\displaystyle{ \phi\left({p_i}^{t_i}\right) }[/math]는 서로소임을 의미한다. 그런데, [math]\displaystyle{ p_i }[/math]가 홀수이면 [math]\displaystyle{ \phi\left({p_i}^{t_i}\right) }[/math]는 짝수이고, 짝수끼리는 서로소가 아니므로 [math]\displaystyle{ m }[/math]은 많아야 한 개의 홀수인 소인수를 가진다. 또한, [math]\displaystyle{ p_i=2 }[/math]이고, [math]\displaystyle{ t_i\geq2 }[/math]이면 [math]\displaystyle{ \phi\left({p_i}^{t_i}\right) }[/math]역시 짝수이다. 즉, [math]\displaystyle{ m }[/math]이 2를 소인수로 가진다면 그 소인수의 지수는 많아야 1이다. 마지막으로, [math]\displaystyle{ m }[/math]이 두 개 이상의 소인수를 가진다고 가정했으므로, 가능한 [math]\displaystyle{ m }[/math]의 형태는 [math]\displaystyle{ 2p^k }[/math]의 꼴 뿐이다.

[math]\displaystyle{ m=2p^k }[/math]일 때

위 문단의 증명은 [math]\displaystyle{ m=2p^k }[/math]일 때 원시근이 존재할 필요조건이지, 충분조건은 아니다. 실제로 원시근이 존재하는지는 알려주지 않는 셈. 물론, [math]\displaystyle{ m }[/math]이 저 형태일 때 원시근이 존재함이 알려져 있다. 정확하게는 다음과 같다.

• [math]\displaystyle{ r }[/math]이 [math]\displaystyle{ p^k }[/math]의 원시근이라 가정하자. 만약 [math]\displaystyle{ r }[/math]이 홀수면, [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ 2p^k }[/math]의 원시근이다. 만약 [math]\displaystyle{ r }[/math]이 짝수면, [math]\displaystyle{ r+p^k }[/math]이 [math]\displaystyle{ 2p^k }[/math]의 원시근이다.
• [math]\displaystyle{ r^{\phi\left(p^k\right)}\equiv1\pmod{p^k} }[/math]이고, 저보다 작은 지수는 합동식을 만족시키지 않는다. 또한, [math]\displaystyle{ \phi\left(2p^k\right)=\phi\left(2\right)\phi\left(p^k\right)=\phi\left(p^k\right) }[/math]이므로, [math]\displaystyle{ r^{\phi\left(2p^k\right)}\equiv1\pmod{p^k} }[/math]이다. 마찬가지로, 저것보다 작은 지수는 합동식을 만족시키지 않는다. 만약 [math]\displaystyle{ r }[/math]이 홀수라면, [math]\displaystyle{ r^{\phi\left(2p^k\right)} }[/math]역시 홀수이고, [math]\displaystyle{ r^{\phi\left(2p^k\right)}\equiv1\pmod2 }[/math]이다. 2와 [math]\displaystyle{ p^k }[/math]는 서로소이므로, [math]\displaystyle{ r^{\phi\left(2p^k\right)}\equiv1\pmod{2p^k} }[/math]이다. 그리고 저 지수보다 작은 지수는 합동식을 만족시키지 못하므로, [math]\displaystyle{ r }[/math]은 원시근이다. 만약 [math]\displaystyle{ r }[/math]이 짝수라면, [math]\displaystyle{ r+p^k }[/math]는 홀수이고, [math]\displaystyle{ r+p^k\equiv r\pmod{p^k},\,r+p^k\equiv1\pmod2 }[/math]이다. 즉, [math]\displaystyle{ r+p^k\equiv1\pmod{2p^k} }[/math]. 마찬가지로 저 지수보다 작은 지수는 합동식을 만족시키지 않으므로 [math]\displaystyle{ r+p^k }[/math]은 원시근이다.
• [math]\displaystyle{ r }[/math]의 존재성은 [math]\displaystyle{ p^k }[/math]의 원시근이 항상 존재함을 알고 있으므로 보장된다. 즉, 모든 [math]\displaystyle{ 2p^k }[/math]꼴의 정수는 원시근을 가진다.

결론

위 명제들을 전부 종합하면, 2, 4, [math]\displaystyle{ p^k }[/math], [math]\displaystyle{ 2p^k }[/math]형태의 정수만 원시근을 가짐을 알 수 있다. 역으로, 저 형태의 정수는 원시근을 가짐도 보였다. 따라서, [math]\displaystyle{ m }[/math]이 원시근을 갖기 위한 필요충분조건은 [math]\displaystyle{ m }[/math]이 2, 4, [math]\displaystyle{ p^k }[/math], [math]\displaystyle{ 2p^k }[/math]의 형태인 것이다.

성질

법 [math]\displaystyle{ m }[/math]에 대한 원시근 [math]\displaystyle{ g }[/math]가 존재할 때,

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