How to prove these two functions are always equal?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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}$$