12. (22 points) From the set $M=\{1,2, \cdots, 36\}$, remove $n$ numbers such that in the remaining elements, the sum of any two numbers is not a factor of 2015. Find the minimum value of $n$.


12. 17.

Notice that the sum of any two elements in set $M$ does not exceed 71.

Since $2015=5 \times 13 \times 31$, the positive divisors of 2015 that are not greater than 71 are $1, 5, 13, 31, 65$. Therefore, in the binary subsets of set $M$,
the pairs with a sum of 5 are $\{1,4\},\{2,3\}$;
the pairs with a sum of 13 are
$$
\begin{array}{l}
\{1,12\},\{2,11\},\{3,10\},\{4,9\}, \\
\{5,8\},\{6,7\} ;
\end{array}
$$

the pairs with a sum of 31 are
$$
\begin{array}{l}
\{1,30\},\{2,29\},\{3,28\},\{4,27\}, \\
\{5,26\},\{6,25\}, \cdots,\{15,16\} ;
\end{array}
$$

the pairs with a sum of 65 are
$$
\{29,36\},\{30,35\},\{31,34\},\{32,33\} \text {. }
$$

For a more intuitive understanding, we can draw a graph where each line segment connects two numbers from the above binary subsets, as shown in Figure 4.

To avoid forming these sums, at least one number from each pair (each line segment) must be deleted.

Thus, in Figure 4(a) and (b), at least four numbers must be deleted each, in Figure 4(c) and (d), at least two numbers must be deleted each, and in Figure 4(e), at least five numbers must be deleted, totaling at least 17 numbers.

On the other hand, by deleting 17 appropriate numbers, the remaining numbers can satisfy the condition. For example, in Figure 4(a), delete $12, 30, 4, 22$; in Figure 4(b), delete $11, 29, 3, 21$; in Figure 4(c), delete $23, 5$; in Figure 4(d), delete $24, 6$; in Figure 4(e), delete $13, 14, 15, 31, 32$. At this point, all the line segments in the graph have been broken.
(Tao Pingsheng provided)