3.3: QR Theorem and Mod
 Page ID
 24463
When we divide a positive integer (the dividend) by another positive integer (the divisor), we obtain a quotient. We multiply the quotient to the divisor, and subtract the product from the dividend to obtain the remainder. Such a division produces two results: a quotient and a remainder.
This is how we normally divide 23 by 4:
\[ \require{enclose}
\begin{array}{rll}
5 && \\[3pt]
4 \enclose{longdiv}{23}\kern.2ex \\[3pt]
\underline{\phantom{0}20} && \\[3pt]
\phantom{00}3
\end{array}\]
In general, the division \(b\div a\) takes the form
\[ \require{enclose}
\begin{array}{rll}
q && \\[3pt]
a \enclose{longdiv}{\phantom{0}b}\kern.2ex \\[3pt]
\underline{\phantom{0}aq} && \\[3pt]
\phantom{00}r
\end{array}\]
so that \(r=baq\), or equivalently, \(b=aq+r\). Of course, both \(q\) and \(r\) are integers. Yet, the following “divisions”
\[{ \require{enclose}\begin{array}{rll}
4 && \\[3pt]
4 \enclose{longdiv}{23}\kern.2ex \\[3pt]
\underline{\phantom{0}16} && \\[3pt]
\phantom{00}7
\end{array}}{\require{enclose}
\begin{array}{rll}
2 && \\[3pt]
4 \enclose{longdiv}{23}\kern.2ex \\[3pt]
\underline{\phantom{0}8} && \\[3pt]
\phantom{00}15
\end{array}}{\require{enclose}
\begin{array}{rll}
6 && \\[3pt]
4 \enclose{longdiv}{23}\kern.2ex \\[3pt]
\underline{\phantom{0}24} && \\[3pt]
\phantom{00}1
\end{array}}{\require{enclose}
\begin{array}{rll}
7 && \\[3pt]
4 \enclose{longdiv}{23}\kern.2ex \\[3pt]
\underline{\phantom{0}28} && \\[3pt]
\phantom{00}5
\end{array}}\]
also satisfy the requirement \(b=aq+r\), but that is not what we normally do. This means having \(b=aq+r\) alone is not enough to define what quotient and remainder are. We need a more rigid definition.
Theorem \(\PageIndex{1}\) QuotientRemainder Theorem
Given any integers \(a\) and \(d\), where \(d>0\), there exist integers \(q\) and \(r\) such that \[a = dq + r,\] where \(0\leq r< d\). Furthermore, \(q\) and \(r\) are uniquely determined by \(a\) and \(d\).
The integers \(d\), \(a\), \(q\), and \(r\) are called the dividend, divisor, quotient, and remainder, respectively. Notice that \(d\) is a multiple of \(a\) if and only if \(r=0\).
Remark
This is the outline of the proof:
 Describe how to find the integers \(q\) and \(r\) such that \(b=aq+r\).
 Show that our choice of \(r\) satisfies \(0\leq r< a\).
 Establish the uniqueness of \(q\) and \(r\).
Regarding the last part of the proof: to show that a certain number \(x\) is uniquely determined, a typical approach is to assume that \(x'\) is another choice that satisfies the given condition, and show that we must have \(x=x'\).
 Proof

This proof is not here because this proof needs the principle of Wellordering Principle which we will cover soon.
However, the outline above describes the general format of the proof.
Notes:
 You can refer to the QuotientRemainder Theorem in later work
 We use QR Theorem or QR Thm as a nick name.
You should not have any problem dividing a positive integer by another positive integer. This is the kind of long division that we normally perform. It is more challenging to divide a negative integer by a positive integer. When \(b\) is negative, the quotient \(q\) will be negative as well, but the remainder \(r\) must be nonnegative. In a way, \(r\) is the deciding factor: we choose \(q\) such that the remainder \(r\) satisfies the condition \(0\leq r<a\).
In general, for any integer \(b\), dividing \(b\) by \(a\) produces a decimal number. If the result is not an integer, round it down to the next smaller integer (see Example 3.3.1). It is the quotient \(q\) that we want, and the remainder \(r\) is obtained from the subtraction \(r=baq\). For example, \[\frac{22}{\;\;7} = 3.1428\ldots\,.\] Rounding it down produces the quotient \(q=4\), and the remainder is \(r=227(4)=6\); and we do have \(22=7\cdot(4)+6\).
Example \(\PageIndex{1}\)
According to the QuotientRemainder Theorem, compute the quotients \(q\) and the remainders \(r\) when \(m\) is divided by \(d\):
(a) \(m= 47\), \(d=5\) & (b) \(m=47\), \(d=5\) & (c) \(m=41\), \(d=12\)
 Solution

