NTIC The Division Algorithm

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 \in Z

and

b > 0,

we can always write

a = q b + r

with

0 \leq 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.

🔗

Finding

q

and

r

is easy in small examples like

a = 13, b = 3 .

We have 13 = 4 \cdot 3 + 1 so q = 4 and r = 1 .

🔗

For bigger values it’s nice to have the result implemented in Sage.


    
        
xxxxxxxxxx
 
1
divmod(281376,29)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

We can check the correctness of the Sage output by multiplying and adding back together.

🔗

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
 
1
divmod(281376,29)[0] * 29 + divmod(281376,29)[1]

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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.

🔗

The discussion in the previous note actually turns out to be an enduring argument in number theory, too. Do we only care about positive numbers, or nonnegative ones as well? We saw this in the stamps example, since one could send a package for free under certain circumstances (campus mail), but might not care about that case. Similarly, are we required to use at least one of each type of stamp, or is it okay (as in our problem) to not use one type?

🔗

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 call

S = {a - k b ∣ k \in Z} .

🔗

(Note that the set looks the same if we add multiples of

b,

since

k \in Z,

but for the purposes of exposition it is easier to think of it as subtraction.)

🔗

The object of main interest in the proof will be the nonnegative piece of

S

which we will call

S^{'} = S \cap N .

For example, if

a = 13, b = 3,

then

S = {\dots 19, 16, 13, 10, 7, 4, 1, - 2, - 5, \dots}

while

S^{'} = {\dots 19, 16, 13, 10, 7, 4, 1} .

🔗

Our strategy will be to apply the well-ordering principle to

S^{'} .

(It is worth thinking briefly about why both

S

and

S^{'}

are nonempty.) Give the name

r

to the smallest element of

S^{'},

which must be writeable as

r = a - b q

(that’s the definition of being an element of

S^{'} \subset S,

after all).

🔗

Now let’s briefly suppose by way of contradiction that

r \geq b .

In that case we could subtract

b

from

r,

and then

r - b \in S^{'}

as well. So

r

would not be the least element of

S^{'},

which is a contradiction. Hence we know that

r < b .

(Note that

r

is the smallest nonnegative number in

S^{'},

just as with our intuition regarding remainders from school.)

🔗

We still have to show that

r

and

q

are the only numbers fulfilling this statement. Suppose

a = b q^{'} + r^{'}

for some integers

q^{'}, r^{'}

where

0 \leq r^{'} < b;

clearly if

r = r^{'}

then we can solve

a - b q = r = r^{'} = a - b q^{'}

to get

q = q^{'}

(since

b > 0

), so the only interesting case is if

r \neq r^{'} .

Without loss of generality, we can assume

r < r^{'} .

🔗

In that case,

a - b q = r < r^{'} = a - b q^{'},

which can be rewritten as

0 < r^{'} - r = b (q - q^{'}) .

Since

q, q^{'} \in Z,

by Fact 1.2.2

q - q^{'}

must be at least one if it isn’t zero. But then

b = b \cdot 1 \leq r^{'} - r = b (q - q^{'})

b \leq r + b \leq r^{'},

which contradicts

0 \leq r^{'} < b .

Thus

q - q^{'} = 0

and hence

q = q^{'}

and

r = r^{'} .

🔗

It’s worth actually trying out the details of this proof with some

a

and

b,

say with

a = 26

and

b = 3 .

🔗

As a scholium (see Exercise 2.5.1) note that if

b < 0

there can still be a positive remainder, but here we would need

0 \leq r < | b |

in the theorem.

🔗

Subsection 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
 
1
for i in [0..10]:
2
   pretty_print(html("The remainder of {} squared with respect to 4 is {}".format(i,divmod(i^2,4)[1])))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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.

🔗

This certainly provides strong numerical evidence for the following proposition. But better than that will be the proof!

🔗

Proposition 2.1.4.

🔗

A perfect square always leaves remainder

r = 0

r = 1

when divided by 4.

Proof.

Using the division algorithm, we can write

n = 4 q + r .

What happens if we square it,

(4 q + r)^{2} ?

Algebraically this yields

16 q^{2} + 8 q r + r^{2} .

Clearly this is a multiple of 4 plus

r^{2} .

So the only possible remainders of

n

are the remainders of

r^{2},

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.

🔗

One cool thing about this proof is that if we just change the proof from using

n = (4 q + r)^{2}

to one using

n = (m q + r)^{2},

we can essentially do the same thing for several divisions at once. If the number we divide by is

m,

then

(m q + r)^{2} = m^{2} q^{2} + 2 m q r + r^{2} = m (m q^{2} + 2 q r) + r^{2},

🔗

hence all that matters for the final remainder is

r^{2},

since the rest is already divisible by

m .

🔗

But we know that there are only

m

possibilities for

r,

so it’s easy to check all their squares. For

m = 6,

the following cell checks for you if you don’t want to check them by hand.


    
        
xxxxxxxxxx
 
1
for i in [0..5]:
2
   pretty_print(html("The remainder of %s squared with respect to 6 is %s"%(i,divmod(i^2,6)[1])))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

This verifies that

r = 0, 1, 3, 4

are the only possible remainders of perfect squares when you divide by six.

Prev Top Next