4
$\begingroup$

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

  • 1
    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$.2012-11-02
  • 5
    A misleading hint if ever there was one.2012-11-02
  • 0
    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.2012-11-02
  • 0
    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.2012-11-02
  • 0
    How does factoring $6042$ help? It's $3780$ that you need to factor.2012-11-02
  • 0
    @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?2012-11-02

2 Answers 2

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

  • 0
    But where did you use the $53$?2012-11-02
  • 0
    @RobertIsrael, sorry for the type error. But why must I use that hint. Is there anything wrong with the approach?2012-11-02
  • 0
    Nothing wrong with it. The actual question, though, was about the hint.2012-11-02
  • 0
    @RobertIsrael, is that the reason for down-voting? As "did" has already commented, some questions here are not hinted properly.2012-11-02
  • 0
    I downvoted an earlier answer that was a mess (and wrong - it had $t(i)t(j)$ instead of $t(ij)$, for example.)2012-11-02
  • 0
    @ThomasAndrews, thanks for your comment unlike many others do that w/o pointing out the mistake.2012-11-02
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$.

  • 0
    yes this seems like their aim2012-11-03