Let S={1,2,3,4,…,2013} and let n be the smallest positive integer such that the product of any n distinct elements in S is divisible by 2013. What are the last 3 digits of n?
To find the last 3 digits of n, we need to determine the value of n.
First, let's analyze the number 2013. Its prime factorization is: 3 * 11 * 61.
For the product of any n distinct elements in S to be divisible by 2013, we need to consider the prime factors of 2013. This means that for each prime factor, we need to have at least one element from S that has that prime factor.
Let's start with the prime factor 3. Since 3 is one of the elements in S, we already have a number with the factor 3.
Next, let's consider the prime factor 11. In order to ensure that the product of any n distinct elements in S is divisible by 2013, we need to have at least one number with the factor 11. Looking at the set S, the numbers that have the factor 11 are: 11, 22, 33, ... , 2013. So we have 2013 / 11 = 183 numbers with the factor 11.
Lastly, let's consider the prime factor 61. Similarly, we need to have at least one number with the factor 61. Looking at the set S, the numbers that have the factor 61 are: 61, 122, 183, ..., 2013. So we have 2013 / 61 = 33 numbers with the factor 61.
Now, to find the value of n, we need to take the maximum count of these prime factors: 1 (for factor 3), 183 (for factor 11), and 33 (for factor 61). Therefore, n = 1 * 183 * 33 = 6039.
The last 3 digits of 6039 are 039, so the answer is 039.