개수를 세는 함수
n=10이면 1, 3, 7, 9가 10과 서로소이므로 φ(10)=4다. 약수의 수를 세는 함수와 다르다. 3과 7은 10의 약수는 아니지만 10과 공약수가 1뿐이므로 개수에 포함된다.
소수와 소수의 거듭제곱
소수 p는 1부터 p−1까지의 모든 정수와 서로소이므로 φ(p)=p−1이다. 양의 정수 k에 대해 φ(pᵏ)=pᵏ−pᵏ⁻¹이다. pᵏ 이하의 수에서 p의 배수들을 제외하면 이 값을 얻는다.
소인수로 계산
서로 다른 소인수가 p₁부터 pᵣ인 n에 대해 φ(n)=n(1−1/p₁)…(1−1/pᵣ)이다. n=18에서는 소인수가 2와 3이므로 18×(1−1/2)×(1−1/3)=6이다. 같은 소인수를 거듭제곱 횟수만큼 반복해 곱하지 않는다.
역원의 개수와 연결
법 n에서 곱셈 역원이 있는 나머지는 n과 서로소인 것들이다. 따라서 n>1일 때 φ(n)은 0 이상 n 미만의 나머지 중 역원을 갖는 것의 수와 같다. 이 성질은 오일러 정리와 연결된다.
관련 문서
서로소 / 최대공약수 / 소수 (수론) / 소인수분해 / 거듭제곱 / 모듈러 역원 / 오일러 정리 (정수론) / 약수