NovaAdmin: DCWiki 복구: 최신본 이식

2026-01-08T08:00:14Z

DCWiki 복구: 최신본 이식

새 문서

{{사유화2}}
{{진지}}
{{이과}}
{{논문}}
{{괜찮은데?}}
{{착한문서}}

==개요==

오일러 φ함수는 당연히 오일러가 만들어낸 것이다.

정의는 다음과 같다.

<pre>자연수 n에 대하여, φ(n) = (n 이하의 자연수 중 n과 서로소인 자연수의 개수)</pre>

그니깐, 예를 하나 들자면 φ(10) = 4이다. (10 이하의 자연수 중 10과 서로소인 놈들은 1, 3, 7, 9로 4개이다.)

여기까지만 보면 어쩌라는 것인지 모를 수도 있다. 그런데 의외로 매우 유용하고, 정수론에서 우려먹는 사골곰국 1순위이다.

==성질==

(1) m, n이 [[서로소]]일 때, φ(mn) = φ(m)φ(n)이다.

(2) p가 소수일 때, φ(p) = p-1이다.

(3) p가 소수, k가 자연수일 때, φ(p^k) = p^k - p^(k-1)이다.

위의 성질 (3)이랑 (1)을 합치면 φ(n)을 구하는 공식 φ(n) = ∏(n−n/p) = n * ∏(1−1/p) 을 얻을 수 있다.

===증명===

(1)은 정의에 의해 쉽게 알 수 있고

(2)(3)은 p가 소수이므로 전체 n개 중에서 p의 배수인 것들의 개수 n/p를 빼준 값이 된다.

혹은 여기 참고 https://www.whitman.edu/mathematics/higher_math_online/section03.08.html

==오일러 정리==

얘가 거의 정수론에서 1짱 먹었다. 이 정리가 뭐냐면 다음과 같다.

<pre>서로소인 두 자연수 a, n에 대하여, a^φ(n) ≡ 1 (mod n)</pre>

얘로 인해서 페르마 정리가 증명되고, 2003^2002^2001의 마지막 세 자릿수를 물어보는 좆같은 문제도 풀어낼 수 있다.

===증명===

기약잉여계 등을 이용한 개씹좆같은 증명이다. 굳이 알지 않아도 됨.

아는 사람이 있다면 추가해줘라.

페르마의 소정리 참고하세요

==관련 문서==

[[φ]] 하이퍼 링크 다는 법을 모르겠다 https://wiki.dcinside.com/wiki/%E2%88%AE 여기로 이어줘라

[[페르마의 소정리]]

[[정수론]]

[[합동식]]

[[서로소]]

오일러 ∮함수 - 편집 역사

NovaAdmin: DCWiki 복구: 최신본 이식