원시근(Primitive root)

모듈러 연산⁠(modular arithmetic)⁠의 시계 $n =$ 에서 1부터 출발해 매번 $a =$ 씩 곱해 봅시다. 자취는 입니다.

나머지는 $n$가지뿐이니 거듭제곱은 언젠가 이미 들른 수로 돌아옵니다(비둘기집 원리⁠, pigeonhole principle⁠). $a$가 $n$과 서로소⁠(coprime)⁠이면(최대공약수⁠(greatest common divisor)⁠가 1) 곱하기 $a$는 되돌릴 수 있는 전단사⁠(bijective)⁠라서, 돌아오는 곳은 언제나 출발점 1입니다. 처음 1로 돌아오기까지의 걸음 수가 $a$의 위수입니다.

$n$과 서로소인 나머지는 $\varphi(n)$개(오일러 피 함수⁠, Euler's totient function⁠)이고, 서로소인 $a$의 거듭제곱은 그 안에서만 움직이니 위수⁠(order)⁠는 $\varphi(n)$을 넘지 못합니다. 이 최대치에 닿는 수, 곧 서로소인 나머지를 한 바퀴에 모두 도는 수가 원시근입니다(오른쪽 노란 막대). 더 나아가 위수는 늘 $\varphi(n)$의 약수⁠(divisor)⁠입니다. 오일러 정리⁠(Euler's theorem)⁠에 따라 $a^{\varphi(n)} \equiv 1$이고, 1로 돌아오는 지수는 모두 위수의 배수⁠(multiple)⁠이기 때문입니다.

$n$이 소수⁠(prime number)⁠ $p$이면 원시근이 반드시 있고, 개수는 $\varphi(p-1)$입니다. 이유를 세 걸음으로 봅니다. 핵심은 소수 $p$로 나눈 나머지만 볼 때(이를 "$p$를 법으로 한다"고 합니다) $x^d \equiv 1$을 만족하는 $x$가 $d$개를 넘지 못한다는 사실입니다. 법이 소수이면 0이 아닌 나머지로 언제나 나눌 수 있어서, 보통의 수에서처럼 $d$차 다항식⁠(polynomial)⁠의 근이 $d$개를 넘지 못하기 때문입니다. 여기서 위수가 $d$인 수는 많아야 $\varphi(d)$개라는 것이 따라 나옵니다(그런 $x$가 있으면 $x, x^2, \dots, x^d$가 해의 전부이고, 그중 위수가 $d$인 것은 $\varphi(d)$개입니다). 그런데 $p-1$의 약수 $d$ 전체에 대해 $\varphi(d)$를 더하면 정확히 $p-1$입니다. 1부터 $p-1$까지의 수가 저마다 이 약수 가운데 하나를 위수로 가지려면 모든 $d$에서 개수가 $\varphi(d)$로 꽉 차야 하고, $d = p-1$에서 원시근 $\varphi(p-1)$개가 나옵니다.

반면 $n = 8, 12, 15$처럼 원시근이 아예 없는 수도 있습니다. 원시근이 있는 $n$은 $2, 4, p^k, 2p^k$($p$는 홀수 소수)뿐입니다. 15에 없는 이유는 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠로 보면 분명합니다. 15로 나눈 나머지는 3으로 나눈 나머지와 5로 나눈 나머지의 쌍입니다. 3 쪽 시계에서는 위수가 많아야 2이고, 5 쪽 시계에서는 많아야 4입니다. 그러니 두 시계가 동시에 1로 돌아오는 걸음 수는 2와 4의 최소공배수⁠(least common multiple)⁠ $\operatorname{lcm}(2, 4) = 4$를 넘지 못하고, $\varphi(15) = 8$에 닿는 수는 없습니다.

원시근 $g$가 있으면 $n$과 서로소인 나머지(곱셈을 되돌릴 수 있어 '단원'이라 부릅니다)가 모두 $g, g^2, \dots, g^{\varphi(n)}$으로 한 줄로 늘어섭니다. 그러면 곱셈은 지수의 덧셈이 됩니다. $g^i \cdot g^j = g^{i+j}$이고 지수는 $\varphi(n)$(소수 $p$라면 $p-1$)에서 0으로 감깁니다. 복소평면⁠(complex plane)⁠에서 1의 거듭제곱근⁠(roots of unity)⁠을 곱하면 각도가 더해지며 원을 도는데(회전⁠, rotation⁠), 1의 $\varphi(n)$제곱근들의 곱셈과 정확히 같은 구조입니다. 거꾸로 $g^k$에서 지수 $k$를 되찾는 일을 보통의 로그에 빗대어 이산로그라 부릅니다. $p$가 수백 자리이면 이 되돌리기를 빠르게 하는 방법이 알려져 있지 않고, 그것이 디피–헬먼 키 교환⁠(Diffie–Hellman key exchange)⁠의 자물쇠입니다.

이어지는 곳. 원 위에 곱셈을 화살표로 그리는 그림은 원 위의 곱셈표⁠(times tables on a circle)⁠와 같은 발상입니다. 2가 원시근이 되는 소수(3, 5, 11, 13, 19, …)가 무한히 많은지는 아직 증명되지 않았습니다. 1927년 오스트리아 출신 수학자 에밀 아르틴이 내놓은 추측이라 아르틴 추측⁠(Artin's conjecture on primitive roots)⁠이라 부릅니다. 다만 1967년 영국의 크리스토퍼 훌리가, 일반화된 리만 가설⁠(Riemann hypothesis)⁠을 참이라고 가정하면 이 추측이 성립함을 증명했습니다. 일반화된 리만 가설은 제타 함수⁠(zeta function)⁠를 닮은 여러 함수⁠(function)⁠의 자명하지 않은 영점⁠(nontrivial zero)⁠도 모두 한 직선 위에 있다는, 리만 가설을 넓힌 추측입니다. 큰 수가 소수인지 가리는 소수 판정⁠(primality test)⁠도 같은 거듭제곱의 고리를 들여다봅니다.