오일러 피 함수 편집하기
누리위키, 온 누리의 백과사전
편집을 되돌릴 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 저장해주세요.
최신판 | 당신의 편집 | ||
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\)이다. 이것을 수식으로 표현하면 다음과 같다: \[ \phi(n)=∣\{a\in \mathbb{N}|1\le a\le n,\;(a,n)=1\}∣.\] |
== 성질 == | == 성질 == | ||
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)\)을 다음과 같이 표현할 수 있다: \[\phi(n)=n\prod_{i=1}^k\left(1−\frac{1}{p_i}\right).\] |
== 같이 보기 == | == 같이 보기 == |