# How many numbers between $1$ and $6042$ (inclusive) are relatively prime to $3780$?

How many numbers between $1$ and $6042$ (inclusive) are relatively prime to $3780$?

Hint: $53$ is a factor.

Here the problem is not the solution of the question, because I would simply remove all the multiples of prime factors of $3780$.

But I wonder what is the trick associated with the hint and using factor $53$.

-
Note: 53 is one of four prime factors of 6042: $6042=2\cdot3\cdot19\cdot53$. Note also that $3780 =2^2\cdot3^3\cdot5\cdot7$. – amWhy Nov 2 '12 at 16:16
A misleading hint if ever there was one. – Did Nov 2 '12 at 16:21
I'm wondering if somehow they expected you to use that $2*53 = 3*5*7+1$ and reduce the problem to a smaller count. But I'm not seeing directly how to do that. – Thomas Andrews Nov 2 '12 at 16:51
Perhaps the hint is there just so you can finish the factoring. You could easily see the 2 and then the 3 and then you're left to figure out how to factor 1007. Not incredibly hard since you just need to try 2, 3, 5, 7, 11, 13, 17, and then 19. But, it is helpful. – Graphth Nov 2 '12 at 19:59
How does factoring $6042$ help? It's $3780$ that you need to factor. – Robert Israel Nov 2 '12 at 20:20

$3780=2^2\cdot3^3\cdot5\cdot7$

Any number that is not co-prime with $3780$ must be divisible by at lease one of $2,3,5,7$

Let us denote $t(n)=$ number of numbers$\le 6042$ divisible by $n$

$t(2)=\left\lfloor\frac{6042}2\right\rfloor=3021$

$t(3)=\left\lfloor\frac{6042}3\right\rfloor=2014$

$t(5)=\left\lfloor\frac{6042}5\right\rfloor=1208$

$t(7)=\left\lfloor\frac{6042}7\right\rfloor=863$

$t(6)=\left\lfloor\frac{6042}6\right\rfloor=1007$

Similarly, $t(30)=\left\lfloor\frac{6042}{30}\right\rfloor=201$

and $t(2\cdot 3\cdot 5\cdot 7)=\left\lfloor\frac{6042}{210}\right\rfloor=28$

The number of number not co-prime with $3780$

=$N=\sum t(i)-\sum t(i\cdot j)+\sum t(i\cdot j \cdot k)-t(i\cdot j\cdot k \cdot l)$ where $i,j,k,l \in (2,3,5,7)$ and no two are equal.

The number of number coprime with $3780$ is $6042-N$

Reference: Venn Diagram for 4 Sets

-
But where did you use the $53$? – Robert Israel Nov 2 '12 at 16:29
@RobertIsrael, sorry for the type error. But why must I use that hint. Is there anything wrong with the approach? – lab bhattacharjee Nov 2 '12 at 16:30
Nothing wrong with it. The actual question, though, was about the hint. – Robert Israel Nov 2 '12 at 16:32
@RobertIsrael, is that the reason for down-voting? As "did" has already commented, some questions here are not hinted properly. – lab bhattacharjee Nov 2 '12 at 16:33
I downvoted an earlier answer that was a mess (and wrong - it had $t(i)t(j)$ instead of $t(ij)$, for example.) – Thomas Andrews Nov 2 '12 at 16:35

Maybe they wanted you to rewrite $$6042 = 2\cdot53 \cdot3\cdot19 = (105+1)(56+1) = 2^3\cdot 3\cdot5\cdot 7^2 + 105 + 56 + 1$$

It's easy to compute the numbers from $1$ to $N=2^3\cdot3\cdot5\cdot 7^2$ relatively prime to $m=2\cdot 3\cdot5\cdot 7$ via $\frac{\phi(m)N}{m}=2^2\cdot 2 \cdot 4 \cdot 6\cdot 7$.

You now only have to count the ones from $1$ to $105+56+1 = 162$ which are relatively prime to $m$.

-
yes this seems like their aim – cingoz recai Nov 3 '12 at 14:56