편향성이 짙을 수도 있으니까 하루빨리 다른 놈이 찾아와서 채워줘라.
이과는 아다를 못 떼 마법을 쓰니까 말이죠...
그러나 표절과 주관적인 생각이 잔뜩 있을 가능성도 농후하니 알아서 거르시기 바랍니다.
또 고급스러운 언어유희와 필력까지 겸한 상질의 문서라 읽는 이로 하여금 뜨거운 감동을 자아냅니다.
잘하면 실질적인 정보를 얻을 수도 있고, 재밌어서 적어도 킬링타임 정도의 평타는 칠 수 있습니다.
시간이 나면 이 문서를 끝까지 정독해 보십시오.
문서를 읽기 전에 모니터나 액정 앞에서 따봉각을 치켜 세웁시다.
개요
오일러 φ함수는 당연히 오일러가 만들어낸 것이다.
정의는 다음과 같다.
자연수 n에 대하여, φ(n) = (n 이하의 자연수 중 n과 서로소인 자연수의 개수)
그니깐, 예를 하나 들자면 φ(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짱 먹었다. 이 정리가 뭐냐면 다음과 같다.
서로소인 두 자연수 a, n에 대하여, a^φ(n) ≡ 1 (mod n)
얘로 인해서 페르마 정리가 증명되고, 2003^2002^2001의 마지막 세 자릿수를 물어보는 좆같은 문제도 풀어낼 수 있다.
증명
기약잉여계 등을 이용한 개씹좆같은 증명이다. 굳이 알지 않아도 됨.
아는 사람이 있다면 추가해줘라.
페르마의 소정리 참고하세요
관련 문서
φ 하이퍼 링크 다는 법을 모르겠다 https://wiki.dcinside.com/wiki/%E2%88%AE 여기로 이어줘라