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