Cryptography Reference
In-Depth Information
We may classify integers according to whether they are divisible by 2, as
follows.
Definition A.10
(
Parity)
If
a
, then we say that
a
is an
even integer
. In other words,
an even integer is one that is divisible by
2
.If
a/
2
∈
Z
, and
a/
2
∈
Z
, then we say that
a
is
an
odd
integer. In other words, an odd integer is one that is not divisible by
2
.
If two integers are either both even or both odd, then they are said to have the
same
parity
. Otherwise they are said to have
opposite
or
different parity
.
∈
Z
Of particular importance for divisibility is the following algorithm.
Theorem A.2
(
The Division Algorithm)
If
a
∈
N
and
b
∈
Z
, then there exist unique integers
q,r
∈
Z
with
0
≤
r<a
,
and
b
=
aq
+
r
.
Proof
. See page 599.
✷
Now we look more closely at our terminology. To say that
b
divides
a
is to
say that
a
is a
multiple
of
b
, and that
b
is a
divisor
of
a
. Also, note that
b
dividing
a
is equivalent to the remainder upon dividing
a
by
b
being zero. Any
divisor
b
=
a
of
a
is called a
proper divisor
of
a
. If we have two integers
a
and
b
, then a
common divisor
of
a
and
b
is a natural number
n
, which is a divisor of
both
a
and
b
. There are special kinds of common divisors that are the content
of our initial formal definition, first used in Chapter 1 (see page 75).
Definition A.11
(
The Greatest Common Divisor)
If
a,b
∈
Z
are not both zero, then the
greatest common divisor
or
gcd
of
a
and
b
is the natural number
g
such that
g
a
,
g
b
, and
g
is divisible by any
common divisor of
a
and
b
, denoted by
g
= gcd(
a,b
)
.
We have a special term for the case where the gcd is 1.
Definition A.12
(
Relative Primality)
If
a,b
, and
gcd(
a,b
)=1
, then
a
and
b
are said to be
relatively prime
or
coprime
. Sometimes the phrase
a
is prime to
b
is also used.
∈
Z
By applying the division algorithm, we get the following according to Euclid.
Theorem A.3
(
The Euclidean Algorithm
)
Let
a,b
b>
0)
, and set
a
=
r
−
1
,b
=
r
0
. By repeatedly applying
the division algorithm, we get
r
j
−
1
=
r
j
q
j
+1
+
r
j
+1
with
0
<r
j
+1
<r
j
for all
0
∈
Z
(
a
≥
j<n
, where
n
is the least nonnegative number such that
r
n
+1
=0
,in
which case
gcd(
a,b
)=
r
n
.
≤
Search WWH ::
Custom Search