(a) 47 = 9(5)+2, so \(q= 5\), \(r=2\)
(b) 47 = 10(5)+3, so \(q= 10\), \(r=3\)
(c) 41 = 4(12)+7, so \(q= 4\), \(r=7\)
handson Exercise \(\PageIndex{1}\label{he:divalgo01}\)
According to the QuotientRemainder Theorem, compute the quotients \(q\) and the remainders \(r\) when \(b\) is divided by \(a\):
(a) \(b= 128\), \(a=7\) & (b) \(b=128\), \(a=7\) & (c) \(b=389\), \(a=16\)
Be sure to verify that \(b=aq+r\).
Definition MOD (and div)
Given integers \(a\) and \(b\), with \(a > 0\),
\[b\bmod a=r \leftrightarrow b=aq+r\]
where \(q \in \mathbb{Z} ,\) \(r\in \mathbb{Z} \) and \(0\leq r<a.\)
Furthermore, \[b\mbox{ div } a=q \leftrightarrow b=aq+r.\]
where \(q \in \mathbb{Z} ,\) \(r\in \mathbb{Z} \) and \(0\leq r<a.\)
\(\mbox{ div }\) and \(\bmod\) are binary operators where \(b\mbox{ div } a\) gives the quotient, and \(b\bmod a\) yields the remainder of the integer division \(b\div a\). Notice \(b\mbox{ div } a\) can be positive, negative, or even zero. But \(b\bmod a\) is always a nonnegative integer less than \(a\). In fact, \(b\bmod a\) will take on one of the values from 0, 1, 2, ..., \(a1.\)
example \(\PageIndex{2}\label{eg:divalgo02}\)
Let \(n\) be an integer such that \(n\bmod6 = 4.\)Determine the value of \((2n+5)\bmod6\).
 Solution

The given information implies that \(n=6q+4\) for some integer \(q\). Then \[2n+5 = 2(6q+4)+5 = 12q+8+5= 12q+13=12q+12+1 = 6(2q+2)+1.\] Therefore, \((2n+5)\bmod6 = 1\).
handson Exercise \(\PageIndex{2}\label{he:divalgo02}\)
Let \(n\) be an integer such that \(n\bmod11 = 5.\) Compute the value of d \((6n4)\bmod11\).
example \(\PageIndex{3}\label{eg:divalgo03}\)
Suppose today is Wednesday. Which day of the week is it a year from now?
 Solution

Denote Sunday, Monday, … , Saturday as Day 0, 1, … 6, respectively. Today is Day 3. A year (assuming 365 days in a year) from today will be Day 368. Since \[368 = 7\cdot52+4,\] it will be Day 4 of the week. Therefore, a year from today will be Thursday.
handson Exercise \(\PageIndex{3}\label{he:divalgo03}\)
Suppose today is Friday. Which day of the week is it 1000 days from today?
Representations of Integers using Modulo
From the QuotientRemainder Theorem, we know that any integer divided by a positive integer will have a set number of remainders, and thus a set number of representations.
For example, any integer divided by 7 will produce a remainder between 0 and 6, inclusive. So every integer, \(n\) can be represented by one of the following:
\(n=7q\quad n=7q+1\quad n=7q+2\quad n=7q+3\quad n=7q+4\quad n=7q+5\quad n=7q+6,\quad \) where \(q \in \mathbb{Z} .\)
These representations can be used to prove the statement: The square of any odd integer has the form \(8m+1\) for some integer \(m.\)
Start by choosing an arbitrary odd integer \(n\). State that by the QuotientRemainder Theorem any integer is able to be represented in one of these ways:
\(n=4q\quad n=4q+1\quad n=4q+2\quad n=4q+3,\quad\) for some integer \(q\).
Using the fact that \(n\) is odd, you will be able to eliminate two of these representations, leaving just two possibilities.
The rest of the proof proceeds using proof by cases (the 2 remaining cases). (See exercises.)
Example \(\PageIndex{5}\label{eg:directpf05}\)
Show that if an integer \(n\) is not divisible by 3, then \(n^21\) must be a multiple of 3.
Remark
The letter \(n\) has been used to identify the integer of interest to us, and it appears in the hypothesis of the implication that we want to prove. Nonetheless, many authors would start their proofs with the familiar phrase “Let \(n\) be … .”
 Answer

