Should I count them manually?

Find the value of the 80th smallest positive integer that is coprime to 9955.

Note: If A A is coprime to B B , then A A and B B don't share any common factor other than 1.


The answer is 109.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

First we note the prime factorization 9955 = 5 × 11 × 181. 9955 = 5 \times 11 \times 181.

So every positive integer that is not a positive multiple of any of 5 , 11 5,11 or 181 181 will be coprime to 9955. 9955. Assuming for the moment that the 80 80 th such coprime integer is less than 181 , 181, we are looking for the least positive integer N N such that

N ( N 5 + N 11 N 55 ) = 80. N - \left(\lfloor \dfrac{N}{5} \rfloor + \lfloor \dfrac{N}{11} \rfloor - \lfloor \dfrac{N}{55} \rfloor\right) = 80.

As a means of expediting a solution, suppose for the moment that N N is divisible by 55. 55. Then this equation becomes

N ( N 5 + N 11 N 55 ) = 80 40 N 55 = 80 N = 110. N - \left(\dfrac{N}{5} + \dfrac{N}{11} - \dfrac{N}{55}\right) = 80 \Longrightarrow \dfrac{40N}{55} = 80 \Longrightarrow N = 110.

So there are 80 80 integers less than or equal to 110 110 that are coprime to 9955. 9955. But since 110 110 itself is not coprime to 9955 , 9955, we can conclude that 109 \boxed{109} is in fact the 80 80 th smallest positive integer that is coprime to 9955. 9955.

Moderator note:

Does the formula f ( n ) = n ( n 5 + n 11 n 55 ) f(n) = n - \left ( \left \lfloor \frac n5 \right \rfloor + \left \lfloor \frac n{11} \right \rfloor - \left \lfloor \frac n{55} \right \rfloor \right ) work if I want to find the n th n^\text{th} coprime positive integer for any positive integer n n ?

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...