division_algorithm.tex

\yourname

\activitytitle{The Division Algorithm}{Dividing integers with remainders will form the basis for several things we want to prove.}

\overview{We would like to distribute $n$ objects evenly among $k$ people and find out how many are left over.  
We will investigate a procedure for doing this, which is called division, even though there will be no fractions in this activity and we will avoid using division symbols like / and $\div$.  
The Division Algorithm dates to Euclid's {\em Elements} from around 300 BC.
Procedures that are guaranteed to work are called {\em algorithms} after the 9th century Persian mathematician al-Khwarizmi, who worked on procedures for arithmetic.  
}

\example{\label{37among5} You are the dealer in a card game that has 37 cards.  (It's not a standard deck of cards.)  There are 5 people playing, and everyone needs to end up with the same number of cards.  Dealing one card to each player leaves 32 cards in your hands.  Write down the numbers 37, 32, and continue until you cannot deal out any more cards evenly:  

\vspace{0.2in}
\noindent
Let $r$ denote the number of cards left over at the end, and let $q$ denote the number of times you subtracted 5, which is also the number of cards that each person got.  Notice that $0 \leq 5q \leq 37$.
You see that $37 - 5q = r$, which you can rewrite as $37 = 5q + r$.  Fill in $q$ and $r$ and write out these two equations.

\noindent
$37-5q = r$ becomes:
\vspace{0.2in}

\noindent
$37 = 5q +r$ becomes:
}{0.2in}

\example{Now you're playing a card game that you have not played before, and you haven't taken the time to count how many cards are in the deck.  You are the dealer again, and there are 5 people who need cards.  Let $n$ denote the number of cards in the deck.  Imagine that you repeat the procedure from the previous example until you can no longer deal out cards evenly.  Again, let $r$ denote the number of cards you have left over at the end and let $q$ denote the number of cards that each person got.  

\vspace{0.05in}
\noindent
What inequalities do we know about the possible values of $r$?  
\vspace{0.2in}

\noindent
What inequalities do we know about the possible values of $q$?  
\vspace{0.2in}

\noindent
Write the relationship between $n$, 5, $q$, and $r$ analogous to $37 - 5q = r$ and the expression analogous to $37 = 5q + r$.  
\vspace{0.2in}

\noindent
The last expression accounts for where all of the $n$ cards have gone; some are dealt out, some are left in your hands.  Write out a sentence that explains this.}{0.3in}

\example{Continuing to divide by 5, complete this sentence:  Given an integer $n > 0$, there exist integers $q$ and $r$ where (list properties of $q$ here) \blank{2in} and (list properties of $r$ here) \blank{2in}, such that (write the relationship between $n$, $q$, and $r$ analogous to $37 = 5q + r$) \blank{2in}.}{0in}

\example{\label{positivepositivedivision} 
Once again, we have $n$ cards, but now there are $k$ people playing, where $k > 0$ is an integer.
You are dealing.
Describe in words how you will deal out the cards and when you will stop.

\vspace{0.6in}
\noindent
Describe in words how many cards you will have left over.

\vspace{0.4in}
\noindent
Using $q$ to denote the number of cards each person gets and $r$ to denote the number of cards left over, write out the relationship between $n, k, q,$ and $r$, and write inequalities concerning $q$ and $r$.}{0.5in}

\stop Compare your work to the others in your group and reconcile any differences.

\question{What happens when $k=1$?  What is $r$?  What is $q$?}{0.4in}

\question{What happens with the cards when $k=0$?  What inequalities must $r$ satisfy?  Can you satisfy $n = qk + r$?  For what value(s) of $q$?   Describe in words, and take your time to get it right, because this explains why we don't divide by 0.}{1in}

\note{As above, suppose that $n$ and $k$ are integers that are greater than 0.
Suppose you find integers $q$ and $r$ for which $n = qk + r$ and $0 \leq r < k$.
Suppose your friend sets out to do the same thing and finds integers $q_2$ and $r_2$ for which $n = q_2 k + r_2$ and $0 \leq r_2 < k$.
Must it be the case that $q = q_2$ and $r = r_2$?
That is, are the values of $q$ and $r$ {\em unique}?
If you think about dealing $n$ cards to $k$ people, it's pretty clear that you and your friend will get the same values of $q$ and $r$, but how can we see this without thinking about card dealing?
It will take a few steps.
}

\show{\label{remainderinequality} Suppose that $r$ and $r_2$ are integers for which $0 \leq r < k$ and $0 \leq r_2 < k$.
Show that $-k < r-r_2 < k$.
Starting and ending expressions are shown below; your goal is to provide crystal clear intermediate steps with no extra steps.
Note:  You can add inequalities that run the same direction; for example, if $a < b$ and $c \leq d$, then $a+c < b+d$.

\vspace*{0.1in}
\noindent
Suppose \circone ~ $0 \leq r < k$ and \circtwo ~ $0 \leq r_2 < k$.

\vspace*{1.3in}
\noindent
Thus $-k < r-r_2 < k$.
}{0in}

\show{\label{DivisionAlgorithmUniqueness}Suppose that $n$ and $k$ are integers with $k > 0$, that $q$, $r$, $q_2$, and $r_2$ are integers such that $n = qk + r$ and $n = q_2 k + r_2$, and that $0 \leq r < k$ and $0 \leq r_2 < k$.
Use \ref{remainderinequality} to show that $q = q_2$ and $r = r_2$.
Starting and ending points are suggested below .
This is not simply a rewrite proof; it requires a spark of genius to complete it, so work on scratch paper, write down everything you know including \ref{remainderinequality}, work together, and be patient.
Write a final argument here.

\vspace*{0.1in}
\noindent
To start, note that because $n = qk + r$ and $n = q_2 k + r_2$, we have $qk+r = q_2 k + r_2$.

\vspace*{2.2in}
\noindent
Thus $q = q_2$ and $r = r_2$.
}{0in}

\theorem{\label{divisionalgorithm}{\bf The Division Algorithm.} Let $n$ and $k$ be integers greater than 0.  Then,
\blist{0in}
\item {\bf Existence.} There exist integers $q$ and $r$ for which $n = qk + r$ and for which $0 \leq r < k$.
\item {\bf Uniqueness.}  The numbers $q$ and $r$ are unique:  there is only one way to choose $q$ and $r$ so that $n = qk + r$ and $0 \leq r < k$.
\elist
The number $q$ is called the {\em quotient} and $r$ is called the {\em remainder}.
Note that there are two parts to the theorem.
You have proven this theorem above in two problems.
The existence part was proven in \blank{0.8in}.  The uniqueness part was proven in \blank{0.8in}.
Check that your group agrees.
}

\example{Rewrite Theorem \ref{divisionalgorithm} for the case where $k=2$.
Use equalities to tell the possible values of $r$.

\vspace{0.1in}
\noindent
Let $n$ be an integer greater than 0.  Then,
\blist{0in}
\item {\bf Existence:} There exist integers $q$ and $r$ \ldots
\item {\bf Uniqueness:}  The numbers $q$ and $r$ are \ldots
\elist
}{0.0in}

\prove{Let $n$ be an integer greater than 0.
Recall the definitions of even and odd.
Use the existence part of the Division Algorithm with $k=2$ to show that $n$ must satisfy at least one of these definitions.}{0.7in}

\prove{Let $n$ be an integer greater than 0.
Use the uniqueness part of the Division Algorithm with $k=2$ to conclude that if $n$ is even, then it cannot be odd.  Also, if $n$ is odd, it cannot be even.  Thus, each integer is even or odd, never both.
}{0.0in}

% ===================================================================
\note{Now we will divide negative numbers by positive numbers, with remainder.}

\example{Start with $-37,$ add 5 to get $-32$, and add 5 repeatedly, writing down the numbers you come to, until you reach a number from 0 to 4.

\vspace{0.4in}
\noindent
Count the number of 5's that you added to write $-37 = 5q + r$; you fill in $q$ and $r$.
Note the sign of the quotient $q$.

\vspace{0.4in}
\noindent
This represents division of a negative number by 5, with remainder.
How does it differ from division of a positive number with remainder?

\vspace{0.4in}
\noindent
In what ways is it the same as division of a positive number with remainder?
}{0.2in}

\prove{Let $n$ be an integer less than 0.
Let $k$ be an integer greater than 0.
Add $k$ to $n$ repeatedly until you reach a non-negative number, then stop.

\vspace{0.1in}
\noindent
How can you be sure that you will ever get all the way to a non-negative number?

\vspace{0.4in}
\noindent
How can you be sure that the first non-negative number you reach will be 0, 1, \ldots, $k-1$ and not a larger number like $k$ or $k+1$?

\vspace{0.5in}
\noindent
What inequalities do you know for $r$?
}{0.0in}

\example{Suppose $n$ = 0.  Show that you can write $n=kq+r$ for integers $q$ and $r$ where $0 \leq r < k$.}{0.2in}

\prove{Let $n$ be an integer less than or equal to 0 and let $k$ be an integer greater than 0.
In \ref{DivisionAlgorithmUniqueness}, we did not assume $n \geq 0$.
Scrutinize your proof of \ref{DivisionAlgorithmUniqueness}.
Will your proof work for $n \leq 0$?  Explain.
}{0.3in}

\theorem{
Completely rewrite Theorem \ref{divisionalgorithm} to cover positive, negative, and zero values of $n$.
Be specific about the assumptions on $n$ and $k$.
}

\pagebreak


% =====================================================================
\show{Let $n$ be an integer and suppose that $n = 3m + 1$ for some integer $m$.
Clearly $r=1$, but should we think of $k$ in the Division Algorithm as being 3 or as being $m$?
$k$ = \blank{1in}

\noindent
Use the Division Algorithm to argue that $n$ cannot be written as $n = 3j$ where $j$ is an integer.
Do not re-prove this part of the Division Algorithm, just cite it carefully to make your point.
Thus, if $n=3m+1$, then $n$ is not a multiple of 3.

\vspace{0.8in}
\noindent
Which part(s) of the Division Algorithm did you use, existence, uniqueness, or both? \blank{1.5in}
}{0.0in}

\show{Let $n$ be an integer and suppose that $n^2$ is a multiple of 3.
For example, $n^2$ could be 36.
List two more values of $n^2$ that are multiples of 3:

\noindent
When $n^2$ is a multiple of 3, we would like to conclude that $n$ is a multiple of 3.
It's hard to do this directly, but it can be done indirectly.
Use the Division Algorithm to write $n= 3q + r$.
Start with ``There exist integers ....'' and be specific about the possible values of $r$.

\vspace{0.4in}
\noindent
Your previous step gives three cases to consider.
For each case, write the expression for $n$, then use algebra to compute $n^2$ and rewrite it as a multiple of 3 plus a remainder of 0, 1, or 2.

\vspace{0.1in}
\noindent
{\bf Case 0:}  $r = 0$, $n = 3q$, \qq so $n^2 = $

\vspace{0.3in}
\noindent
{\bf Case 1:}  $r = 1$, $n = \blank{0.5in}$, so $n^2 = $

\vspace{0.3in}
\noindent
{\bf Case 2:}  

\vspace{0.3in}
\noindent
Knowing that $n^2$ is in fact a multiple of 3, use your cases above to rule out one or more of the cases, and so rule out one or more of the possible values of $r$.
Can you conclude that $n$ is a multiple of 3?
This is harder than you might think to explain clearly; work hard on it.
}{0.6in}

\show{Suppose $n$ is an integer.
Can $n^2$ be of the form $3m + 2$ where $m$ is an integer?
Use the cases you found in the previous question.}{0.8in}

\example{In the triple of consecutive integers 5, 6, 7, exactly one number is a multiple of 3.
Circle it.
Same thing for 13, 14, 15.
Circle the multiple of 3.
Write down 5 more triples of consecutive integers.
Do you always get a multiple of 3? \blank{1in}
Can you get more than one multiple of 3? \blank{1in}}{0in}

\pagebreak

% =====================================================================
\show{Let $n$ be an integer and consider the numbers $n$, $n+1$, and $n+2$.
Show that exactly one of these is a multiple of 3.
Use three cases, $n = 3k$, $n = 3k + 1$, and $n = 3k + 2$, and follow the guide below.

\vspace*{0.1in}
\noindent
{\bf Case 1:}  $n = 3k$.  Then $n+1 = $ \blank{1.5in} and $n+2 = $ \blank{1.5in}.\\
Exactly one of these is a multiple of three (circle it).
Use the Division Algorithm to argue that the other two are not multiples of 3.
Work hard, be clear.

\vspace*{0.4in}
\noindent
{\bf Case 2:}  $n = 3k+1$.  Then $n+1 = $ \blank{1.5in} and $n+2 = $ \blank{1.5in}.\\
Exactly one of these is a multiple of three (circle it).
Use the Division Algorithm to argue that the other two are not multiples of 3.
Work hard, be clear.

\vspace*{0.4in}
\noindent
{\bf Case 3:}  $n = 3k+2$.  Then $n+1 = $ \blank{1.5in} and $n+2 = $ \blank{1.5in}.
}{0.2in}

\example{Think about pairs of consutive even numbers, like 8 and 10, or 14 and 16.
One number is a multiple of 4 (circle it), the other is not.  Check five more pairs in the same way.}{0in}

\show{
Let $n$ be even and consider the numbers $n$ and $n+2$.
Use two cases to show that exactly one of these is a multiple of 4.
What two cases?
You will need a new idea.}{2in}

\example{Let $n=1$ and compute $n^3-n$.  
Let $n=3$ and compute $n^3-n$.
Let $n=5$ and compute $n^3-n$.}{0.0in}

\show{Let $n$ be an odd integer.  Show that $n^3-n$ is a multiple of 24.  Here you will need a few sparks of genius.
Use scratch paper to brainstorm different approaches that you could try, then try the one that looks the most promising.
Fortunately there are several ways to do this proof.
}{0in}

\vfill          % pad the rest of the page with white space