오일러 ∮함수
조무위키
편향성이 짙을 수도 있으니까 하루빨리 다른 놈이 찾아와서 채워줘라.
|
주의. 이 문서는 심히 진지하여 노잼일 수 있습니다. 이 글은 놀랍게도 조무위키에서 진지를 빨고 있습니다. 노잼이다 싶으시면 여기를 클릭하시어 이 문서를 탈출할 수 있습니다. |
|
이 문서는 이과가 작성했거나, 또는 이과에 대해 다룹니다. 무슨 생각으로 작성한 건지는 잘 모르겠습니다만 맞는말임은 틀림 없습니다. 이과는 아다를 못 떼 마법을 쓰니까 말이죠... |
|
이 문서는 조무위키의 논문입니다! 이 문서는 조무위키의 히키새끼들이 합작해 길이와 내용, 전문성이 썩 나쁘진 않은 문서입니다. 그러나 표절과 주관적인 생각이 잔뜩 있을 가능성도 농후하니 알아서 거르시기 바랍니다. |
|
이 문서는 놀랍게도 조무위키치고는 괜찮은 문서입니다. 정말 놀랍게도! 이 문서는 조무위키 문서임에도 의외로 정밀하고, 적당한 양식을 갖추었습니다. 또 고급스러운 언어유희와 필력까지 겸한 상질의 문서라 읽는 이로 하여금 뜨거운 감동을 자아냅니다. 잘하면 실질적인 정보를 얻을 수도 있고, 재밌어서 적어도 킬링타임 정도의 평타는 칠 수 있습니다. 시간이 나면 이 문서를 끝까지 정독해 보십시오. |
|
문서를 읽기 전에 모니터나 액정 앞에서 따봉각을 치켜 세웁시다. |
|
개요[편집]
오일러 φ함수는 당연히 오일러가 만들어낸 것이다.
정의는 다음과 같다.
자연수 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 여기로 이어줘라