"오일러 피 함수"의 두 판 사이의 차이
누리위키, 온 누리의 백과사전
(새 문서: '''오일러 피 함수'''(Euler's phi function) 또는 '''오일러 파이 함수''' \(\phi(n)\)이란 어떤 자연수 \(n\)보다 작거나 같은 자연수 중에서 \(n\)과 ...) |
잔글 (162.158.18.35(토론)의 편집을 티디의 마지막 판으로 되돌림) |
||
| (사용자 2명의 중간 판 2개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
| − | '''오일러 피 함수'''(Euler's phi function) 또는 '''오일러 파이 함수''' \(\phi(n)\)이란 어떤 [[자연수]] \(n\)보다 작거나 같은 자연수 중에서 \(n\)과 [[서로소(정수)|서로소]]인 것의 개수를 나타내는 함수이다. 예를 들어, \(\phi(8)=∣\{1,3,5,7\}∣=4\)이다. 이것을 수식으로 표현하면 다음과 같다: | + | '''오일러 피 함수'''(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> |
== 성질 == | == 성질 == | ||
| 7번째 줄: | 7번째 줄: | ||
* \(\phi(p^a)=p^a−p^{a−1}\). | * \(\phi(p^a)=p^a−p^{a−1}\). | ||
* \((m,n)=1\)이라면, \(\phi(mn)=\phi(m)\phi(n)\)이다. (오일러 피 함수는 [[곱셈적 함수]]이다.) | * \((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)\)을 다음과 같이 표현할 수 있다: | + | ** 이 성질을 이용하면 어떤 자연수 \(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> |
== 같이 보기 == | == 같이 보기 == | ||
2017년 5월 21일 (일) 19:36 기준 최신판
오일러 피 함수(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]
