Euler’s phi function은 modulo 에서 곱셈 역원을 가지는 원소의 개수를 센다. 이 함수는 합동식의 주기를 결정하고 Fermat’s Little Theorem을 합성수 법으로 확장한다.
Euler’s Phi Function
로 정의한다. 예를 들어
이다. 가 소수이면 이 모두 와 서로소이므로 이다.
Prime Power의 phi 함수
중 와 서로소가 아닌 수는 정확히 의 배수이며 개이다. 따라서
이다.
Multiplicativity
이면
증명
Chinese Remainder Theorem에 의해
이다. residue 가 과 서로소일 필요충분조건은 가 과도, 과도 서로소인 것이다. 따라서 invertible residue의 선택은 두 법에서 독립적이며 개수는 곱이 된다.
이를 소인수분해에 적용하면
을 얻는다. 곱은 을 나누는 서로 다른 소수에 대해서만 취한다.
의 parity
이면 은 짝수이다. 가 과 서로소이면 도 서로소이고, 이면 이다. 가 invertible이므로 가 되어 에 모순이다. 따라서 원소들이 서로 다른 쌍 를 이룬다.
Reduced Residue System
modulo 에서 과 서로소인 나머지를 하나씩 모은 집합을 reduced residue system이라고 한다.
이면 도 reduced residue system의 순열이다. 실제로 두 항이 합동이면 를 약분할 수 있어 원래 두 항이 같아진다.
Euler’s Theorem
이면
증명
reduced residue system에 를 곱한 집합은 원래 집합의 순열이므로
이다. 각 는 과 서로소이므로 전체 곱을 약분하여 정리를 얻는다.
가 소수이면 이므로 Fermat’s Little Theorem이 된다.
큰 거듭제곱 계산
이면 지수를 modulo 으로 줄일 수 있다. 예를 들어 의 마지막 두 자리를 계산하면
이므로 이다.
단, 인 경우에는 Euler 정리를 그대로 적용하면 안 된다. 이때는 prime power별로 계산한 뒤 CRT를 사용하는 것이 안전하다.
Gauss’s Identity
증명
을 의 값에 따라 분할한다. 인 는 으로 쓸 수 있고
이다. 따라서 그러한 의 개수는 이다. 모든 약수 에 대해 합하면 개의 정수를 정확히 한 번씩 세므로 결과를 얻는다.
Reduced Residue의 합
일 때 reduced residue system의 원소를 최소 양의 나머지로 택하면
이다. 각 를 와 짝지으면 한 쌍의 합이 이기 때문이다.
Möbius Formula for phi
Gauss’s identity에 Möbius inversion을 적용하면
을 얻는다. 가 square-free 약수에 대해서만 0이 아니므로 소인수별로 곱을 전개하면 다시
이 나온다.
정리
Euler’s phi function은 invertible residue의 개수를 세며 prime power 공식과 multiplicativity로 계산된다. Reduced residue system에 서로소인 수를 곱하면 순열이 된다는 사실이 Euler’s Theorem의 핵심이다. Gauss identity와 Möbius inversion은 phi 함수를 약수합의 관점에서 다시 표현한다.
연습 문제
- 을 구한다.
- 을 40으로 나눈 나머지를 구한다.
- 를 직접 확인한다.
풀이
1번
이므로
이다.
2번
이고 이다. 이므로
이다.
3번
12의 약수는 이고 phi 값은 각각 이다. 합은 12이다.