합동식의 거듭제곱은 단순히 지수가 반복되는 것이 아니라 유한한 곱셈군 안에서 주기를 이룬다. 이 주기를 order라고 하며, 하나의 원소가 모든 원소를 생성하면 primitive root가 된다.
Finite Group과 Cyclic Group
집합 와 연산 가 결합법칙, 항등원, 역원을 만족하면 group이다. 연산이 교환법칙까지 만족하면 Abelian group이다.
인 residue class들의 집합
은 곱셈에 대해 크기 인 유한 Abelian group이다.
원소 의 모든 정수 거듭제곱으로 군 전체를 만들 수 있으면
라고 하고 cyclic group이라 한다. 를 generator라고 한다.
Order of an Element
유한군에서 의 order는
이다. modulo 에서는 로 쓴다.
이면
이다. , 로 나누면 이고, 이것이 항등원이면 order의 최소성으로 이다.
Lagrange’s Theorem
유한군 의 부분군 의 크기는 를 나눈다. 특히 의 크기는 이므로
이다. 따라서
이며 Euler’s Theorem도 이 결과의 한 형태이다.
Order of a Power
이면
이다.
, , 라 하자. 이다. 더 작은 지수에서 항등원이 된다면 이고, 이므로 가 되어 최소값은 이다.
Primitive Root
이고
이면 를 modulo 의 primitive root라고 한다. 이때
은 reduced residue system 전체를 정확히 한 번 생성한다.
소수 에 대해 는 cyclic이므로 primitive root가 항상 존재한다.
Polynomial Congruence의 Root Bound
가 소수이고 가 modulo 에서 0이 아닌 degree 다항식이면 의 해는 최대 개이다.
증명은 한 근 가 있으면 field 위의 factor theorem으로 로 인수분해하고 induction을 적용한다. 이 정리는
의 해 개수를 제어하는 데 사용된다.
Order가 정확히 인 원소
이면 은 정확히 개의 해를 가진다. 한편 그 해들은 order가 의 약수인 원소들이다. order가 정확히 인 원소 수를 라 하면
이다. Gauss identity 와 비교하면
이다. 특히 primitive root의 개수는
이다.
Primitive Root Test
가 소인수분해되어 있다고 하자. 가 primitive root일 필요충분조건은 모든 서로 다른 소인수 에 대해
인 것이다. order는 의 약수이므로, 어떤 소인수 방향으로도 order가 줄어들지 않음을 확인하는 검사이다.
예를 들어 , 에서 은
이므로 order가 16이고 primitive root이다.
Primitive Root가 존재하는 법
양의 정수 이 primitive root를 가질 필요충분조건은
중 하나인 것이다. 여기서 는 홀수 소수이다.
완전한 증명은 여러 보조정리를 요구한다. 핵심 아이디어는 홀수 소수 의 primitive root 중 적절한 것을 로 lift한 뒤 induction으로 까지 order를 유지하는 것이다. 반대로 서로 다른 두 홀수 소인수를 갖거나 , 인 경우에는 Euler 함수 크기보다 모든 원소의 order가 작아져 generator가 존재하지 않는다.
정리
Order는 유한군에서 거듭제곱의 최소 주기이며 군의 크기를 나눈다. Primitive root는 reduced residue system 전체를 생성하는 원소이다. 소수 법의 곱셈군은 cyclic이고, order가 인 원소의 개수는 이다.
연습 문제
- 을 구한다.
- 을 공식으로 계산한다.
- 2가 modulo 11의 primitive root인지 판정한다.
풀이
1번
이므로 order는 3이다.
2번
이다. 실제로 이다.
3번
이므로 과 을 확인하면 된다.
이므로 2는 primitive root이다.