Cryptography Reference
In-Depth Information
APPENDIX
I
List of Propositions
Proposition 1.
If
x
,
y
, and
z
are integers with
x
|
y
and
y
|
z
, then
x
|
z
.
Proposition 2.
If
c
,
x
,
y
,
m
, and
n
are integers such that
c
|
x
and
c
|
y
, then
c
|(
mx
+
ny
).
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 quo-
tient,
r
the remainder,
b
the divisor, and
y
the dividend.
Proposition 4.
Every positive integer greater than 1 has a prime divisor.
Proposition 5.
There are infinitely many primes.
Proposition 6.
If
n
is composite, then
n
has a prime factor not exceeding the square root
of
n
.
Proposition 7.
Let
x
,
y
, and
z
be integers with (
x
,
y
) =
d
. Then
a.
(
x
/
d
,
y
/
d
) = 1
b.
(
x
+
cy
,
y
) = (
x
,
y
).
Proposition 8.
The gcd of integers
x
and
y
, not both zero, is the least positive integer
that is a linear combination of
x
and
y
.
Proposition 9.
(
a
1
,
a
2
,
a
3
, ...,
a
n
) = ((
a
1
,
a
2
),
a
3
, ...,
a
n
).
Proposition 10.
If
c
and
d
are integers and
c
=
dq
+
r
where
q
and
r
are integers, then
(
c
,
d
) = (
d
,
r
).
Search WWH ::
Custom Search