+0

# Number Theory

0
137
2

How many integers between 1 and 1,000,000 are relatively prime to $$60$$.

Apr 16, 2022

#1
0

i=0;a=1;b=1000000;c=60;cycle:d=a;if(gcd(c,d)==1,goto end, goto next);end:print d,", ",;i++; next: a=a+1;if(a<=b, goto cycle, 0);print"Total No. of coprimes ==", i

OUTPUT==266,666 integers between 1 and 1,000,000 that are relatively prime to 60

Apr 16, 2022
#2
+1

For an integer to be relatively prime to 60, it has to be:

(i) not divisible by 2

(ii) not divisible by 3

(iii) not divisible by 5

By inclusion-exclusion principle and using the fact that $$\text{# of integers in }[1, N]\text{ divisible by }k = \left\lfloor\dfrac{N}k\right\rfloor$$,

$$\begin{array}{cl} &\text{# of numbers relatively prime to 60}\\ =& 1000000 - \left\lfloor\dfrac{1000000}2\right\rfloor - \left\lfloor\dfrac{1000000}3\right\rfloor - \left\lfloor\dfrac{1000000}5\right\rfloor + \left\lfloor\dfrac{1000000}6\right\rfloor + \left\lfloor\dfrac{1000000}{10}\right\rfloor + \left\lfloor\dfrac{1000000}{15}\right\rfloor-\left\lfloor\dfrac{1000000}{30}\right\rfloor \\=&266666\end{array}$$

Apr 16, 2022
edited by MaxWong  Apr 16, 2022