Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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$. –  amWhy Nov 2 '12 at 16:16
5  
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
show 1 more comment

2 Answers

$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

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
    
yes this seems like their aim –  cingoz recai Nov 3 '12 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.