원시근 찾기 계산기
법 n에 원시근이 있는지 판정하고 가장 작은 원시근과 원시근 전체를 냅니다. 원소마다 곱셈 위수를 표로 보여 「위수는 언제나 φ(n)의 약수」라는 라그랑주 정리가 눈에 보이고, 위수를 φ(n)번 곱하지 않고 구하는 방법도 횟수로 견줍니다.
1부터 5,000까지. 모든 원소의 위수를 실제로 구하므로 상한을 두었습니다.
7의 가장 작은 원시근
3
φ(7) = 6이고 원시근은 모두 φ(φ(n)) = 2개입니다. 후보를 2개 판정하는 데 거듭제곱을 3번만 했습니다.
원시근 전부
3, 5
원시근 하나를 g라 하면 나머지는 모두 g^k 꼴이고, 그 가운데 gcd(k, φ(n)) = 1인 k만 다시 원시근이 됩니다. 그래서 개수가 정확히 φ(φ(n))개입니다.
3의 거듭제곱 한 바퀴
3 → 2 → 6 → 4 → 5 → 1
6걸음 만에 1로 돌아왔고, 그동안 7과 서로소인 수를 한 번씩 모두 훑었습니다. 이것이 원시근의 정의이며, 거듭제곱만으로 곱셈군 전체를 만들어 낸다는 뜻에서 「생성원」이라고도 합니다.
얼마나 값싸게 판정했나
위수는 언제나 φ(n)의 약수이므로(라그랑주), φ(n)의 소인수 q마다 a^(φ(n)/q) ≢ 1인지만 보면 됩니다. 하나라도 1이면 그보다 짧은 주기로 되돌아온다는 뜻이라 원시근이 아닙니다. 그래서 후보 하나를 판정하는 데 거듭제곱이 2번이면 끝나고, a¹·a²·a³ …을 1이 나올 때까지 곱해 보는 방법의 최대 6번과 비교됩니다.
위수의 분포
| 위수 d | 그런 원소 | φ(d) |
|---|---|---|
| 1 | 1개 | 1 |
| 2 | 1개 | 1 |
| 3 | 2개 | 2 |
| 6 | 2개 | 2 |
원시근이 있으면 φ(n)의 각 약수 d마다 위수가 d인 원소가 정확히 φ(d)개입니다. 두 열이 모두 맞아떨어지는 것이 곱셈군이 순환군이라는 증거이고, 계산 전체의 검산이기도 합니다.
원소별 위수
| a | 위수 | 원시근 |
|---|---|---|
| 1 | 1 | · |
| 2 | 3 | · |
| 3 | 6 | ○ |
| 4 | 3 | · |
| 5 | 6 | ○ |
| 6 | 2 | · |
어느 줄을 봐도 위수가 φ(n) = 6의 약수입니다. 이것이 라그랑주 정리이고, 위수를 값싸게 구할 수 있는 근거이기도 합니다.
계산 방법
- 1법 n을 넣습니다. 1부터 5,000까지 다룹니다.
- 2원시근이 있으면 가장 작은 것과 전체 목록이 나옵니다.
- 3가장 작은 원시근의 거듭제곱 한 바퀴에서 서로소인 수를 모두 훑는지 확인합니다.
- 4「위수의 분포」 표에서 그런 원소의 개수와 φ(d)를 견줍니다. 원시근이 있으면 두 열이 정확히 맞습니다.
- 5「원소별 위수」 표에서 모든 위수가 φ(n)의 약수인 것을 확인합니다.
자주 묻는 질문
거듭제곱만으로 n과 서로소인 수를 전부 만들어 내는 수입니다. a의 곱셈 위수(a^k ≡ 1이 되는 가장 작은 k)가 φ(n)과 같을 때 a를 원시근이라 합니다. 예를 들어 법 7에서 3은 원시근이라 3, 2, 6, 4, 5, 1로 1부터 6까지를 한 번씩 모두 훑습니다.
n = 1, 2, 4, 홀수 소수의 거듭제곱 pᵏ, 그리고 그 두 배인 2pᵏ일 때만 있습니다. 8, 12, 15, 16처럼 흔한 수에는 없습니다. 디피-헬만 키 교환이 소수를 법으로 쓰는 것도 그래야 원시근이 존재해 생성원으로 삼을 수 있기 때문입니다.
아닙니다. 위수는 언제나 φ(n)의 약수이므로(라그랑주 정리), φ(n)의 소인수 q마다 a^(φ(n)/q) ≡ 1인지만 물으면 됩니다. φ(n) = 408이면 408번이 아니라 소인수 2, 3, 17 세 개만 보면 되고, 거듭제곱 자체도 분할 제곱으로 로그 번이면 끝납니다. 이 계산기는 두 방법의 횟수를 나란히 보여 줍니다.
있을 때 정확히 φ(φ(n))개입니다. 원시근 하나를 g라 하면 나머지는 모두 g^k 꼴인데, 그 가운데 gcd(k, φ(n)) = 1인 k만 다시 원시근이 되기 때문입니다. 법 7이면 φ(φ(7)) = φ(6) = 2로, 3과 5 둘입니다.
원시근이 있으면 φ(n)의 각 약수 d마다 정확히 φ(d)개입니다. 이 성질은 곱셈군이 순환군일 때만 성립하므로, 위수 표를 세어 φ(d)와 맞춰 보면 계산 전체를 검산할 수 있습니다. 반대로 원시근이 없는 n에서는 두 열이 반드시 어긋납니다.
이 계산기는 원시근 자체가 목적이라 원시근 전체 목록과 모든 원소의 위수 표, 판정 비용까지 냅니다. 오일러 파이 함수 계산기는 φ(n)을 구하는 것이 목적이고 원시근은 존재 여부와 가장 작은 것만 곁들입니다. φ 계산은 두 도구가 같은 코드를 씁니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 n = 1부터 400까지의 모든 서로소 원소에 대해, 소인수를 덜어 내며 구한 위수가 a¹·a²·a³ …을 곧이곧대로 곱해 얻은 위수와 일치하는지 대조해 했습니다.
- 가장 작은 원시근은 널리 실려 있는 표(OEIS A046145)의 값과 맞췄습니다 — n = 41이면 6, 71이면 7, 191이면 19, 409면 21입니다. 원시근이 없는 8·12·16도 함께 고정했습니다.
- 원시근 개수가 φ(φ(n))과 같은지 n ≤ 400에서 실제로 세어 대조했고, 위수가 d인 원소가 φ(d)개라는 성질도 같은 범위에서 확인했습니다. 원시근이 없는 n에서는 이 성질이 반드시 깨지는 것도 함께 고정했습니다.
- φ 계산과 원시근 존재 판정은 오일러 파이 함수 계산기와 같은 코드(src/lib/calc/eulerTotient.ts)를 씁니다.
- n은 5,000까지 다룹니다. 모든 원소의 위수를 실제로 구해 표를 만들기 때문입니다. 표는 60줄까지, 원시근 목록은 60개까지 보입니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.