Section 2.1 The Division Algorithm
ΒΆSubsection 2.1.1 Statement and examples
ΒΆLet's start off with the division algorithm. This is the familiar elementary school fact that if you divide an integer a by a positive integer b, you will always get an integer remainder r that is nonnegative, but less than b. Equally important, there is only one possible remainder under these circumstances.Theorem 2.1.1. Division Algorithm.
For a,bβZ and b>0, we can always write a=qb+r with 0β€r<b and q an integer. Moreover, given a,b there is only one pair q,r which satisfy these constraints. We call the first element q the quotient, and the second one r the remainder.
Proof.
The proof appears below in Subsection 2.1.2.
xxxxxxxxxx
divmod(281376,29)
xxxxxxxxxx
9702*29+18
Sage note 2.1.2. Counting begins at zero.
There are several things to note about this early computation. First, note that the answer to divmod
came in parentheses, a so-called tuple data type.
Second, there is another way to approach this computation, more programmatically so that it's easier to reuse. What do you think the [0]
and [1]
mean?
xxxxxxxxxx
divmod(281376,29)[0] * 29 + divmod(281376,29)[1]
To access the first and second parts of the answer (the quotient and remainder), we use square brackets, asking for the 0th and 1st parts of the tuple (9702,18)
! (This operation is called indexing.) In Python, the programming language behind Sage (as in many other languages), counting begins at zero.
Subsection 2.1.2 Proof of the Division Algorithm
ΒΆOne neat thing about the division algorithm is that it is not hard to prove but still uses the Well-Ordering Principle; indeed, it depends on it. The key set is the set of all possible remainders of a when subtracting multiples of b, which we callSubsection 2.1.3 Uses of the division algorithm
ΒΆIt's kind of fun to prove interesting things about powers using the division algorithm, and likely you did in a previous course. For instance, there is an interesting pattern in the remainders of integers when dividing by 4. If you are online, evaluate the following Sage cell to see the pattern. (It's also easy to just get the remainders of the first ten or so perfect squares by hand.)xxxxxxxxxx
for i in [0..10]:
pretty_print(html("The remainder of {} squared with respect to 4 is {}".format(i,divmod(i^2,4)[1])))
Sage note 2.1.3. Repeating commands for different input.
The syntax for i in [0..10]:
just means we want to do the next command for integers from 0 to 10. Such a repetition is called a loop.
Another way Python uses to generate the list of different input is the range
command; try substituting range(11)
for [0..10]
in the Sage cell above. Can you discover what the difference is between these?
The rest of the command (all the percent symbols and so forth) is mostly for correct formatting. That includes the indentation in the second line β an essential part of Python and Sage.
Proposition 2.1.4.
A perfect square always leaves remainder r=0 or r=1 when divided by 4.
Proof.
Using the division algorithm, we can write \(n=4q+r\text{.}\) What happens if we square it, \((4q+r)^2\text{?}\)
Algebraically this yields \(16q^2+8qr+r^2\text{.}\) Clearly this is a multiple of 4 plus \(r^2\text{.}\) So the only possible remainders of \(n\) are the remainders of \(r^2\text{,}\) where \(r\) is already known to be less than 4!
Now check these yourself to see that the only possibilities are the ones in the statement of the proposition.
xxxxxxxxxx
for i in [0..5]:
pretty_print(html("The remainder of %s squared with respect to 6 is %s"%(i,divmod(i^2,6)[1])))