What is the maximum value of $n$ with average value must be an integer? 
Let $M$ be a positive integer greater than $1$. All integers from $1$ to $M$ were written on a board.
Each time we erase a positive integer on the board in a way that the average value of all numbers that have been erased must always be an integer.
Assume that there are $n$ numbers that have been erased ($1 \leq n \leq M$, $n$ is not a constant number). The process will end with $n$ numbers if and only if it is impossible to erase the $(n+1)th$ number so that the average value of $n+1$ erased numbers can be an integer.
For all possible ways to erase the numbers, what is the maximum and the minimum value that $n$ can reach?

For example, with $M=3$, we have the maximum of $n$ is $3$ (choose $a_1=1$, $a_2=3$, $a_3=2$ ) , the minimum value of $n$ is $1$ (choose $a_1=2$, then it is impossible to choose $a_2=1$ or $a_2=3$ because $\frac{2+1}{2}, \frac{2+3}{2}$ are not integers). For larger $n$, I thought that I can solve with Chinese Remainder Theorem, but I didn't know how to use it.
Is it possible to find the minimum or maximum value of $n$?. If not, what are the conditions of $M$ so that the minimum or maximum value of $n$ can be found?
(Sorry, English is my second language, so the questions may unclear for some readers)
 A: EDIT: I've edited the post because at first I did average as $\frac{1}{2}\sum a_i$ instead of $\frac{1}{i}\sum a_i$. Below is the corrected answer:

Modeling the problem for maximum or minimum we get:
\begin{align*}
\text{max/min }&\sum_{i=1}^{m}b_i\\
\text{such that }& b_11+b_22+\cdots+b_MM=Mk\\
&b_i\in\{0,1\},k\in\mathbb{N}
\end{align*}
Suppose $M=1$. We can erase the only value: $1$, and it's average is $\frac{1}{1}=1$ an integer. Therefore max=min=$1$.
Suppose $M=2$. We can only erase $2$, because $\frac{3}{2}\notin \mathbb{Z}$. Therefore max=min=$1$.
Now let's suppose $M\geq 3$. Let's see for what $M$'s we can erase all numbers, that is $n=M$:
$$
1+2+\cdots+M = \frac{M(M+1)}{2} = Mk \rightarrow M=2k-1
$$
Hence for $M\in\{3,5,7,9,\cdots\}$ we can erase all numbers to get it's average as an integer.
We've covered the cases for $M$ when it's odd and $M\geq 3$. Let's see what happens for the cases where $M$ is even, that is, $M=2q$.
$$
1+2+\cdots+2q = \frac{2q(2q+1)}{2} = q(2q+1) = 2q^2+q
$$
We want that result to be equal to $Mk=2qk$ for some $k \in \mathbb{N}$. Therefore if we let $b_q=0$ we get the sum as:
$$
1+2+\cdots + 2q - q = 2q^2+q - q = 2q^2
$$
And that is equal to $2qk$ for $k=q$. Therefore for $M=2q$ we get $n=M-1$.
That means that when $M=2q$ we only need $b_q=0$ to guarantee that the average of the sum of the erased numbers is an integer.
Finally see that for $M\geq 1$ you can always use the same reasoning for $M=1$ for the minimum... You remove $1$ and the average of the removed numbers is going to be $\frac{1}{1}=1$ that is an integer.
Since we've covered all cases for $M$, we're done.

Examples:
For $M=12345$:
$$
1 + 2 + \cdots + 12345 = 76205685 \text{ and } \frac{76205685}{12345}=6173
$$
For $M=124=2\cdot 62$:
$$
1 + 2 + \cdots + 124 - 62 = 7750 - 62 = 7688 \text{ and } \frac{7688}{124}=62
$$
