|
|
1번째 줄: |
1번째 줄: |
− | '''오일러 피 함수'''(Euler's phi function) 또는 '''오일러 파이 함수''' \(\phi(n)\)이란 어떤 [[자연수]] \(n\)보다 작거나 같은 자연수 중에서 \(n\)과 [[서로소(정수)|서로소]]인 것의 개수를 나타내는 함수이다. 예를 들어, \(\phi(8)=∣\{1,3,5,7\}∣=4\)이다. 이것을 수식으로 표현하면 다음과 같다: <math> \phi(n)=∣\{a\in \mathbb{N}|1\le a\le n,\;(a,n)=1\}∣.</math>
| |
| | | |
− | == 성질 ==
| |
− | \(p\)는 [[소수(자연수)|소수]]라고 하자.
| |
− | * \(\phi(p)=p−1\).
| |
− | ** 역으로, \(\phi(n)=n−1\)이라면, \(n\)은 소수이다.
| |
− | * \(\phi(p^a)=p^a−p^{a−1}\).
| |
− | * \((m,n)=1\)이라면, \(\phi(mn)=\phi(m)\phi(n)\)이다. (오일러 피 함수는 [[곱셈적 함수]]이다.)
| |
− | ** 이 성질을 이용하면 어떤 자연수 \(n\)의 소인수 분해가 \(n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}\)라면, \(\phi(n)\)을 다음과 같이 표현할 수 있다: <math>\phi(n)=n\prod_{i=1}^k\left(1−\frac{1}{p_i}\right).</math>
| |
− |
| |
− | == 같이 보기 ==
| |
− | * [[오일러의 정리]]
| |
− | * [[곱셈적 함수]]
| |
− |
| |
− | [[분류:수학]]
| |
− | [[분류:수론]]
| |