오일러 피 함수
IT 위키
오일러 피 함수(Euler's totient function, φ 함수)는 주어진 양의 정수 n에 대하여, n과 서로소인 1 이상 n 이하의 양의 정수의 개수를 나타내는 산술 함수이다.
명칭 및 표기[편집 | 원본 편집]
오일러 피 함수는 영어로 Euler's totient function 또는 Euler's φ-function이라고 하며, 여기서 "totient"는 오직 이 함수의 값을 지칭하는 특수한 용어이다. 한국어에서는 이 함수를 보통 오일러 피 함수 또는 φ 함수(파이 함수)라고 부르며, 이는 수학적 표기 φ(n)에서 비롯된 관용적 표현이다. "토시엔트 함수" 또는 "토션트 함수"와 같은 음역 표현은 거의 사용되지 않으며, 한국어 수학 교육 및 학술 문헌에서도 정착되지 않은 용어이다.
오일러 피 함수는 두가지 표기가 사용되었다. ϕ(n)와 φ(n)인데, 수학자들의 공개 온라인 여론조사에서는 후자가 70% 정도 지지받았다.[1]
정의[편집 | 원본 편집]
오일러 피 함수 φ(n)은 다음 조건을 만족하는 정수 k의 개수로 정의된다.
- 1≤k≤n
- gcd(k, n)=1
예를 들어, φ(9)=6이다. 이는 1부터 9까지의 수 중에서 9와 서로소인 수(1, 2, 4, 5, 7, 8)가 6개이기 때문이다.
성질[편집 | 원본 편집]
- n이 소수일 경우 φ(n) = n - 1이다.
- n이 서로소인 두 수 a, b의 곱일 경우 φ(ab) = φ(a)φ(b)이다. (곱셈적 함수)
- n의 소인수분해가 n = p₁^k₁ · p₂^k₂ · ... · pₙ^kₙ일 때,
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₙ)
계산 예시[편집 | 원본 편집]
- φ(1) = 1
- φ(2) = 1
- φ(5) = 4 (1, 2, 3, 4가 모두 5와 서로소)
- φ(10) = 4 (1, 3, 7, 9)
오일러 정리[편집 | 원본 편집]
오일러 피 함수는 오일러 정리와 밀접한 관련이 있다.
오일러 정리는 다음과 같이 표현된다: 서로소인 두 정수 a와 n(n>0)에 대해 a^φ(n) ≡ 1 (mod n)
이 정리는 페르마의 소정리를 일반화한 것으로, RSA 암호 알고리즘 등 수론 기반 암호 체계에 활용된다.
응용[편집 | 원본 편집]
- RSA 암호 알고리즘의 키 생성 과정에서 사용된다.
- 정수론에서 모듈러 역원 계산에 자주 사용된다.
- 디지털 서명 및 인증 시스템 등에서 수학적 기반으로 활용된다.
같이 보기[편집 | 원본 편집]
참고 문헌[편집 | 원본 편집]
- Tom M. Apostol, *Introduction to Analytic Number Theory*, Springer-Verlag, 1976.
- Kenneth H. Rosen, *Elementary Number Theory and Its Applications*, Pearson, 2010.
