2
$\begingroup$

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

I have been thinking about this question for some time.Here is an explicit example.

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.

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – Jean-Claude Arbaut
    Dec 24, 2013 at 8:41
  • $\begingroup$ @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! $\endgroup$
    – rah4927
    Dec 24, 2013 at 8:52
  • $\begingroup$ No I mean $u_n$ (the number you are looking for) takes these values, so $u_n=\mathrm{floor}((n+3)/2)$. $\endgroup$
    – Jean-Claude Arbaut
    Dec 24, 2013 at 8:53
  • $\begingroup$ And sorry, it's really $u_n=\mathrm{floor}((n+1)/2)$ since you divide by smaller numbers (I missed this). $\endgroup$
    – Jean-Claude Arbaut
    Dec 24, 2013 at 8:56

1 Answer 1

Reset to default
5
$\begingroup$

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...

$\endgroup$
4
  • 1
    $\begingroup$ +1,Nice.By the way,since we are talking about divisors smaller than 100,we must be counting 0 as a remainder.What happens when x is a prime number?0 can't possibly be a remainder then. $\endgroup$
    – rah4927
    Dec 24, 2013 at 8:56
  • 1
    $\begingroup$ Also,$\dfrac{x}{2}-1$ is not always an integer.There must must be a floor or ceiling involved somewhere. $\endgroup$
    – rah4927
    Dec 24, 2013 at 9:29
  • $\begingroup$ 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$. $\endgroup$
    – rah4927
    Dec 24, 2013 at 9:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hagen von Eitzen
    Dec 24, 2013 at 10:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .