The following list of numbers is given: 21, 40, 59, 78, 97, . . . , 4562. Find the number of integers in this list whose HCF with 240 is not more than 1.
The following list of numbers is given: 21, 40, 59, 78, 97, . . . , 4562. Find the number of integers in this list whose HCF with 240 is not more than 1.
The correct option is C 64
The Euler's number ϕ(n) for 240 is given as:
ϕ(240)=240(1−12)(1−13)(1−15)=64 21, 40, 59, 78, 97, . . . , 4562 are in Arithmetic Progression with common difference as 19.
Number of terms =[(4562−21)19]+1
=(454119)+1=239+1=240
Now, applying the interesting property of numbers:
"If a is prime to n, the number of terms of the Arithmetic Progression x, x+a, x+2a, . . . , x+(n-1)a which are prime to n is ϕ(n).
ϕ(n) = no. of positive integers smaller than n and co-prime to n.
Hence the number of positive integers in the above list whose HCF with 240 is not greater than 1
= The number of positive integers in the list which are prime to 240=ϕ(240) = 64.
64
The Euler's number ϕ(n) for 240 is given as:
ϕ(240)=240(1−12)(1−13)(1−15)=6421, 40, 59, 78, 97, . . . , 4562 are in Arithmetic Progression with common difference as 19.
Number of terms =[(4562−21)19]+1
=(454119)+1=239+1=240
Now, applying the interesting property of numbers:
"If a is prime to n, the number of terms of the Arithmetic Progression x, x+a, x+2a, . . . , x+(n-1)a which are prime to n is ϕ(n).
ϕ(n) = no. of positive integers smaller than n and co-prime to n.
Hence the number of positive integers in the above list whose HCF with 240 is not greater than 1
= The number of positive integers in the list which are prime to 240=ϕ(240) = 64.
