|
정수론 Number Theory |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수· 배수 | 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 모듈러 역원 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론( 국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
|
특수함수 Special Functions |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
<colbgcolor=#383B3D><colcolor=#fff> 적분 | 오차함수(error function)( 가우스 함수 · 가우스 적분 함수) · 베타 함수( 불완전 베타 함수) · 감마 함수( 불완전 감마 함수 · 로그 감마 함수) · 타원 적분 · 야코비 타원 함수 · 지수 적분 함수 · 로그 적분 함수 · 삼각 적분 함수 · 쌍곡선 적분 함수 · 프레넬 적분 함수 · 구데르만 함수 |
| 미분방정식 | 르장드르 함수[math(^\ast)] ( 구면 조화 함수) · 베셀 함수 · 에르미트 함수 · 라게르 함수 · 에어리 함수 | |
| 역함수 | 브링 근호 · 람베르트 W 함수 · 역삼각함수 | |
| 급수 | 제타 함수 · 후르비츠 제타 함수 · 세타 함수 · 초기하함수 · 폴리로그함수 · 폴리감마 함수 · 바이어슈트라스 타원 함수 | |
| 정수론 | 소수 계량 함수 · 소인수 계량 함수 · 뫼비우스 함수 · 최대공약수 · 최소공배수 · 약수 함수 · 오일러 피 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 바쁜 비버 함수 | |
| 기타 | 헤비사이드 계단함수 · 부호 함수 · 테트레이션( 무한 지수 탑 함수) · 지시함수 · 바닥함수 / 천장함수 · 허수지수함수 · 혹 함수 | |
| [math(^\ast)] 특수함수가 아니라 특정 조건을 만족시키는 다항함수이지만, 편의상 이곳에 기술했다. | ||
1. 개요
오일러 피 함수(Euler phi function, Euler totient function)는 특수함수의 하나로, 자연수 [math(n)]에 대해 다음과 같이 정의된다.[math(\varphi(n) = |\{m: 1\le m\le n, \gcd(m,n)=1\}|)]
이름대로 레온하르트 오일러가 정의한 함수다. 위에서 [math(\gcd)]는 최대공약수이고, 따라서 [math(\phi(n))]은 [math(n)]과 서로소인 [math(n)] 이하의 자연수의 개수이다.
2. 성질
이 함수는 다양한 성질을 지니고 있다. 첫째로, [math(\varphi)]는 곱셈적 함수(multiplicative function)이다. 즉, 서로소인 두 자연수 [math(a)], [math(b)]에 대해[math(\varphi(ab) = \varphi(a) \,\varphi(b))]
이다. 증명은 [math(\gcd(a,b) = 1)]일 때 [math(\gcd(m,ab) = 1\iff \gcd(m,a) = \gcd(m,b) = 1)] 임을 이용하면 간단히 할 수 있다. 하지만 완전 곱셈적 함수(completely multiplicative function)는 아니다. 즉, 모든 자연수 [math(a)], [math(b)]에 대해 [math(\varphi(ab) = \varphi(a) \,\varphi(b))]가 성립하는 건 아니다. 간단한 예시로 [math(\varphi(2\cdot2) = 2 \neq 1\cdot1 = \varphi(2) \,\varphi(2))]가 있다.
둘째로, 임의의 소수 [math(p)]에 대하여 [math(\varphi(p^n))]은 [math(1 \leq a \leq p^n)]인 [math(a)] 중 [math(p^n)]과 서로소인 수의 개수이며, [math(p^n)]는 [math(p)]만을 소인수로 가지기 때문에 다음이 성립한다.
[math(\displaystyle \varphi(p^n) = p^n-p^{n-1} = p^n \biggl( 1-\frac1p \biggr))]
이 두 성질을 조합하면, 오일러 피 함수를 다음과 같은 식으로 표현할 수 있다. 자연수 [math(n)]이 [math(\displaystyle n = \prod_{i=1}^r {p_i}^{k_i})]로 소인수분해 될 때, 다음이 성립한다.
[math(\displaystyle \varphi(n) = \varphi \Biggl( \prod_{i=1}^r {p_i}^{k_i} \Biggr) \!= \prod_{i=1}^r \varphi({p_i}^{k_i}) = \prod_{i=1}^r \biggl[ {p_i}^{k_i} \biggl( 1-\frac1{p_i} \biggr) \biggr])]
즉, [math(\displaystyle \varphi(n) = n \prod_{p\mid n} \biggl( 1-\frac1p \biggr))]이다.
한 가지 흥미로운 공식은
[math(\displaystyle n = \sum_{d\mid n}\varphi\left(d\right))]
이라는 것이다. 증명은 [math(\{1, 2, \cdots, n\})] 을 [math(S_k = \{1\le m\le n:\gcd(m, n)=k\})]로 분할하여 할 수 있다. [math(\gcd(m, n)=k\iff \gcd\left(\frac{m}{k}, \frac{n}{k}\right) = 1)] 이고, [math(1\le m\le n\iff \frac{m}{k}\le\frac{n}{k})]이므로, [math(|S_k| = \varphi\left(\frac{n}{k}\right))]이다. 따라서,
[math(\displaystyle n = \sum_{k\mid n}|S_k| = \sum_{k\mid n}\varphi\left(\frac{n}{k}\right) = \sum_{d\mid n}\varphi(d))] 이다.
여기에 뫼비우스 반전 공식(Möbius inversion formula)을 적용하면, 뫼비우스 함수 [math(\mu)][1]를 포함한 다음 공식이 성립한다.
[math(\displaystyle\varphi(n)=\sum_{d\mid n}d\mu\left(\frac{n}{d}\right)=\sum_{d\mid n}\mu\left(d\right)\frac{n}{d})]
2.1. 계산 예시
[math( n = 12 )]일때 소인수 [math( (p) = 2,3 )][math( \varphi(12) = 12\prod\limits_{p /12} \left( 1- \dfrac{1}{p} \right) )]
[math( \varphi(12) = 12 \left( 1- \dfrac{1}{2} \right)\left( 1- \dfrac{1}{3} \right) )]
[math( \varphi(12) = 12 \left( \dfrac{1}{2} \right)\left( \dfrac{2}{3} \right)=4 )]
2.2. 토션트 합 함수
토션트 합 함수(Totient Summatory Function)는 오일러 피 함수 [math( \varphi(n) )]의 합으로 정의된다. 이 함수는 주어진 [math( n )]까지의 모든 [math( \varphi(k) )]값을 누적 합한 값을 나타낸다.[2]토션트 합 함수([math( \Phi(n) )],Totient Summatory Function) 의 정의
[math(\Phi(n)= \sum\limits_{k=1}^{n} \varphi(k) )]
2.2.1. 근사식 계산
[math(\Phi(n)= \sum\limits_{k=1}^{n} \varphi(k) \quad )] -(1)
우선 [math( \varphi(k) = k\prod\limits_{p/k}\left( 1-\dfrac{1}{p} \right) )]
따라서
(2)에 대해서 평균적인 비율을 가정하면 [math( k )]가 모든 자연수에 대해 평균적이므로 이 값을 구하려면, 우선 [math( \varphi(k) = k\prod\limits_{p/k}\left( 1-\dfrac{1}{p} \right) )]
따라서
[math( \dfrac{\varphi(k)}{k} = \prod\limits_{p/k}\left( 1-\dfrac{1}{p} \right) \quad )] -(2)
(2)은 [math( k )]이하의 정수 중 [math( k )]와 서로소[math( p )]인 정수의 비율을 보여준다.
(2)은 [math( k )]이하의 정수 중 [math( k )]와 서로소[math( p )]인 정수의 비율을 보여준다.
[math( k )]의 소인수 분포를 고려함으로써 [math( k )]가 특정 소수 [math( P )]에 대해 독립적으로 영향을 받는다고 가정할수있게된다. 따라서 모든 소수 [math( P )]에 대한 무한곱의 형태
[math( \prod\limits_{P}\left( 1-\dfrac{1}{P^2} \right) =\dfrac{\varphi(k)}{k} \quad )] -(3)
얻을수있다.
(3)을 (1)에 대입하면
[math( \Phi(n)= \sum\limits_{k=1}^{n} \varphi(k) = \sum\limits_{k=1}^{n} k\prod\limits_{P}\left( 1-\dfrac{1}{P^2} \right) \quad )] -(4)
[math( \sum\limits_{k=1}^{n} k = 1+2+3+4+ \cdots + n = \dfrac{n(n+1)}{2} \quad )] -(5)
[math( \prod\limits_{P}\left( 1-\dfrac{1}{P^2} \right) = \dfrac{1}{\zeta(2)} = {\zeta(2)}^{-1} = \left( \sum\limits_{k=1}^{\infty} \dfrac{1}{k^2} \right)^{-1} = \left(\dfrac{\pi^2}{6} \right)^{-1} = \left(\dfrac{6}{\pi^2} \right) \quad )] -(6)
(5),(6)을 (4)에 대입하면
[math( \Phi(n)= \dfrac{n(n+1)}{2} \left(\dfrac{6}{\pi^2} \right) )]
[math( n \rightarrow \infty 일때 n +1 \approx n)]을 가정하고
[math( \Phi(n)= \dfrac{n^2}{2} \left(\dfrac{6}{\pi^2} \right) = \dfrac{3}{\pi^2}n^2 )] 를 조사할수있다.
[math( \sum\limits_{k=1}^{n} k = 1+2+3+4+ \cdots + n = \dfrac{n(n+1)}{2} \quad )] -(5)
[math( \prod\limits_{P}\left( 1-\dfrac{1}{P^2} \right) = \dfrac{1}{\zeta(2)} = {\zeta(2)}^{-1} = \left( \sum\limits_{k=1}^{\infty} \dfrac{1}{k^2} \right)^{-1} = \left(\dfrac{\pi^2}{6} \right)^{-1} = \left(\dfrac{6}{\pi^2} \right) \quad )] -(6)
(5),(6)을 (4)에 대입하면
[math( \Phi(n)= \dfrac{n(n+1)}{2} \left(\dfrac{6}{\pi^2} \right) )]
[math( n \rightarrow \infty 일때 n +1 \approx n)]을 가정하고
[math( \Phi(n)= \dfrac{n^2}{2} \left(\dfrac{6}{\pi^2} \right) = \dfrac{3}{\pi^2}n^2 )] 를 조사할수있다.