# Number of remainders after dividing $x$

Given a positive integer $x$,how many possible remainders can you get after dividing $x$ by positive integers smaller than it?

Let the number be $100$.No matter what number you choose that is less than $100$,you can never get a remainder of $50$.So my question is,how many possible remainders are there after division of a number $x$ [such as $100$] by other numbers?This should require some modular arithmetic,since it deals with remainders.

Now obviously,all numbers greater than $\dfrac{x}{2}$ generate remainders that are integers smaller than $\dfrac{x}{2}$.Does it mean that when the divisor is smaller than x,the only remainders not possible are $x/2$ and integers greater than $x/2$?

Some form of hint will be appreciated.

Happy Yuletime,everyone.

• Not sure how to prove it, but, try to compute the number $u_n$ of remainders of $n$ divided by $k$: $2,2,3,3,4,4,5,5,6,6,...$ So it seems to be $\mathrm{floor} ((n+3)/2)$. By the way, Happy Yule! Dec 24, 2013 at 8:41
• @arbautjc,can you please elaborate?I don't understand what you mean by dividing n by 2,2,3,3,4,4. . . ...Also,Happy Yule! Dec 24, 2013 at 8:52
• No I mean $u_n$ (the number you are looking for) takes these values, so $u_n=\mathrm{floor}((n+3)/2)$. Dec 24, 2013 at 8:53
• And sorry, it's really $u_n=\mathrm{floor}((n+1)/2)$ since you divide by smaller numbers (I missed this). Dec 24, 2013 at 8:56

The number of different remainders possible is $\frac{x}{2}-1$. The remainder cannot be greater than $\frac{x}{2}$, otherwise you can divide the number another time by the divisor, which is greater or equal to $2$. For $100$, you cannot have a remainder bigger than $49$, because otherwise you can add $1$ to the quotient : if $$100=bq+r$$ with $r$ bigger than $49$, then you can subtract at least once more $q$ to 100...
• Also,$\dfrac{x}{2}-1$ is not always an integer.There must must be a floor or ceiling involved somewhere. Dec 24, 2013 at 9:29
• More importantly,number of remainders is $\dfrac{x}{2}$,not $\dfrac{x}{2}-1$.You are not counting 0.As an example,take 4.The possible remainders are 0and 1.Therefore the number of remainders is 2,not $\dfrac{4}{2}-1=1$. Dec 24, 2013 at 9:35
• More precisely we canb say that the set of possible rmainders is $\{0,\ldots,\lfloor \tfrac x2-1\rfloor\}$ as $r\in\{0,\ldots,\lfloor \tfrac x2-1\rfloor\}$ occurs when dividing by $x-r$ (note that $x-r>r$) and no greater remainder is possible as already observed by the OP. Dec 24, 2013 at 10:19