1
$\begingroup$

If $a$ and $b$ are positive integers and $/$ stands for integer division, we have these two functions:

$$f(a,b) = (a + b - 1) / b$$

and

$$g(a,b) = \begin{cases} a/b, & \text{if $a \mod b = 0$} \\[2ex] a / b + 1, & \text{if $a \mod b \neq 0$} \end{cases} $$

We can see $f(a,b)$ equals to $g(a,b)$ by filling a and b with actual numbers, but how do you prove that they are always equal? I've answered this question here but I think I was over-complicating it so not really convinced by myself.

This problem is quite common in real life. Consider we have 10 students and now we need to divide them into several groups each of which has the same number of students, say, that number is 3. Now we need to calculate how many groups there will be, and the answer is 4. If we put it into math function then $g(a,b)$ is a natural way of thinking, but $f(a,b)$ also does the job. Why?

$\endgroup$
18
  • 1
    $\begingroup$ Since this site is for asking math questions, could you rewrite your expressions using MathJax so that we have some formulas to look at? $\endgroup$ – user526015 Feb 13 '19 at 10:43
  • $\begingroup$ Exactly @James... $\endgroup$ – Dr. Mathva Feb 13 '19 at 10:44
  • $\begingroup$ Thus, a % b == 0 means that a is a mult of b ? $\endgroup$ – Mauro ALLEGRANZA Feb 13 '19 at 10:45
  • 1
    $\begingroup$ @James Since this problem concerns both math and programming and I doubt if there's a way to express the second in a math formula I think it's proper to show them in code format. $\endgroup$ – Ivan Huang Feb 13 '19 at 10:46
  • 1
    $\begingroup$ @IvanHuang $$f(a,b)=\begin{cases}\frac{a}{b}, & a\mod b =0\\ \frac{a}{b}+1,& a\mod b \neq 0.\end{cases}$$ and $g(a,b)=\frac{a+b-1}{b}$. You see it is definitely possible to write them in a more math-usual form. $\endgroup$ – user526015 Feb 13 '19 at 11:48
1
$\begingroup$

For positive integers $a$, $b$, the two expressions are the same.

Suppose $a=qb+r$, where $q=a/b$ (quotient) and $r=a\%b$ (remainder). Then $$a+b-1=(q+1)b+(r-1)$$ If $r\ge1$ then $r-1$ is the new remainder and the new quotient is $$(a+b-1)/b = q+1 = a/b + 1$$ Otherwise if $r=0$, then $a+b-1=qb + (b-1)$, which gives the second formula $$(a+b-1)/b = q = a/b$$

$\endgroup$
2
  • $\begingroup$ In the second step how are you sure $(a+b-1)/b = q+1$ and $(a+b-1)\mod b = r - 1$? Why can't it be, say $(a+b-1)/b = q-1$ and $(a+b-1)\mod b = r+b-1$? The same goes with the third step, how do you make sure the new quotient is $q$ and remainder is $b-1$? I couldn't really follow that. $\endgroup$ – Ivan Huang Feb 14 '19 at 0:43
  • $\begingroup$ @Ivan Huang. By the definition of remainder, $r<b$, so $r-1<b$ for the second step; and obviously $b-1<b$ for the third. Note that quotients and remainders are unique. $\endgroup$ – Chrystomath Feb 15 '19 at 9:29
0
$\begingroup$

Try a=-1 and b=2 and you may be surprised.

Different languages define operators differently. Integer division may round to negative infinity or to zero. The % operator in most languages is not the modulo for negative numbers.

$\endgroup$
1
  • $\begingroup$ Okay... then I'll add that a and b are both positive integers... $\endgroup$ – Ivan Huang Feb 13 '19 at 11:03
0
$\begingroup$

Notice that we can express integer division in terms of vanilla-flavoured division using the floor function. For example, your function $f$ could be expressed

$$f(a,b)=\left\lfloor\frac{a+b-1}{b}\right\rfloor=\left\lfloor\frac{a-1}{b}+1\right\rfloor=\left\lfloor\frac{a-1}{b}\right\rfloor+1$$

and $g$ could be expressed

$$g(a,b)=\left\{\begin{array}{ll} \displaystyle\left\lfloor\frac a b\right\rfloor,&\left(\exists k\in \mathbb Z\right)\left(a=kb\right)\\ \displaystyle\left\lfloor\frac{a}{b}\right\rfloor+1,&\text{otherwise} \end{array}\right.$$

Before we see why $f$ and $g$ are equivalent it might help to notice the following:

  • If $a$ can be expressed as $kb+r$ where $k\ge 0$ and $0\le r<b$ then $$\left\lfloor\frac{a}{b}\right\rfloor=\left\lfloor\frac{kb+r}{b}\right\rfloor=k+\left\lfloor\frac r b\right\rfloor=k$$

  • We can "complete the remainder" to get the identity:$$\left\lfloor\frac a b\right\rfloor = \left\lfloor\frac{kb+r\color{darkorange}{+(b-r)}}{b}\right\rfloor-1=k$$

(For example, if $a=28$ and $b=5$ so that $k=5$ and $r=3$. Notice that $\left\lfloor\frac {28} 5\right\rfloor=5$ and that $\left\lfloor\frac {28\color{darkorange}{+2}} 5\right\rfloor-1=5$.)

Now, if we consider the cases in $g$ separately:

Case 1: $a$ is a multiple of $b$

$$\begin{align} \left\lfloor\frac{a-1}{b}\right\rfloor+1 &=\left(\left\lfloor\frac{a-1\color{darkorange}{+1}}{b}\right\rfloor-1\right)+1\\\\ &=\left\lfloor\frac a b\right\rfloor \end{align}$$

Case 2: otherwise

In this case there exist unique $k\ge 0$ and $0<r<b$ such that $a=kb+r$, so

$$\begin{align} \left\lfloor\frac{a-1}{b}\right\rfloor+1 &=\left(\left\lfloor\frac{kb+r-1+\color{darkorange}{(b-r + 1)}}{b}\right\rfloor-1\right)+1\\\\ &=\left\lfloor \frac{b(k+1)}{b}\right\rfloor\\\\ &=\left\lfloor k+1\right\rfloor\\\\ &=\left\lfloor\frac ab\right\rfloor+1 \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.