Why study integers and divisibility?
- binary, octal, hexadecimal systems
- solving equations such as 36x+48y=56 where x and
y must be integers
- latin squares
- mod n
- prime numbers - used for example in cryptography.
We begin with division. When we divide an integer by another integer,
we usually look for a remainder (rest) which is as small as possible while
remaining non-negative. For example,
if we divide 27 by 6 we get 4 remainder 3. What does that mean? It
means that 27=6
4 + 3. However,
we could also write 27=36 + 9,
which means we get a
remainder of 9.
We are making two assumptions
r < b
The next theorem shows that our assumptions are correct.
For all integers a and b > 0, there exist unique integers
q and r such that a=qb+r where
0 r < b.
| Proof | Comments |
First we show that there are integers q, r where r
|
Now, what is it we want to prove? We can break it down
into several steps.
|
| Now, taking q=0 and r=a, we have a=bq+r=0b+q. |
How can we do this? If we take an example, we can write
27=40 + 27. In this case q=0 and
r=27 0 - in general this is
a=b0 + a, so
there is a non-negative remainder.
|
|
Let S be the set of all non-negative integers r such that a=bq+r. Let
r0 be the smallest element in S. Suppose r0
b.
We will obtain a contradiction. As r0 is an element in S,
we can write a=bq0 + r0 for some integer
q0. As r0 b,
r0-b is also non-negative. Hence
a=(q0+1)b+ (r0-b), where r0
0, so (r0 - b) is an
element of S. Now
r0 > r0 - b 0, so
r0 - b is a smaller element of S than r0 which we
assumed to be the smallest element of S. This is a contradiction.
Hence there is an integer r such that a=bq+r and
b r > 0.
|
Now to show that r < b we use contradiction and a
useful trick. We suppose r > b and that r is the smallest
non-negative remainder when a is divided by b. We get a contradiction by
finding a remainder which is smaller than our supposed smallest element!
There is an axiom - the Well-Ordering Axiom which enables us to
be sure that there is a smallest element in any set of non-negative
integers. (This is covered more thoroughly in Diskret Matematik B.) Note that we say an integer r as we do not yet know if there is just one integer r. In mathematics we need to be precise - if there is a possibility that there is more than one, we should say 'a' and not 'the'. |
| Suppose r1, r2, q1 and
q2 are integers such that
a=bq1+r1 (1) and a=bq2+r2 (2)
where 0 r1 < r2
< b. Subtracting (1) from (2), we get
b(q1-q2)+(r1-r2)=0, that is
b(q1-q2)=r2-r1 > 0. As
r1 < r2 < b, we have
r2-r1 < b.
It is also a multiple of b, which is a contradiction as there are no
integer multiples of b in the given range. Hence there is are unique q and
r satisfying the conditions.
|
Now we know that integers q and r, satisfying the conditions given, exist. We need to show they are unique. Again, we use a useful trick. We suppose they are not unique and get a contradiction. |
We call this unique remainder r such that
0 r < b the principal remainder.
There are two important consequences of the uniquess proved in the theorem above. The first is that we know that an integer is either even or odd, but never both and the second is discussed in the next section.
That the remainder is unique has important consequences. Consider the number 329. What does that mean? It means
102 +
210 +
91.Is there any other way to write this number in our normal decimal system? We 'know' there is not because of our previous experience. The reason is because the principal remainder is unique. When we divide 325 by 100 we get 3 remainder 25, so we write 3 in the hundreds position. When we divide 25 by 10 we get 2 remainder 5, so we want 2 in the tens position. Finally we have 5 left, so we write that in the units position to get 325. We had no choice at any stage as to what to write where.
Now we will look at different position systems and how we can convert from denary (base 10) to other bases.
How can we write 327 in binary?
We need to find the quotient (kvot) and
principal remainder when 327 is divided by 256=28.
We get 1 remainder 71.
We now need to find the quotient and remainder when 71
(the previous remainder) is divided by 128=27.
This gives0 remainder 71.
Continuing, we divide by 64=26 to get
1 remainder 7.
Dividing 7 by 32=25 we get0 remainder 5.
Dividing 7 by 16=24 we get 0 remainder 5.
Dividing 7 by 8=23 we get 0 remainder 5.
Dividing 7 by 4=22 we get 1
remainder 3.
Dividing 3 by 2=21 we get1
remainder 1,
and finally dividing 1 by 1 we get 1 remainder 0.
This means that 32510 (the subscript indicates the base)
can be written as 1010001112. (Always a good idea to check
an answer if possible: 1010001112 =
(256+64+4+2+1)10 =
32710.)
There is a problem with this method. If we want to write the number x in binary, we have to calculate all the powers of 2 which are at most x. When x is small, this isn't too bad, but what if x is large? We really want a more practical method. Next we consider such a method.
We divide 327 by 2, and then we divide the quotient by 2 and so on.
| 327 | = | 2163 | + | 1 | |
| 163 | = | 281 | + | 1 | |
| 81 | = | 240 | + | 1 | |
| 40 | = | 220 | + | 0 | |
| 20 | = | 210 | + | 0 | |
| 10 | = | 25 | + | 0 | |
| 5 | = | 22 | + | 1 | |
| 2 | = | 21 | + | 0 | |
| 1 | = | 20 | + | 1 | |
| Stop when quotient is 0. | |||||
Now read the final column above in reverse order. We get 101000111, which is exactly what we had before.
How did the calculation work? When we divided by 2 the first time, we got
2+1.Now we
continue with 163, so we have 163=812+1.
We substitute this for 163 in the above calculation to get
have
2 + 1 =
(812 +
1)2 + 1 =
8122 +
12 + 1.
Replacing 81 in the above, we get
2+1)22 +
12 + 1 =
4023 +
122 +
12 + 1.Replacing 40 gives
2+0)23 +
122 +
12 + 1 =
2024 +
023 +
122 +
12 + 1.Replacing 20 gives
2 +
0)24 +
023 +
122 +
12 + 1
=
1025 +
024 +
023 +
122 +
12 + 1
Replacing 10 gives
2+0)25 +
024 +
023 +
122 +
12 + 1
=
526 +
025 +
024 +
023 +
122 +
12 + 1
Replacing 5 gives
| 327 | = |
(22+1)26 +
025 +
024 +
023 +
122 +
12 + 1 |
| = |
227 +
126 +
025 +
024 +
023 +
122 +
12 + 1 |
And finally, replacing 2 gives
| 327 | = |
(12+0)27 +
126 +
025 +
024 +
023 +
122 +
12 + 1
|
| = |
128 +
027 +
126 +
025 +
024 +
023 +
122 +
12 +
1 | |
| = | 1010001112. |
To write 327 in base 8, we apply the same technique as above.
| 327 | = | 408 |
+ | 7 |
| 40 | = | 58 |
+ | 0 |
| 5 | = | 08 |
+ | 5 |
| Quotient was 0 in previous row, so stop and write down the remainders in reverse order. | ||||
Hence 327=5078.
(Check: 582 +
081 +
7 = 564+7=327.)