Cryptography Reference
In-Depth Information
A.2 Basic Arithmetic
Basic Arithmetic
A
natural number
n
is one of the so-called counting numbers consisting of
the set
(where the ellipsis
...
means
ad infinitum
or
“up to infinity”). The natural numbers, and their negatives, together with 0
is called the set of
integers
, namely,
{
1
,
2
,
3
,...
}
, denoted by
N
{
...,
−
3
,
−
2
,
−
1
,
0
,
1
,
2
,
3
,...
}
, denoted by
Z
(where the ellipsis on the left
...
, denotes from negative infinity and on the
right,
ad infinitum
).
Definition A.8
(
Primes)
If
p
(
p>
1)
and
p
has no positive divisors, other than itself and
1
,
then
p
is a prime number, or simply
a prime
.If
n
∈
N
∈
N
,n>
1
, and
n
is not a
prime, then
n
is
composite
.
Once we have primes as the building bricks of the integers, we have a means
of representing any given integer.
Definition A.9
(
Canonical Prime Factorization)
If
n
,n >
1
, then the factorization
n
=
i
=1
p
a
i
, where
a
i
∈
N
∈
N
, and
2
≤
p
1
<p
2
<...<p
N
, is the
canonical prime factorization
of
n
.
Moreover, those representations are essentially unique as the following fun-
damental fact shows.
Theorem A.1
(
The Fundamental Theorem of Arithmetic)
Let
n
∈
,n >
1
. f
n
=
i
=1
p
i
=
i
=1
q
i
, where the
p
i
and
q
i
are primes, then
r
=
s
, and the factors are the same if their order is ignored.
N
Proof
. See [167, Theorem 1.4.2, page 44].
✷
= 0, then
a/b
is a
rational number
. The set of all rational
numbers is denoted by
If
a,b
∈
Z
with
b
Q
. Rational numbers have period
ic
decimal expansions,
such as 1
/
3=0
.
3333
...
, but those numbers, such as
√
2, do not have any re-
peated pattern in their decimal expansions. These numbers are called
irrational
numbers
. The collection af all the rational and irrational numbers is called the
set of
real numbers
, denoted by
R
. The collection of only the
positive
reals is
+
. Also, if
x
, then
x
n
=
x
denoted by
R
∈
R
and
n
∈
N
·
x
···
x
multiplied
n
times is called an
exponentiation
of
x
.
, then to say that
b
divides
a
, denoted by
b
a
,
means that
a
=
bx
for a
unique
x
Divisibility
.If
a,b
∈
Z
, denoted by
x
=
a/b
. Note that the
existence and uniqueness of
x
implies that
b
cannot be 0. We also say that
a
is
divisible
by
b
.If
b
does
not
divide
a
, then we write
b
∈
Z
a
, and say that
a
is
not
divisible
by
b
. Note that
x
is not unique for
a
=
b
= 0. We say that
division by
zero is undefined
.
Search WWH ::
Custom Search