Cryptography Reference
In-Depth Information
CHAPTER
4
Linear Diophantine Equations
and Linear Congruences
4.1
LINEAR DIOPHANTINE EQUATIONS
Diophantine equations are special types of equations. What characterizes them is that their
solutions must be integers. Consider the following equation:
12
x
+ 27
y
= 32.
This is called a linear diophantine equation in two variables. It is diophantine because we
are only interested in integer solutions for the variables, and it is linear because the highest
power of any variable in the equation is 1. The preceding equation has no integer solutions
for
x
and
y
(try to find one, if you like), whereas the following equation
12
x
+ 27
y
= 30
has infinitely many integral solutions! One solution is
x
=
20,
y
= 10. (Try to find some
more, or a formula which gives them all.) What distinguishes the first equation from the sec-
ond? Proposition 16 will provide the answer to this; it will tell us which such equations
have solutions, and which do not. The proof is constructive, in that it shows how to find the
solutions when they exist.
PROPOSITION 16.
Let
a
and
b
be nonzero 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.
Proof.
Suppose
x
and
y
are integers such that
ax
+
by
=
c
. (*)
Then, since
d
|
a
and
d
|
b
, by proposition 2,
d
also divides
c
. Thus, the contrapositive says
if
d
does not divide
c
then there are no integral solutions. So, suppose
d
|
c
. Proposition 12
demonstrates the existence of integers
s
and
t
such that
d
=
as
+
bt
.
Search WWH ::
Custom Search