Let \(n\) be an integer that is not divisible by 3. When it is divided by 3, the remainder is 1 or 2. Hence, \(n=3q+1\) or \(n=3q+2\) for some integer \(q\).
Case 1: If \(n=3q+1\) for some integer \(q\), then by algebra \[n^21 = 9q^2+6q = 3 (3q^2+2q),\] where \(3q^2+2q\) is an integer because the \(\mathbb{Z}\) is closed under multiplication and addition. Thus in this case, \(n^21\) is a multiple of 3, by definition of multiple.
Case 2: If \(n=3q+2\) for some integer \(q\), then by algebra \[n^21 = 9q^2+12q+3 = 3(3q^2+4q+1),\] where \(3q^2+4q+1\) is an integer because the \(\mathbb{Z}\) is closed under multiplication and addition. Thus in this case, \(n^21\) is a multiple of 3, by definition of multiple..
In both cases, we have shown that \(n^21\) is a multiple 3. Therefore, if an integer \(n\) is not divisible by 3, then \(n^21\) must be a multiple of 3.
\(W^5\)
handson exercise \(\PageIndex{6}\label{he:directpf06}\)
Show that \(n(n+1)(2n+1)\) is divisible by 6 for all \(n\in\mathbb{N}\).
 Hint

One of the two integers \(n\) and \(n+1\) must be even (you MAY refer to the theorem: Consecutive integers have opposite parity.), so we can easily show that the product \(n(n+1)(2n+1)\) is a multiple of 2. Hence, it remains to show that it is also a multiple of 3. Consider three cases: \(n=3q\), \(n=3q+1\), or \(n=3q+2\), where \(q\) is an integer.
Absolute Value and Triangle Inequality Theorem
Definition
For all real numbers \(x\),
\(x = \begin{cases} x & \text{if } x < 0 \\ x & \text{if } x \geq 0 \end{cases}\)
Theorem \(\PageIndex{1}\) Triangle Inequality Theorem
For all real numbers \(x\) and \(y\), the following inequality holds: \(x+y\leq x + y\).
 Proof

proof is still to come
Summary and Review
 Given any integer \(b\), and any positive integer \(a\), there exist uniquely determined integers \(q\) and \(r\) such that \(b=aq+r\), where \(0\leq r<a\).
 We call \(q\) the quotient, and \(r\) the remainder.
 The reason we have unique choices for \(q\) and \(r\) is the criterion we place on \(r\). It has to satisfy the requirement \(0\leq r<a\).
 In fact, the criterion \(0\leq r<a\) is the single most important deciding factor in our choice of \(q\) and \(r\).
 We define two binary operations on integers. The \(\mbox{ div }\) operation yields the quotient, and the \(\bmod\) operation produces the remainder, of the integer division \(b\div a\). In other words, \(b\mbox{ div } a=q\), and \(b\bmod a=r\).
Exercises
exercise \(\PageIndex{1}\label{ex:divalgo01}\)
Find
(a) \(300 \bmod 13=\)
(b) \( 115 \bmod 11=\)
(c) \(145 \bmod 22=\)
 Solution

(a) 1 because 23(13)= 299 and 300 = 23(13) +1
(b) 6 because 11(11)= 121 and 115 = 11(11) + 6
(c) impossible since 22 is not greater than 0.
exercise \(\PageIndex{2}\label{ex:divalgo02}\)
Find \(b\bmod a\), where
(a) \(79 \bmod 19=\)
(b) \(59 \bmod 18=\)
(c) \(823 \bmod 16=\)
(d) \(172 \bmod 8=\)
(e) \(134 \bmod 20=\)
exercise \(\PageIndex{3}\label{ex:divalgo03}\)
Let \(m\) and \(n\) be integers such that \[m\bmod5=1, n\bmod5=3.\] Determine
(a) \((m+n)\bmod5\)
(b) \((mn)\bmod5\)
exercise \(\PageIndex{4}\label{ex:divalgo04}\)
Prove that among any three consecutive integers, one of them is a multiple of 3.
 Hint

Let the three consecutive integers be \(n\), \(n+1\), and \(n+2\). What are the possible values of \(n\bmod3\)? What does this translate into, according to the division algorithm? In each case, what would \(n\), \(n+1\), and \(n+2\) look like?
exercise \(\PageIndex{5}\label{ex:divalgo05}\)
Prove that \(n^3n\) is always a multiple of 3 for any integer \(n\) by
 A casebycase analysis.
 Factoring \(n^3n\).
exercise \(\PageIndex{6}\label{ex:divalgo06}\)
Prove The square of any odd integer has the form \(8m+1\) for some integer \(m.\)
(See comments in the text, Representations of Integers using Modulo, about this proof.)
exercise \(\PageIndex{7}\label{ex:divalgo07}\)
Let \(m\) and \(n\) be integers such that \[a\bmod5=4, b\bmod5=2.\]