Cryptography Reference
In-Depth Information
This proposition tells us that if an integer divides two others, it also divides any integer
linear combination of the other two.
E
XAMPLE
.
Note that 4|20 and 4|8. By the previous theorem then, 4 also divides 128 = 4 · 20
+ 6 · 8.
The following proposition is very useful in that it establishes that any integer can be
expressed as a multiple of any other positive integer
b
, plus some remainder, where that
remainder is nonnegative and less than
b
. It is called the division algorithm.
3.1
THE DIVISION ALGORITHM
PROPOSITION 3
(The Division Algorithm.) If
y
and
b
are integers such that
b
> 0, then
unique integers
q
and
r
such that 0
≤
r
<
b
and
y
=
bq
+
r
. This
q
is called the quotient,
r
the remainder,
b
the divisor, and
y
the dividend.
Proof.
Let
S
be the set of all integers of the form
y bk
where
k
is an integer. Further,
let
T
be the set of all nonnegative members of
S
.
T
is not the empty set, since
y bk
> 0
whenever
k
<
y
/
b
. So,
T
must have a smallest element; choose
q
to be the value of
k
so that
y bq
is the smallest member of
T
. Now, set
r
=
y bq
. We will show that this choice of
q
and
r
are exactly those desired. First, we know that
r
≥
0, (since
y bq
is nonnegative)
and
r
<
b
, since if
r
≥
b
we would have
r
>
r b
=
y bq b
=
y b
(
q
+ 1)
≥
0, which
says we have a nonnegative integer smaller than
r
in
T
, a contradiction. Thus, 0
≤
r
<
b
.
We have shown that
r
and
q
exist; now we must show that they are unique. Suppose we
have two equations
y
=
bq
1
+
r
1
(*)
y
=
bq
2
+
r
2
with 0
≤
r
1
<
b
and 0
≤
r
2
<
b
. Subtract the second from the first to get 0 =
b
(
q
1
q
2
) +
(
r
1
r
2
), or
r
2
r
1
=
b
(
q
1
q
2
). Thus,
b
|(
r
2
r
1
). Since 0
≤
r
1
<
b
and 0
≤
r
2
<
b
we get
b
<
r
2
r
1
<
b
. Because 0 is the only multiple of
b
between
b
and
b
(not including
b
and
b
),
b
divides
r
2
r
1
only if
r
2
r
1
= 0, or when
r
1
=
r
2
. Replacing
r
2
with
r
1
in the equa-
tions in (*), we easily establish that
q
1
=
q
2
, and thus
q
and
r
are indeed unique.
E
XAMPLES
.
We wish to find
q
and
r
as defined in the division algorithm for all of the fol-
lowing equations:
• 65 = 3
q
+
r
. Divide 65 by 3 to get
q
= 21,
r
= 2.
•
21 = 5
q
+
r
. If we simply divide
21 by 5, we get a quotient of
4, and a remainder
of
1. To place the remainder in the proper range, simply add 5 to it, while subtracting
1 from the quotient. This yields
q
=
5,
r
= 4. This is a simple way of calculating
q
and
r
when the dividend is negative.
Search WWH ::
Custom Search