# Products in a Set

Let:

$$S := \{1,2,3,\dots,1337\}$$

and let $n$ be the smallest positive integer such that the product of any $n$ distinct elements in $S$ is divisible by $1337$. What are the last three digits of $n$?

I'm having a bit of trouble with this problem: the context is that my prof. gave this as a 'extra' exercise to me to do for fun.

Any help would be appreciated, thanks!

• I find it interesting that your prof gave it as an exercise, yet only asks for the "last three digits of $n$", as opposed to the value of $n$. This is very similar to a Brilliant problem that I just posed this week, where 1337 is replaced with 2013. – Calvin Lin Jun 18 '13 at 0:04
• That is pretty interesting, I didn't think to ask where he got the question from - I'll ask him next time I see him. – kvmu Jun 18 '13 at 6:02

$1337=7\times191$ and there are $190$ numbers with a factor of $7$ before $1337$ and $6$ numbers with a factor of $191$ before $1337$.
Suppose you've chosen all the numbers in the set except those that have a factor of either $7$ or $191$. That'd be $1337$ minus $1$ (for $1337$) minus $6$ (for numbers with factor $191$) minus $190$ (for numbers with factor $7$). $1337-1-6-190=1140$. Now the worst possible condition you can have is that you've chosen all the number that have a factor of $7$ but no number with a factor of $191$ which are $190$ in total. This essentially means that you have all the $7$s in the list but no number of factor $191$ to pair them up with $7$ resulting in some multiple of $1337$. So now you have $1140+190=1330$. Now you need any one of the remaining 7 numbers to get a product divisible by $1337$. So $1330+1=1331$. Therefore the last $3$ digits of $n$ are $331$.
Hint: A first step is to factor $1337$. Why does that help?
• So we factor 1337, to get the (7)(191) - this helps us determine the lower bound for $n$. But the problem requires a certainty that if we pick $n$ numbers from the set, it will definitely be divisible by $1337$. I can also determine that there are 190 numbers before 1337 that is divisible by 7 and 6 numbers before 1337 divisible by 191. For the product to be divisible by 1337, I need to pick one of both of those numbers that are divisible by 7 and 191 (at least). – kvmu Jun 17 '13 at 3:37