수학 원시근(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

댓글

이 블로그의 인기 게시물

Python urllib.parse.quote()

KiCad 시작하기 7 (FreeRoute 사용하기 2)

음악 총보(Score), 파트보(Part)

KiCad 시작하기 3 (새로운 소자 추가하기)

Forensics .pyc 파일 .py로 복구하기

Kivy 시작하기 12 (Pyinstaller로 exe 파일 만들기)

Android Compose automation for getting localized images to use on Play Store app image

딩기 요트 명칭

Android Default background color setting

Android App architecture: State holders and UI state