JEE Main 2021 (Online) 22nd July Evening ShiftQuestion 1
The sum of all the elements in the set $\{n\in\{1,2,\ldots,100\}\mid\text{H.C.F. of }n\text{ and }2040\text{ is }1\}$ is equal to $\_\_\_\_\_\_$ .
Permutation and Combination
Answer$1251$
Solution
Concept. H.C.F.$(n,2040)=1$ means $n$ has none of the prime factors of $2040$. Remove the multiples of those primes from $1+2+\dots+100$ by inclusion-exclusion. Formulas used. (1) $1+2+\dots+m=\frac{m(m+1)}{2}$(2) Sum of multiples of $d$ up to $100$: $S(d)=d\cdot\frac{m(m+1)}{2}$, $m=\lfloor 100/d\rfloor$(3) $|P\cup Q\cup R\cup T|=\sum|P|-\sum|P\cap Q|+\sum|P\cap Q\cap R|-|P\cap Q\cap R\cap T|$Step 1 - Factorise. $2040=2^3\cdot3\cdot5\cdot17$. So $n$ must not be divisible by $2,3,5$ or $17$. Step 2 - Total sum, by (1). $1+2+\dots+100=\frac{100\cdot101}{2}=5050$. Step 3 - Single primes, by (2). $S(2)=2\cdot\frac{50\cdot51}{2}=2550$, $S(3)=3\cdot\frac{33\cdot34}{2}=1683$ $S(5)=5\cdot\frac{20\cdot21}{2}=1050$, $S(17)=17\cdot\frac{5\cdot6}{2}=255$ Sum $=5538$. Step 4 - Pairs (products $\le 100$ only). $S(6)=6\cdot\frac{16\cdot17}{2}=816$, $S(10)=10\cdot\frac{10\cdot11}{2}=550$ $S(15)=15\cdot\frac{6\cdot7}{2}=315$, $S(34)=34\cdot\frac{2\cdot3}{2}=102$ $S(51)=51$, $S(85)=85$ Sum $=1919$. Step 5 - Triples. Only $2\cdot3\cdot5=30$ is $\le100$: $S(30)=30\cdot\frac{3\cdot4}{2}=180$. The others ($102,170,255$) and the four-fold product $510$ exceed $100$, so they give $0$. Step 6 - Use (3). Sum of numbers divisible by at least one prime $=5538-1919+180=3799$. Step 7 - Subtract. Required sum $=5050-3799=1251$. Answer: 1251