Prime modulo maximum Prove that the remainder of division of a positive number $n$ by a prime $p \le n$ is maximized when $p$ is the smallest prime larger than $\frac{n}{2}.$  
It is easy to see that for any number of the form $\frac{n}{2}+k$ where $k \gt 0$, if $k$ is increased remainder will decrease. How to prove that for any number $p \le \frac{n}{2}$, I cannot obtain remainder more than what can be obtained from $\frac{n}{2}+k$ (first prime number large than half of n).

This does not hold true. Consider $n=14$, the smallest prime larger than $\frac{14}{2}=7$ is $11$, but the maximum remainder is attained for prime $5 \lt 7$:
$$14 \bmod 5 = 4 \;\;\gt\;\; 14 \bmod 11 = 3$$

[ EDIT ]    The following shetches the proof to the related question asked in a comment below.


The remainder of the division of a positive number $n$ by a positive $p \le n$ (not necessarily a prime) is maximized when $p = \lfloor \frac{n}{2}\rfloor + 1$.

First, let $p = \lfloor \frac{n}{2}\rfloor + k$ where $k \ge 1$. Then $2 p \gt n$ so the quotient of the division must be $1$, and the remainder will be $n - p = n - \lfloor \frac{n}{2}\rfloor - k$. This is obviously maximized when $k = 1$ in which case it is $r_{max} = n - \lfloor \frac{n}{2}\rfloor - 1$.
Now, take $p \le \lfloor \frac{n}{2}\rfloor$. Then the remainder will be by definition a number $r \lt p \le \lfloor \frac{n}{2}\rfloor$. Since $r$ is an integer, it follows that $r \le \lfloor \frac{n}{2}\rfloor - 1 \le n - \lfloor \frac{n}{2}\rfloor - 1 = r_{max}$. The equality could only be attained when $2 \lfloor \frac{n}{2}\rfloor = n$ but in that case $n$ would need to be even, $p = \lfloor \frac{n}{2} \rfloor$ would be a divisor of $n$ and the remainder would be $0$. This proves the strict inequality $r \lt r_{max}$.
