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 25200 that are prime to 3600 .

(Observe that 25200 = 7 × 3600 .

Answers

Proof. Since k 3600 = 1 is equivalent to ( 3600 + k ) 3600 = 1 , there are as many integers prime with 3600 in [ [ 1 , 3600 ] ] than in [ [ 3601 , 7200 ] ] , and more generally than in [ [ K 3600 + 1 , ( K + 1 ) 3600 ] ] for all K .

Therefore, the number N 7 of positive integers 25200 that are prime to 3600 is

N 7 = 7 ϕ ( 3600 ) = 7 × 960 = 6720 .

For a more complete and more formal proof, see the generalization in Problem 25.

User profile picture
2024-08-11 17:34
Comments