수학 원시근(Primitive root modulo n)

원시근(Primitive root modulo n)에 대해서 알아보겠습니다.

φ(n)의 집합 A가 있고, 원소로는 {a, b, c, d}를 포함하고 있을 때, a부터 d까지 차례로 원소 값 하나씩 거듭제곱하여(a, a², a³, ...) 양의 정수 n으로 나눴을 때, 나머지가 집합 A의 원소 값{a, b, c, d}을 전부 포함하고 있는 원소 값을 찾습니다.
만약 원소 b가 φ(n)의 값을 모두 가지게 된다면, b는 n의 원시근이 됩니다. ​





예시를 들어보겠습니다.
A = φ(5) = {1, 2, 3, 4}
​
​
1 (mod 5) = 1, 1 (mod 5) = 1 ..... 결과가 {1}
2( mod 5) = 2, 4 (mod 5) = 4, 8 (mod 5) = 3, 16 (mod 5) = 1, ... 결과가 {1, 2, 3, 4} (원시근)
3 (mod 5) = 3, 9 (mod 5) = 4, 27 (mod 5) = 2, 81 (mod 5) = 1, ... 결과가 {1, 2, 3, 4} (원시근)
4 (mod 5) = 4, 16 (mod 5) = 1, 64 (mod 5) = 4, ... 결과가 {1, 4}
​
2와 3만이 φ(5) 원소 {1, 2, 3, 4}가 나옵니다.
따라서, 2와 3은 5의 원시근입니다.
​
끝.

카테고리: Math