오일러 파이 함수2 서로소의 개수 2 (오일러 파이 함수) 서로소의 개수2자연수 \( n \) 이하 \( n \)과 서로소인 자연수의 개수를 구하는 아이디어는 지난 포스트에 언급하였다. 2024.06.01 - [수학] - 서로소의 개수 서로소의 개수\( n \)이하의 자연수 중에서 \( n \)과 서로소인 수의 개수를 세어보자. 예를 들어, \( n=10 \) 이라고 하면, 10 이하의 자연수 중에서 10과 서로소인 자연수는 다음과 같다. 1, 3, 7, 9여기에서 1은 모든conaninfotech.tistory.com 이번에는 이것을 쉽게 구하는 오일러 파이 함수를 소개한다. 자연수 \( n \)을 다음과 같이 소인수분해 하면,\( n=p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_r^{a_r} \; \; ( p_i는 \, 소수 ) .. 2024. 6. 3. 서로소의 개수 - 포함배제의 기본원리 서로소의 개수 (포함배제의 기본원리) \( n \)이하의 자연수 중에서 \( n \)과 서로소인 수의 개수를 세어보자. 예를 들어, \( n=10 \) 이라고 하면, 10 이하의 자연수 중에서 10과 서로소인 자연수는 다음과 같다. 1, 3, 7, 9여기에서 1은 모든 수의 약수인데, 왜 서로소인가 하는 의문이 들겠지만,1은 모든 수와 최대공약수가 1이므로 서로소이다. 10 이하의 자연수 중에서 아래의 논리로 생각해보자.(10과 서로소인 수 개수) = 10 - (10과 서로소가 아닌 수의 개수)= 10 - (2의 배수 또는 5의 배수인 수의 개수)= 10 - { (2의 배수 개수) + (5의 배수 개수) - (2와 5의 공배수 개수) }= 10 - { 5 + 2 - 1 }= 10 - 6= 4이다. 하나.. 2024. 6. 1. 이전 1 다음 반응형
