# Highest possible remainder

To solve a programming challenge I needed to find the highest obtainable remainder for a given number when divided by a number between 1 and n. I figured out that this is $n$ mod $(\lfloor(n/2)\rfloor + 1)$ . Math not being my thing I couldnt figure out how to prove this . Can anyone give me pointers ?

-
How about $n\bmod(n+1)=n$? Are there hidden conditions you're not describing in the question? If so, please edit the question to show them. –  Henning Makholm Dec 28 '12 at 10:15
The problem statement is a confusing story . The divisor is between 1 and n . So n + 1 is not allowed. –  Sam Dec 28 '12 at 10:18
@Sam If the divisor is between 1 and n like you said in your comment then you are right, assuming by $(n/2)$ you mean the floor of $n/2$. Hints: Use the division algorithm for showing that nothing below $[n/2]+1$ can leave a higher remainder; direct computation shows the rest of the possibilities are too small. –  peoplepower Dec 28 '12 at 10:21
yeah i meant floor of n/2 . –  Sam Dec 28 '12 at 10:22
Virtually the only information your question contains is the formula "$n \bmod (n/2)+1$". Can you seriously imagine that onybody could figure out what your problem is from only that information? To make things worse parentheses are missing in your expression (and the ones present aren't useful). Do you mean $(n \bmod n/2)+1$ (which is either $1$ or $2$, depending on the parity of $n$) or do you mean $n \bmod (n/2+1)$ (which is $n/2-1$ or $n/2$) ? –  Marc van Leeuwen Dec 28 '12 at 10:26