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

  • 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
    @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