Last week, I suggested a process for getting better at writing proofs. To illustrate that process, here’s an example of how to use it to prove a theorem from Rosen.
Prove: If $a$ and $d$ are positive integers, then $(-a) \textbf{ div } d = -a \textbf{ div } d$ if and only if $d \mid a.$
Step 1: Find a proof to practice
This proof is an exercise from a section in Rosen called “Divisibility and Modular Arithmetic.” It’s an odd-numbered exercise, so I’ll be able to compare my proof with the one from the solution guide.
Step 2: Brainstorm
For this step, we’ll think about the proof statement and collect any information that might be useful.
When I first read the proof statement, I found the equation $(-a) \textbf{ div } d = -a \textbf{ div } d$ to be ambiguous. It probably has a precise meaning when taking into account order of operations rules, but I prefer to be more explicit, writing it as $(-a) \textbf{ div } d = -(a \textbf{ div } d)$. I’ll assume that this is equivalent to the original equation.
The $\textbf{div}$ operator relates to a theorem known as the Division Algorithm (Rosen 4.1.3 Theorem 2). This theorem states that given integers $a$ and $d$, with $d>0$, there are unique integers $q$ and $r$, with $0 \leq r<d$, such that $a = dq + r$. In this equality, $q$ is called the quotient, and it is defined as $q = a \textbf{ div } d$
$d \mid a$ means $d$ divides $a$ (with no remainder). It follows that $a/d$ is an integer.
With the notation defined, the next step is to try some examples.
Informally, we can think of $a \textbf{ div } d$ as meaning “divide $a$ by $d$ and discard the remainder.” If $a=4$ and $d=2$, standard division says $a/d=4/2=2r0$ ($2$ with a remainder of $0$), so $a \textbf{ div } d=2$, the same result provided by the $/$ operator. But if $a=4$ and $d=3$ then $a/d=4/3=1r1$, so $a \textbf{ div } d=1$. The remainder is ignored.
By definition in this context, the remainder must be nonnegative. We have to be careful about this rule when dividing negative numbers. For example, if $a=-4$ and $d=2$, $a/d = -4/2 = -2r0$. For zero remainders, this works as expected. But if $a=-4$ and $d=3$ then $a/d=-4/3=-2r2$, not $-1$ with a remainder of $-1$. We have to adjust the quotient to get a nonnegative remainder. I find it useful to write this as $-4/3=(-6/3)+(2/3)$. The $-6/3$ term is the quotient, which evaluates to $-2$, and the $2/3$ term is the remainder, which is usually written as $2$, without the denominator.
Next, let’s check that the theorem works for a couple of examples:
Example 1:
Let $a=4$ and $d=2$. Since $2 \mid 4$, the theorem says:
$$(-a) \textbf{ div } d = -(a \textbf{ div } d)$$ $$(-4) \textbf{ div } 2 = -(4 \textbf{ div } 2)$$ $$-2 = -(2)$$ $$-2 = -2$$
So the first example works.
Example 2:
Let $a=4$ and $d=3$. Since $3 \not| ~4$, the theorem says:
$$(-a) \textbf{ div } d \neq -(a \textbf{ div } d)$$ $$(-4) \textbf{ div } 3 \neq -(4 \textbf{ div } 3)$$ $$-2 \neq -(1)$$ $$-2 \neq -1$$
So the second example works as well.
These examples suggest why this theorem is true. It has to do with how the $\textbf{div}$ operator works with negative numbers. When $d \mid a$, there is no remainder, so $(-a) \textbf{ div } d$ is the same as $-a/d$, which is an integer according to elementary division rules. So we can just evaluate $a/d$ and then negate it.
But when $d \not| ~a$, evaluating $(-a) \textbf{ div } d$ takes a bit more work. It’s not the same as $a/d$ because of the rule that a remainder must be positive.
Let’s make these $\textbf{div}$ rules more precise. It can be shown that $a \textbf{ div } d = \lfloor{a/d}\rfloor$ (see Rosen 4.1.2, Definition 2, Remark). We can write this equivalence a few different ways, which will be useful in the proof:
$$a \textbf{ div } d = \lfloor{a/d}\rfloor \tag{1}$$ $$(-a) \textbf{ div } d = \lfloor{-a/d}\rfloor \tag{2}$$ $$-(a \textbf{ div } d) = -\lfloor{a/d}\rfloor \tag{3}$$
Step 3: Write a draft
Let’s consider some ideas for the proof. Since we’re proving an “if and only if” statement, a standard approach is to prove each direction separately. So we will have a Part 1 proof that if $(-a) \textbf{ div } d = -(a \textbf{ div } d)$ then $d \mid a$, and a Part 2 proof that if $d \mid a$ then $(-a) \textbf{ div } d = -(a \textbf{ div } d)$.
We’ll use these tools:
The equalities $(1)$, $(2)$, and $(3)$, which relate the $\textbf{div}$ operator and the floor function.
Properties of the floor function.
The Division Algorithm, which guarantees a unique quotient and remainder when two integers are divided.
For Part 1, we start with a $\textbf{div}$ equation. Using $(1)$, $(2)$, and $(3)$, we can convert it to an equation in which the floor function operates on fractions. Then we can use the Division Algorithm to express each fraction as a quotient and a remainder. Divisibility is related to remainders, so we can use the information about remainders to show that $d$ divides $a$.
For Part 2, we start with the assumption that $d$ divides $a$, which means $a/d$ is an integer. This means the floor functions have no effect on $a/d$, so when we use $(1)$, $(2)$, and $(3)$ to introduce floor functions, they just disappear. This makes it straightforward to get to the desired $\textbf{div}$ equation.
We’ll see that the way $\textbf{div}$ works with a negative argument is related to how the floor function handles a negative argument.
Step 4: Fill in the details
We now have all the information we need to prove the “if and only if” statement in two parts:
Part 1: If $(-a) \textbf{ div } d = -(a \textbf{ div } d)$ then $d \mid a$.
Let $a$ and $d$ be integers such that $(-a) \textbf{ div } d = -(a \textbf{ div } d)$. Using $(2)$ and $(3)$, we can convert this equality to floor notation and write $\lfloor{-a/d}\rfloor = -\lfloor{a/d}\rfloor$.
By the Division Algorithm, we know that given our positive $a$ and $d$, we can find unique integers $q$ and $r$ such that $a=dq+r$. Dividing by $d$, we get $a/d=q+r/d$. Multiplying that equation by $-1$ gives us $-a/d=-q-r/d$. We now have $a/d$ and $-a/d$ expressed as an integer quotient and a fractional remainder between 0 (inclusive) and 1 (exclusive).
Substituting these results into the floor functions, we get $\lfloor{-a/d}\rfloor =\lfloor{-q-r/d}\rfloor$ and $-\lfloor{a/d}\rfloor=-\lfloor{q+r/d}\rfloor$.
For a positive argument, the floor function simply discards any fractional component. So $-\lfloor{q+r/d}\rfloor=-q$.
For the negative argument, $-q-r/d$, the expression $\lfloor{-q-r/d}\rfloor$ evaluates to either $-q$ (if $r=0$) or $-q-1$ (if $r>0$).
(To see why this is, think of the floor function as moving a real number to the left on the number line to the next lowest integer. So for a positive real number like $3.14$, the result is just $3$, with the $0.14$ stripped off. But for a negative real number like $-3.14$, the result is $-4$, the next lower integer.)
But our initial assumption is $(-a) \textbf{ div } d = -(a \textbf{ div } d)$, which means that $-\lfloor{q+r/d}\rfloor$ and $\lfloor{-q-r/d}\rfloor$ are equal. Since $-q \ne -q-1$, it must be true that $r=0$, which is the definition of $d \mid a$, as required.
Part 2: If $d \mid a$ then $(-a) \textbf{ div } d = -(a \textbf{ div } d)$.
Let $d$ and $a$ be integers such that $d \mid a$. By definition, that means $a/d=q$ for some integer $q$. Multiplying by $-1$ gives us $-a/d=-q$. Taking the floor of both sides: $\lfloor{-a/d}\rfloor=\lfloor{-q}\rfloor$. But this is just $-q$, since taking the floor of an integer doesn’t change it. By $(2)$, $(-a) \textbf{ div } d = \lfloor{-a/d}\rfloor$, so we have $(-a) \textbf{ div } d = -q$.
Consider the equation $a/d=q$ again. Taking the floor of both sides gives us $\lfloor a/d \rfloor=\lfloor q \rfloor=q$. Multiplying by $-1$: $-\lfloor a/d \rfloor=-q$. By $(3)$, $-(a \textbf{ div } d) = -\lfloor{a/d}\rfloor$, so we have $-(a \textbf{ div } d) = -q$ as well. Therefore, $-q=(-a) \textbf{ div } d = -a \textbf{ div } d$, as required.
The combination of Part 1 and Part 2 proves the theorem.
Step 5: Read someone else’s version
The Rosen solution guide takes a somewhat different approach to this proof. Instead of proving the “if” and the “only if” parts of the theorem, they prove Part 2 and its inverse. By the rules of logic, this is equivalent to proving Part 1 and Part 2. Here is that proof, which I have expanded with additional detail.
Solution Guide Part A: If $d \mid a$ then $(-a) \textbf{ div } d = -(a \textbf{ div } d)$.
Let $d$ and $a$ be integers such that $d \mid a$. By definition, that means that $a/d=m$ for some integer $m$, and therefore $a=md$. Multiplying by $-1$, we get $-a=(-m)d$, which means
$$-a/d=-m \tag{4}$$
Since $d \mid a$, we know that $a/d$ is an integer, so $a/d=\lfloor a/d \rfloor$, which is equivalent to $a \textbf{ div } d$ according to $(1)$. Multiplying by $-1$ gives us $-a/d=-(a \textbf{ div } d)=-m$ according to $(4)$.
Since $d \mid a$, we also know that $-a/d$ is an integer, so $-a/d=\lfloor -a/d \rfloor$, which is equivalent to $(-a) \textbf{ div } d$ according to $(2)$. So we have $-a/d=\lfloor -a/d \rfloor=(-a) \textbf{ div } d=-m$, according to $(3)$.
Since both expressions are equal to $-m$, we have shown that $-m = (-a) \textbf{ div } d = -(a \textbf{ div } d)$, as required.
Solution Guide Part B: If $d \not\mid a$ then $(-a) \textbf{ div } d \neq -(a \textbf{ div } d)$.
Let $d$ and $a$ be integers such that $d \not\mid a$. This means we will have a nonzero remainder when dividing $a$ by $d$. Expressed in Division Algorithm notation: There exist integers $q$ and $r$ such that $a=qd+r$, $0<r<d$, and $q=a \textbf{ div } d$.
Multiplying the Division Algorithm equality by $-1$ gives us $-a = (-q)d-r$. Let’s manipulate this as follows:
$$-a = (-q)d-r$$ $$-a=-qd-d+d-r$$ $$-a=(-q-1)d+(d-r) \tag{5}$$
Since $0<r<d$, we know that $0<d-r<d$. This means we can interpret $(5)$ as a Division Algorithm equation with dividend $-a$, divisor $d$, quotient $(-q-1)$ and remainder $(d-r)$. By the definition of $\textbf{div}$, this means $(-a) \textbf{ div }d=(-q-1)$, the quotient.
But the definition of $\textbf{div}$ also tells us that $q=a \textbf{ div } d$, which means $-q=-(a \textbf{ div } d)$. Since $(-q-1) \neq -q$, we have shown that assuming $d \not\mid a$ leads to the conclusion that $(-a) \textbf{ div } d \neq -(a \textbf{ div } d)$, as required.
Since we have proven statements of the form “if $A$ then $B$” and “if not $A$ then not $B$” (the inverse), this suffices to prove “$A$ iff $B$”.
Step 6: Practice it later
In last week’s post, I mentioned Cal Newport’s approach of reproducing proofs for his Discrete Math class using a Quiz and Recall system. A prerequisite for using this system is having something to recall. The proofs shown above are probably too detailed to learn and recall. But writing proofs out in extreme detail forces you to understand every step. This is good preparation before you settle on a more compact version to use for study.
I’m writing about discrete math and competitive programming this year. For an introduction, see A Project for 2019. To read the whole series, see my Discrete Math category page.