오일러 피 함수 편집하기

오일러 피 함수(Euler's totient function, φ 함수)는 주어진 양의 정수 n에 대하여, n과 서로소인 1 이상 n 이하의 양의 정수의 개수를 나타내는 산술 함수이다.
==명칭 및 표기==
오일러 피 함수는 영어로 Euler's totient function 또는 Euler's φ-function이라고 하며, 여기서 "totient"는 오직 이 함수의 값을 지칭하는 특수한 용어이다. 한국어에서는 이 함수를 보통 오일러 피 함수 또는 φ 함수(파이 함수)라고 부르며, 이는 수학적 표기 φ(n)에서 비롯된 관용적 표현이다. "토시엔트 함수" 또는 "토션트 함수"와 같은 음역 표현은 거의 사용되지 않으며, 한국어 수학 교육 및 학술 문헌에서도 정착되지 않은 용어이다.

오일러 피 함수는 두가지 표기가 사용되었다. ϕ(n)와 φ(n)인데, 수학자들의 공개 온라인 여론조사에서는 후자가 70% 정도 지지받았다.<ref>https://cims.nyu.edu/~tjl8195/survey/results.html#q5</ref> 
==정의==
오일러 피 함수 φ(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 암호 알고리즘의 키 생성 과정에서 사용된다.
*정수론에서 모듈러 역원 계산에 자주 사용된다.
*디지털 서명 및 인증 시스템 등에서 수학적 기반으로 활용된다.
==같이 보기==
*[[오일러 정리]]
*[[페르마의 소정리]]
*[[소수]]
*[[최대공약수]]
*[[RSA 암호화]]
==참고 문헌==
*Tom M. Apostol, *Introduction to Analytic Number Theory*, Springer-Verlag, 1976.
*Kenneth H. Rosen, *Elementary Number Theory and Its Applications*, Pearson, 2010.
==각주==
[[분류:수학]]
[[분류:보안]]