Cryptography Reference
In-Depth Information
Proposition 11. (The Euclidean Algorithm.)
Let
r
0
=
c
and
r
1
=
b
be integers
such that
c
≥
b
> 0. If the division algorithm is successively applied to obtain
r
j
=
r
j
1
q
j
1
+
r
j
2
with 0 <
r
j
2
<
r
j
1
for
j
= 0, 1, 2, . . . ,
n
2 and
r
n
1
= 0, then (
c
,
b
) =
r
n
.
Proposition 12.
Let
x
and
y
be positive integers. Then
(
x
,
y
) =
s
n
x
+
t
n
y
where the
s
n
and
t
n
are defined recursively as
s
j
=
s
j
2
q
j
1
s
j
1
for
j
= 2, . . . ,
n
s
0
= 1
s
1
= 0
t
j
=
t
j
2
q
j
1
t
j
1
for
j
= 2, . . . ,
n
t
0
= 0
t
1
= 1
and the
q
j
and
r
i
are as in the Euclidean algorithm.
Proposition 13.
If
a
,
b
, and
c
are positive integers with
a
and
b
relatively prime, and
such that
a
|
bc
, then
a
|
c
.
Proposition 14.
Suppose
a
1
,
a
2
, . . . ,
a
n
are positive integers, and
p
is a prime which
divides
a
1
a
2
...
a
n
. Then there is an integer
i
such that 1
≤
i
≤
n
and
p
|
a
i
.
Proposition 15. (The Fundamental Theorem of Arithmetic.)
Every posi-
tive integer
n
greater than 1 can be written in the form
n
=
p
1
p
2
...
p
n
where each
p
i
is prime,
i
= 1, 2, ...,
n
. Furthermore, this representation is unique.
Proposition 16.
Let
a
and
b
be integers with
d
= (
a
,
b
). If
d
|
c
, the integer solutions
x
and
y
of the equation
ax
+
by
=
c
are
x
=
x
0
+
bn
/
d
,
y
=
y
0
an
/
d
, where
x
=
x
0
,
y
=
y
0
is a
particular solution. If
d
c
, the equation has no integer solutions.
Proposition 17.
Integers
a
and
b
are congruent modulo
m
iff
∃
an integer
k
such that
a
=
b
+
km
.
Proposition 18.
Let
a
,
b
and
c
be integers, and let
m
be a positive integer. Then
a.
a
a
(mod
m
)
b.
a
b
(mod
m
) implies
b
a
(mod
m
)
c.
a
b
(mod
m
) and
b
c
(mod
m
) implies
a
c
(mod
m
).
Proposition 19.
Let
a
,
b
, and
c
be integers, and let
m
be a positive integer. Suppose
a
b
(mod
m
). Then
Search WWH ::
Custom Search