Movatterモバイル変換

[0]ホーム
URL:

본문으로 이동
위키백과
검색

오일러 피 함수

위키백과, 우리 모두의 백과사전.
오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다.

수론에서오일러 피 함수(-函數,영어:Euler’s phi (totient) function)는정수환의몫환의가역원을 세는함수이다. 즉,n이양의 정수일 때, ϕ(n)은n과서로소인 1부터n까지의 정수의 개수와 같다. 예를 들어, 1부터 6까지의 정수 가운데 1, 5 둘만 6과 서로소이므로, ϕ(6) = 2이다. 1부터 10까지의 정수는 모두 11과 서로소이며, 11은 자기 자신과 서로소가 아니므로, ϕ(11) = 10이다. 1은 자기 자신과 서로소이므로, ϕ(1) = 1이다.

정의

[편집]

양의 정수n{\displaystyle n}의오일러 피 함수ϕ(n){\displaystyle \phi (n)}은정수환의몫환Z/(n){\displaystyle \mathbb {Z} /(n)}의가역원군의 원소 개수이다. 즉, 1부터n{\displaystyle n}까지의 정수 가운데n{\displaystyle n}과서로소인 것들의 개수이다.

ϕ(n)=|(Z/(n))×|=|{k∈{1,…,n}:gcd{n,k}=1}|{\displaystyle \phi (n)=|(\mathbb {Z} /(n))^{\times }|=|\{k\in \{1,\dotsc ,n\}\colon \gcd\{n,k\}=1\}|}

성질

[편집]

오일러 피 함수는곱셈적 함수다. 즉, 만약 두 정수m,n{\displaystyle m,n}이 서로소라면, 다음이 성립한다.

ϕ(mn)=ϕ(m)ϕ(n){\displaystyle \phi (mn)=\phi (m)\phi (n)}

오일러 피 함수 값은소인수를 통해 다음과 같이 구할 수 있다. 이를오일러 곱 공식(영어:Euler product formula)이라고 한다.

ϕ(n)=n∏p∣n(1−1p){\displaystyle \phi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}

예를 들어, 20의 소인수는 2, 5이므로ϕ(20){\displaystyle \phi (20)}은 다음과 같이 구할 수 있다.

ϕ(20)=20(1−12)(1−15)=20×12×45=8{\displaystyle \phi (20)=20\left(1-{\frac {1}{2}}\right)\left(1-{\frac {1}{5}}\right)=20\times {\frac {1}{2}}\times {\frac {4}{5}}=8}

특히, 소수p{\displaystyle p}의 거듭제곱pk{\displaystyle p^{k}}의 오일러 피 함수 값은

ϕ(pk)=pk−1(p−1){\displaystyle \phi (p^{k})=p^{k-1}(p-1)}

이며, 소수p{\displaystyle p}의 값은

ϕ(p)=p−1{\displaystyle \phi (p)=p-1}

이다.

오일러 피 함수를 통해항등 함수를 다음과 같이 나타낼 수 있다. 이는레온하르트 오일러가 증명하였다.

∑d|nϕ(d)=n{\displaystyle \sum _{d|n}\phi (d)=n}

이는 분수1/n,2/n,…,n/n{\displaystyle 1/n,2/n,\dots ,n/n}들을 기약 분수 형태의 분모에 따라 묶어서 센 것으로 볼 수 있다. 이에뫼비우스 반전 공식을 가하면

∑d|ndμ(n/d)=ϕ(n){\displaystyle \sum _{d|n}d\mu (n/d)=\phi (n)}

을 얻는다 (μ{\displaystyle \mu }는뫼비우스 함수).

만약 양의 정수a,n{\displaystyle a,n}이 서로소라면, 다음과 같은 합동식이 성립한다. 이를오일러의 정리라고 한다.

aϕ(n)≡1(modn){\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}

값

[편집]

1부터 80까지의 정수의 오일러 피 함수 값은 다음과 같다. (OEIS의 수열A000010)

n1234567891011121314151617181920
ϕ(n)112242646410412688166188
n2122232425262728293031323334353637383940
ϕ(n)12102282012181228830162016241236182416
n4142434445464748495051525354555657585960
ϕ(n)4012422024224616422032245218402436285816
n6162636465666768697071727374757677787980
ϕ(n)6030363248206632442470247236403660247832

응용

[편집]

오일러 피 함수는 수학의 다양한 분야에서 등장한다. 예를 들어,군론에서는순환군Z/nZ{\displaystyle \mathbb {Z} /n\mathbb {Z} }의 가능한 생성원(generator)의 수는ϕ(n){\displaystyle \phi (n)}이다. 이는n{\displaystyle n}과 서로소인 임의의 수를 사용하여Z/nZ{\displaystyle \mathbb {Z} /n\mathbb {Z} }를 생성할 수 있기 때문이다.

또한,정n각형이작도 가능한 다각형인지, 즉눈금없는 자와 컴퍼스만으로 작도할 수 있는지는ϕ(n){\displaystyle \phi (n)}이 2의거듭제곱수인지와동치이다. 즉,

n = 2, 3, 4, 5, 6, 8, 10, …

이라면

ϕ(n){\displaystyle \phi (n)} = 1, 2, 2, 4, 2, 4, 4, …

이므로 정n각형을 작도할 수 있지만, 다른 값의 경우에는 작도할 수 없다. 특히,n이소수인 경우를페르마 소수라고 한다.

오일러 피 함수는암호학의RSA 암호에서도 핵심적인 역할을 한다.

같이 보기

[편집]

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=오일러_피_함수&oldid=39160676"
분류:
숨은 분류:
[8]ページ先頭
©2009-2025 Movatter.jp