오일러 함수의 성질과 계산 방법
오일러 함수 φ(n)은 1부터 n까지 n과 서로 소인 수의 개수를 나타냅니다. 두 수 a와 b가 서로 소일 때 gcd(a,b)=1이 성립합니다.
재귀적 계산식
임의의 양의 정수 a에 대해 다음 식이 성립합니다:
φ(ab) = φ(a)×φ(b)×gcd(a,b)/φ(gcd(a,b))
a와 b가 서로 소일 경우 φ(ab) = φ(a)×φ(b)가 됩니다.
증명
n을 소인수 분해한 후 φ(n)을 계산하는 방식을 통해 증명할 수 있습니 ...
7월 11일 23:00에 게시됨