100 이하의 자연수 중 30과 서로소인 자연수의 개수를 구하는 문제는 정수론의 기본적인 개념을 활용하여 해결할 수 있습니다. 서로소라는 것은 두 자연수의 최대공약수(GCD)가 1일 때를 의미합니다. 따라서 30과 서로소인 자연수란 30과의 최대공약수가 1인 자연수를 말합니다. 30의 소인수분해를 통해 30의 약수들을 파악하고, 이 약수들을 공약수로 가지지 않는 수를 찾는 것이 핵심입니다.
먼저 30을 소인수분해하면 30 = 2 × 3 × 5가 됩니다. 즉, 30은 소인수 2, 3, 5를 가지고 있습니다. 30과 서로소인 자연수는 이 소인수 2, 3, 5를 공약수로 가지지 않는 자연수입니다. 이는 곧, 30과 서로소인 자연수는 2의 배수도 아니고, 3의 배수도 아니고, 5의 배수도 아닌 자연수라는 것을 의미합니다.
1부터 100까지의 자연수 중에서 30과 서로소인 자연수의 개수를 구하기 위해, 전체 자연수의 개수에서 30과 서로소가 아닌 자연수의 개수를 빼는 방식으로 접근할 수 있습니다. 30과 서로소가 아닌 자연수는 30과 최대공약수가 1보다 큰 자연수이며, 이는 30의 소인수인 2, 3, 5 중 적어도 하나를 공약수로 가지는 자연수입니다. 즉, 2의 배수, 3의 배수, 5의 배수인 자연수들을 먼저 파악해야 합니다.
전체 자연수는 100개입니다. 이제 2의 배수, 3의 배수, 5의 배수의 개수를 구한 후 포함-배제의 원리를 적용하여 30과 서로소가 아닌 자연수의 개수를 계산합니다. 100 이하의 자연수 중 2의 배수는 100 ÷ 2 = 50개, 3의 배수는 100 ÷ 3 = 33개, 5의 배수는 100 ÷ 5 = 20개입니다. 이들을 단순히 더하면 중복 계산이 발생하므로 포함-배제의 원리를 사용합니다.
먼저 2의 배수와 3의 배수의 교집합, 즉 6의 배수는 100 ÷ 6 = 16개입니다. 2의 배수와 5의 배수의 교집합, 즉 10의 배수는 100 ÷ 10 = 10개입니다. 3의 배수와 5의 배수의 교집합, 즉 15의 배수는 100 ÷ 15 = 6개입니다. 마지막으로 2, 3, 5의 모두의 배수, 즉 30의 배수는 100 ÷ 30 = 3개입니다.
포함-배제의 원리에 따라 2의 배수 또는 3의 배수 또는 5의 배수인 자연수의 개수는 다음과 같습니다. (2의 배수 개수 + 3의 배수 개수 + 5의 배수 개수) - (6의 배수 개수 + 10의 배수 개수 + 15의 배수 개수) + (30의 배수 개수)
= (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74개
이 74개는 100 이하의 자연수 중에서 30과 서로소가 아닌 자연수의 개수입니다. 따라서 100 이하의 자연수 중에서 30과 서로소인 자연수의 개수는 전체 자연수의 개수에서 30과 서로소가 아닌 자연수의 개수를 빼면 됩니다.
100 (전체 자연수 개수) - 74 (30과 서로소가 아닌 자연수 개수) = 26개
따라서 100 이하인 자연수 중에서 30과 서로소인 자연수는 총 26개입니다. 이 문제는 오일러의 토션트 함수(Euler's totient function, φ(n))를 활용하여 일반화할 수도 있습니다. φ(n)은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수를 나타냅니다. 30과 서로소인 100 이하의 자연수의 개수는 100 이하의 자연수 중에서 30의 배수가 아닌 수의 개수를 구하는 것과는 조금 다릅니다. 정확히는, 100 이하의 자연수 중에서 30과의 최대공약수가 1인 수의 개수를 구해야 합니다.