head_scratchers.tex

\yourname

\activitytitle{Head Scratchers}{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.  Procedures that are guaranteed to work are called {\em algorithms} after the 9th century Persion mathematician al-Khwarizmi, who worked on procedures for arithmetic.  The division algorithm itself dates to Euclid's {\em Elements} from around 300 BC.}

\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.  Let $r$ denote the number of cards left 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.  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.}{1.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 at the end and $q$ denote the number of cards that each person got.  What do we know for sure about the possible values of $r$?  What do we know for sure about the possible values of $q$?  Write the relationship between $n$, 5, $q$, and $r$ analogous to $37 - 5q = r$ and the expression analogous to $37 = 5q + r$.  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.}{1.5in}

\example{Continuing to divide by 5, complete this sentence:  Given an integer $n \geq 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.
Your fried is dealing.
Write instructions telling your friend how to deal the cards out, when to stop dealing, and say what you can about how many cards she will have left over and how many cards each person will get.
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$.}{2in}

\stop Compare your work to the others in your group.  Work to get the best possible phrasing of \ref{positivepositivedivision}.

\question{What happens when $k=0$?  Can you satisfy $n = qk + r$?  What goes wrong?}{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 tries 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 could we see this without thinking about card dealing?
It will take a few steps.
}

\show{Suppose that $r$ and $b$ are integers for which $0 \leq r < k$ and $0 \leq b < k$.
Carefully combine these inequalities to show that $-k < r-b < k$.
Your goal is to provide a crystal clear argument with no extra steps.
You can add inequalities that run the same direction; for example, if $a < b$ and $c < d$, then $a+c < b+d$.
}{2in}

\show{\label{DivisionAlgorithmUniqueness}Suppose that $n$ and $k$ are integers, that $k > 0$, and that $q$, $r$, $a$, and $b$ are integers such that $n = qk + r$ and $n = ak + b$ and that $r$ and $b$ take values between 0 and $k-1$.
Set $qk + r$ equal to $ak + b$ and argue that $q = a$ and $r = b$.
Work on scratch paper and then write a final argument here.
Take the time to write a clear argument that your whole group likes.
If you use a proof by contradiction, say so.
If you use a proof by cases, say so.}{3in}

\theorem{{\bf The Division Algorithm.} Let $n$ and $k$ be integers greater than 0.
There are two parts to the theorem.
\blist{0in}
\item {\bf Existence.} There exist unique 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; $n = qk + r$ is the only way to write $n$ as a multiple of $k$ plus a remainder from $0, 1, 2, \ldots, k-1$.
\elist
The number $q$ is called the {\em quotient} and $r$ is called the {\em remainder}.
You have proven this theorem above.
Identify where the existence part was proven, and where the uniqueness part was proven.
}

\prove{Let $n$ be an integer greater than 0.
Use the existence part of the division algorithm to show that $n$ must be even or $n$ must be odd.
That is, it must be at least one of them.}{2in}

\prove{Let $n$ be an integer greater than 0.
Use the division algorithm to divide $n$ by 2 and use the uniqueness part to conclude that $n$ cannot be both even and odd.}{2in}

\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 between 0 and 4.
Count the number of 5's that you added to write $-37 + 5k = r$, where you fill in $k$ and $r$.
Rewrite this as $-37 = 5q + r$ and note the sign of $q$.
This represents division of a negative number with remainder.
How does it differ from division of a positive number with remainder?}{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 number between 0 and $k-1$.
Can you be sure that you will ever get all the way to 0?
Can you be sure that you don't jump over the numbers $0, 1, \ldots, k-1$ and keep adding $k$ forever?
Use the result to argue that you can write $n + pk = r$ for some integer $p$, and rearrange it to read $n = qk + r$.
What do you know about the possible values of $q$ and $r$?
}{2in}

\prove{Let $n$ be an integer less than 0 and let $k$ be an integer greater than 0.
Argue that there exist {\em unique} integers $q$ and $r$ for which $n = qk + r$ and $0 \leq r < k$.
This is like \ref{DivisionAlgorithmUniqueness}.
What changes are needed, if any?}{2in}

\show{Suppose that $n$ is an integer and $n = 3m + 1$ where $m$ is an integer.
Show that $n$ cannot be a multiple of 3.}{2in}

\show{Let $n$ be an integer and suppose that $n^2$ is a multiple of 3.
We would like to conclude that $n$ is a multiple of 3.
Use the division algorithm to divide $n$ by 3, which will give three cases, one for each possible remainder.
Consider each case.
What can you conclude about $n$ being a multiple of 3?}{1in}

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

\show{Let $k$ be an integer and consider the numbers $k$, $k+1$, and $k+2$.
Show that exactly one of these is a multiple of 3.
A proof by cases might be a good idea.
Note that there are two things to show:  that one of $k$, $k+1$, and $k+2$ is a multiple of 3, and that the other two are not.}{2in}

\show{Let $k$ be even and consider the numbers $k$ and $k+2$.
Show that exactly one of these is a multiple of 4.}{2in}

\show{Let $n$ be an odd integer.  Show that $n^3-n$ is a multiple of 24.}{0in}

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