경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!{{학술}} Euler's phi function, Euler's totient function <s>Euler's blood function이 아니다!</s> == 정수론에서 == 정수론에서 <math>\phi\left(n\right)</math>은 <math>n</math>보다 작거나 같은 양의 [[정수]] 중에서 <math>n</math>과 [[서로소]]인 수의 개수를 나타내는 함수다. 예를 들면, 6보다 작거나 같은 수 중에 6과 서로소인 수는 1, 5의 두 개 뿐이므로 <math>\phi\left(6\right)=2</math>가 된다. === 성질 === #임의의 양의 정수 <math>n</math>의 기약잉여계의 원소의 수는 <math>\phi\left(n\right)</math>이다. #<math>\gcd\left(a,n\right)=1</math>인 정수 <math>a</math>에 대해 <math>a^{\phi\left(n\right)}\equiv1\pmod n</math>이 성립한다. #<math>p</math>가 [[소수]]면, <math>\phi\left(p\right)=p-1</math>이다. 역도 성립한다. #소수 <math>p</math>에 대해 <math>\phi\left(p^a\right)=p^a-p^{a-1}</math>이다. #오일러 피 함수는 [[곱셈적 함수]]이다. 즉, 서로소인 양의 정수 <math>m,\,n</math>에 대해 <math>\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right)</math>가 성립한다. #<math>n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}</math>라 하자 (단, <math>p_i</math>는 서로 다른 소수, <math>a_i</math>는 [[자연수]]). 그럼 <math>\phi\left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)</math>이다. #<math>n> 2</math>이면 <math>\phi\left(n\right)</math>는 짝수다. #<math>m\mid n</math>이면 <math>\phi\left(m\right)\mid\phi\left(n\right)</math>이다. #<math>\phi\left(n^k\right)=n^{k-1}\phi\left(n\right)</math> #<math>\sum_{d\mid n}\phi\left(d\right)=n</math> === 증명 === #기약잉여계의 정의에 의해 자명하다. #[[오일러의 정리]] 참조. #쉬우므로 생략. {{ㅊ|증명은 독자에게 연습문제로 남긴다.}} #<math>p^a</math>와 서로소가 아닌 수는 <math>p</math>를 반드시 약수로 가져야 한다. 이는 곧 <math>p</math>의 배수를 의미하고, <math>p^a</math>보다 작거나 같은 <math>p</math>의 배수는 <math>p^a\div p=p^{a-1}</math>이다. <math>\therefore\phi\left(p^a\right)=p^a-p^{a-1}</math> #1부터 <math>mn</math>까지의 정수를 다음과 같이 나타내자. {|class=wikitable style=text-align:center |- |1||m+1||2m+1||…||(n-1)m+1 |- |2||m+2||2m+2||…||(n-1)m+2 |- |<math>\vdots</math>||<math>\vdots</math>||<math>\vdots</math>||||<math>\vdots</math> |- |r||m+r||2m+r||…||(n-1)m+r |- |<math>\vdots</math>||<math>\vdots</math>||<math>\vdots</math>||||<math>\vdots</math> |- |m||2m||3m||…||mn |} 만약 <math>\gcd\left(r,m\right)=d\neq1</math>이면, <math>d\mid r,\,d\mid m</math>이므로 <math>d\mid km+r</math>이다. 즉, <math>\gcd\left(km+r,mn\right)\geq d</math>. 따라서 <math>r</math>번째 줄은 <math>mn</math>과 서로소인 정수를 포함하고 있지 않다. 만약 <math>\gcd\left(r,m\right)=1</math>이면, <math>r</math>번째 줄에는 <math>r,\,m+r,\,2m+r,\,\cdots,\,\left(n-1\right)m+r</math>를 포함하고 있고, 이 수들은 <math>m</math>과 서로소이다. 만약 서로소가 아니라면, <math>d\neq1</math>인 <math>d</math>에 대해 <math>d\mid m,\,d\mid km+r</math>이므로 <math>d\mid r</math>이 되어 <math>d\mid\gcd\left(m,r\right)=1</math>이 되어 모순이다. 또한, 이 수들은 법 <math>n</math>에 대해 서로 다르다. 만약 <math>im+r\equiv jm+r\pmod n</math>이라면 <math>im\equiv jm\pmod n</math>이고, <math>\gcd\left(m,n\right)=1</math>이므로 <math>i\equiv j\pmod n</math>이다. 그런데 <math>0\leq i,\,j\leq n-1</math>이므로 <math>i=j</math>여야만 한다. 정리하면, 저 수들은 법 <math>n</math>에 대해 기약잉여계를 구성한다. 1번 성질에 의해, 저 수들 중에 <math>n</math>과 서로소인 수의 개수는 <math>\phi\left(n\right)</math>이다. 한편, 저런 수들의 집합은 <math>\phi\left(m\right)</math>개 존재한다.<br/><math>\therefore\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right)</math>. 6.<br/><math>\begin{align*}\phi\left(n\right)&=\phi\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right)\\&=\phi\left(p_1^{a_1}\right)\phi\left(p_2^{a_2}\right)\cdots\phi\left(p_k^{a_k}\right)\\&=\left(p_1^{a_1}-p_1^{a_1-1}\right)\left(p_2^{a_2}-p_2^{a_2-1}\right)\cdots\left(p_k^{a_k}-p_k^{a_k-1}\right)\\&=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\\&=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\end{align*}</math> 7. 6번 성질에서 <math>\phi\left(n\right)=\prod_{i=1}^{k}\left(p_i^{a_i}-p_i^{a_i-1}\right)=\prod_{i=1}^{k}p_i^{a_i-1}\left(p_i-1\right)</math>임을 알 수 있다. 그런데 <math>n> 2</math>이므로, <math>n</math>은 홀수인 소인수를 가지거나 소인수 2를 두 번 이상 가진다. 곧, 위 공식에서 <math>\phi\left(n\right)</math>가 짝수임을 유도할 수 있다. 8. <math>n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}</math> (<math>a_i</math>는 자연수)라 하면, <math>m\mid n</math>이므로 <math>m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}</math> (<math>a_i</math>는 음이 아닌 정수)가 된다. 6번 성질에서 <math>\phi\left(m\right)\mid\phi\left(n\right)</math>임이 바로 유도된다. 9. <math>n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}</math>라 하면, <math>n^k=p_1^{ka_1}p_2^{ka_2}\cdots p_m^{ka_m}</math>이다. 6번 성질을 적용하면 <math>\phi\left(n^k\right)=n^{k-1}\phi\left(n\right)</math>임이 바로 유도된다. 10. 1부터 <math>n</math>까지의 수를 다음과 같은 규칙에 의해 분류한다. :<math>\gcd\left(m,n\right)=d</math>이면 <math>m\in C_d</math> 그러면, <math>m\in C_d</math>이기 위한 필요충분 조건은 <math>\gcd\left(m/d,n/d\right)=1</math>임을 알 수 있다. 곧, <math>\left|C_d\right|=\phi\left(n/d\right)</math>이다. 또한, <math>C_d</math>는 <math>n</math>의 partition임을 알 수 있다. 따라서, <math>n=\sum_{d\mid n}\phi\left(n/d\right)</math>. 그런데 모든 약수 <math>d</math>에 대해 값을 더하므로, <math>\sum_{d\mid n}\phi\left(n/d\right)=\sum_{d\mid n}\phi\left(d\right)</math>.<br/><math>\therefore n=\sum_{d\mid n}\phi\left(d\right)</math> == 추상대수학에서 == [[추상대수학]]에서 오일러 피 함수는 조금 다르게 정의한다. 물론, 정수론적인 정의와 동치임을 증명할 것이다. 추상대수학 버전의 오일러 피 함수를 설명하기 전에 몇가지 용어를 정의한다. #nth root of unity: <math>z^n=1</math>인 [[복소수]] <math>z</math>를 말한다. #primitive nth root of unity: <math>\xi</math>가 nth root of unity이고, <math>n</math>이 <math>\xi^n=1</math>를 만족하는 가장 작은 양의 [[정수]]라면, <math>\xi</math>를 primitive nth root of unity라 부른다. #cyclotomic polynomial: <math>d</math>가 양의 정수일 때, dth cyclotomic polynomial을 <math>\Phi_d\left(x\right)=\prod\left(x-\xi\right)</math>로 정의한다. 여기서 <math>\xi</math>는 모든 primitive dth root of unity이다. 이제, 오일러 피 함수는 nth cyclotomic polynomial의 차수로 정의한다. 즉, <math>\phi\left(n\right)=\deg\left(\Phi_n\left(x\right)\right)</math>. === 성질과 증명 === #모든 nth root of unity <math>\xi</math>는 <math>e^{2\pi ik/n}=\cos\left(2\pi k/n\right)+i\sin\left(2\pi k/n\right)</math>과 동일하다 (<math>0\leq k\leq n-1</math>인 정수). #*<math>\xi=\cos\left(2\pi/n\right)+i\sin\left(2\pi/n\right)</math>라 하면, [[드 무아브르의 공식]]에 의해, <math>\xi^n=\left(\cos\left(2\pi/n\right)+i\sin\left(2\pi/n\right)\right)^n=\cos\left(2\pi\right)+i\sin\left(2\pi\right)=1</math> 이다. 즉, <math>\xi</math>는 nth root of unity이다. 또한, <math>k</math>가 정수라면, <math>\left(\xi^k\right)^n=\left(\xi^n\right)^k=1^k=1</math>이므로 <math>\xi^k</math> 역시 nth root of unity이다.<br/>역으로, <math>\xi</math>가 nth root of unity라 가정하자. <math>\left|\xi\right|=1</math>이므로, 적당한 <math>\theta</math>에 대해 <math>\xi=\cos\theta+i\sin\theta</math>이다. [[드 무아브르의 공식]]에 의해, <math>\xi^n=\cos n\theta+i\sin n\theta=1</math>이다. 이 식은 <math>n\theta=2k\pi</math>는 일 때 성립한다. 또한, <math>\cos</math>의 주기가 <math>2\pi</math>이므로 <math>0\leq k< n</math>이라 해도 된다. #<math>\xi</math>가 primitive dth root of unity라 가정하자. 만약 <math>\xi^n=1</math>이면, <math>d\mid n</math>이다. #*[[나눗셈 정리]]에 의해, <math>n=qd+r</math>, (<math>0\leq r< d</math>)이다. 그런데 <math>1=\xi^n=\xi^{qd+r}=\xi^{qd}\xi^r=\xi^r</math>이다. 만약 <math>r\neq0</math>이면, <math>d</math>가 <math>\xi^d=1</math>를 만족하는 가장 작은 양의 정수라는 사실에 모순된다. 따라서 <math>r=0</math>이고, <math>d\mid n</math>이다. #모든 [[자연수]] <math>n</math>에 대해, <math>x^n-1=\prod_{d\mid n}\Phi_d\left(x\right)</math>이다. #*각 <math>n</math>의 인수 <math>d</math>에 대해, <math>\prod\left(x-\xi\right)</math>를 모아 곱하면 된다 (<math>\xi</math>는 primitive dth root of unity). 1번과 2번 성질이 필요하다는 점에 주목. #모든 [[자연수]] <math>n</math>에 대해, <math>n=\sum_{d\mid n}\phi\left(d\right)</math>이다. #*<math>\phi\left(n\right)</math>이 <math>\Phi_n\left(x\right)</math>의 차수라는 점과, 3번 성질과, 다항식의 차수는 인수의 차수들의 합이라는 사실을 이용하면 유도된다. #<math>n</math>이 1이상인 [[정수]]일 때, <math>\phi\left(n\right)</math>는 <math>1\leq k\leq n,\,\gcd\left(k,n\right)=1</math>을 만족하는 정수 <math>k</math>의 개수이다. #*1번 성질에 의해 모든 nth root of unity는 <math>\xi=e^{2\pi ik/n}</math>이므로, <math>\xi</math>가 primitive란 것과 <math>\gcd\left(k,n\right)=1</math>라는 명제가 동치임을 보이면 된다.<br/>만약 <math>k,\,n</math>이 [[서로소]]가 아니라면, 1보다 큰 적당한 정수 <math>d</math>에 대해 <math>n=dr,\,k=ds</math>가 성립한다. 또한, <math>r< n</math>라는 것을 알 수 있다. 따라서 <math>\frac{k}{n}=\frac{s}{r}</math>이고, <math>\left(e^{2\pi ik/n}\right)^r=\left(e^{2\pi is/r}\right)^r=1</math>이므로 <math>e^{2\pi ik/n}</math>은 primitive nth root of unity가 아니다. <br/>역으로, <math>\gcd\left(k,n\right)=1</math>이라 가정하자. 그럼 적당한 정수 <math>s,\,t</math>에 대해 <math>sk+tn=1</math>이 성립한다. 한편, <math>\eta=e^{2\pi i/n}</math>라 정의하면, <math>\eta=e^{2\pi i/n}=e^{2\pi iks/n}e^{\pi int/n}=e^{2\pi iks/n}=\xi^s</math>이다. 만약 <math>1\leq d< n</math>이고 <math>\xi^d=1</math>인 <math>d</math>가 존재한다면 <math>\xi^{ds}=1=\eta^d</math>이다. 그런데 <math>\eta</math>는 primitive nth root of unity이므로 이는 모순이고, 조건을 만족하는 <math>d</math>는 존재하지 않음을 알 수 있다. 따라서 <math>\xi</math>는 primitive nth root of unity이다. {{ㅊ|'''뭔 개소리야'''}} {{각주}} [[분류:정수론]][[분류:추상대수학]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:ㅊ (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:취소선 (원본 보기) (준보호됨)