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

Question

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 02 '12 at 16:16
I'm wondering if somehow they expected you to use that $253 = 35*7+1$ and reduce the problem to a smaller count. But I'm not seeing directly how to do that. — Thomas Andrews, Nov 02 '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. — GeoffDS, Nov 02 '12 at 19:59
How does factoring $6042$ help? It's $3780$ that you need to factor. — Robert Israel, Nov 02 '12 at 20:20
@RobertIsrael So, it's a bad hint. But, it's a much better explanation than assuming you're supposed to somehow use $53$ somewhere else in the problem. That's my point. The teacher did something stupid. It's not the first time a teacher has done it. It's not about some magic trick with the number 53. Why are we trying to find some explanation other than the obvious? — GeoffDS, Nov 02 '12 at 21:29

lab bhattacharjee · Answer 1 · 2012-11-02T18:34:24.170

2

$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

edited Nov 02 '12 at 18:34

answered Nov 02 '12 at 16:20

lab bhattacharjee

274,582

But where did you use the $53$? – Robert Israel Nov 02 '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 02 '12 at 16:30
Nothing wrong with it. The actual question, though, was about the hint. – Robert Israel Nov 02 '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 02 '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 02 '12 at 16:35
@ThomasAndrews, thanks for your comment unlike many others do that w/o pointing out the mistake. – lab bhattacharjee Nov 02 '12 at 16:37

Thomas Andrews · Answer 2 · 2012-11-02T19:49:25.900

2

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$.

edited Nov 02 '12 at 19:49

answered Nov 02 '12 at 16:59

Thomas Andrews

177,126

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

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

2 Answers2