Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 2.3.13 (Number of positive integers $\leq 25200$ prime to $3600$)
Exercise 2.3.13 (Number of positive integers $\leq 25200$ prime to $3600$)
Find the number of positive integers that are prime to .
(Observe that .
Answers
Proof. Since is equivalent to , there are as many integers prime with in than in , and more generally than in for all .
Therefore, the number of positive integers that are prime to is
□
For a more complete and more formal proof, see the generalization in Problem 25.