최근 수정 시각 : 2022-04-05 18:07:19

오일러 피 함수

오일러 파이 함수에서 넘어옴
정수론
Number Theory
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법
산술
나눗셈 약수·배수 배수 · 약수( 소인수) · 소인수분해( 목록) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 부부수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버츠와 스위너톤-다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론 · 해석적 정수론
함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수· 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

특수함수
Special Functions
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="letter-spacing: -1px"
{{{#!wiki style="margin:-6px -1px -11px; word-break: keep-all"
적분 오차함수(error function) · 베타 함수( 불완전 베타 함수) · 감마 함수( 불완전 감마 함수 · 로그 감마 함수) · 타원 적분 · 야코비 타원 함수 · 지수 적분 함수 · 로그 적분 함수 · 삼각 적분 함수 · 쌍곡선 적분 함수 · 프레넬 적분 함수 · 구데르만 함수
미분방정식 르장드르 함수* · 구면 조화 함수 · 베셀 함수 · 에르미트 함수 · 라게르 함수 · 에어리 함수
역함수 브링 근호 · 람베르트 [math(W)] 함수 · 역삼각함수
급수 제타 함수 · 세타 함수 · 초기하함수 · 폴리로그함수 · 바이어슈트라스 타원 함수
정수론 소수 계량 함수 · 소인수 계량 함수 · 뫼비우스 함수 · 최대공약수 · 최소공배수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 바쁜 비버 함수
기타 헤비사이드 계단 함수 · 부호 함수 · 테트레이션( 무한 지수 탑 함수) · 집합 판별 함수 · 바닥함수 / 천장함수 · 허수지수함수 · 혹 함수
* 특수함수가 아니라 특정 조건을 만족시키는 다항함수이지만, 편의상 이곳에 기술했다. }}}}}}}}}}}}

1. 개요

오일러 피 함수(Euler phi function) 특수함수의 하나로, 정의는 다음과 같다.

[math(\displaystyle \phi(n) \equiv \sum_{m=1}^{n} (\bold{1}_{\{1\}} \circ \gcd)(m,\,n)\quad)]([math(n \in \mathbb{N})])

위에서 [math(\gcd)]는 최대공약수, [math(\bold{1}_{\{1\}})]는 서로소만을 취하기 위한 1만을 원소로 갖는 집합의 판별 함수이다.

이름대로 레온하르트 오일러가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 계단함수다.

몇가지 특수한 성질이 존재하는데, 그 중 하나는 서로소인 서로 다른 두 수 [math(a,b)]라는 조건을 걸 경우, 정수론적 함수[1]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다.

만약 [math(\gcd(a,\,b)=1)]이라면, [math(\phi(ab)=\phi(a)\phi(b))]

또, 임의의 소수 [math(p)]에 대하여, [math(\phi(p^n))]은 [math(1\leq a\leq p^n)]인 [math(a)]중 [math(p^n)]과 서로소인 수의 개수이며, [math(p^n)]는 [math(p)]만을 소인수로 가지기 때문에 자동적으로

[math(\displaystyle \phi(p^n)=p^{n}-\frac{p^{n}}{p}=p^{n}\left(1-\frac{1}{p}\right))]가 된다.

이 두 성질을 조합하면, 오일러 피 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다.
[math(\displaystyle a=\prod_{i=1}^n p_{i}^{k_{i}})]의 형태로 소인수분해할 수 있다고 두면
[math(\displaystyle \phi(a)=\phi\left(\prod_{i=1}^n p_{i}^{k_{i}}\right)=\prod_{i=1}^n \phi(p_{i}^{k_{i}})=\prod_{i=1}^n \left[p_{i}^{k_{i}}\left(1-\frac{1}{p_i}\right)\right])]

즉, [math(\displaystyle \phi(n)= n \prod_{p|n}\left(1-\frac {1}{p}\right))](단, [math(p)]는 소수)

또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, 뫼비우스 함수 [math(\mu)][2]를 이용하면 다음이 성립한다.
[math(\displaystyle\phi(n)=\sum_{n\mid d}\mu\left(\frac{n}{d}\right)d)]



[1] 정의역과 치역이 모두 정수, 혹은 정수의 부분집합인 함수 중에서 [math(f(ab)=f(a)f(b))]라는 성질을 지닌 함수를 의미한다. [2] 주어진 수가 소수의 거듭제곱을 인수로 가지고 있는지를 판정하는 함수다. 거듭제곱을 인수로 가지고 있다면 0, 거듭제곱이 없다면 소인수의 개수, 즉 소인수 계량 함수를 따져서 [math(\mu(n)=\left(-1\right)^{\omega(n)})]가 된다.