Cryptography Reference
In-Depth Information
Since
d
|
c
, there is an integer
e
such that
de
=
c
. Multiply both sides of
d
=
as
+
bt
by
e
to obtain
c
=
de
= (
as
+
bt
)
e
=
a
(
se
) +
b
(
te
)
and we see then that
x
=
x
0
=
se
,
y
=
y
0
=
te
is a particular solution to (*). Now, let
x
=
x
0
+
bn
/
d
,
y
=
y
0
an
/
d
, where
n
is any integer. Note that this is also a solution:
ax
+
by
=
ax
0
+
abn
/
d
+
by
0
ban
/
d
=
ax
0
+
by
0
=
c
.
We must show that every solution of (*) must be of this form. Suppose
x
and
y
are inte-
gers such that
ax
+
by
=
c
. Since
ax
0
+
by
0
=
c
, we subtract and rearrange terms to get
(
ax
+
by
)
(
ax
0
+
by
0
) = 0
a
(
x x
0
) +
b
(
y y
0
) = 0
a
(
x x
0
) =
b
(
y
0
y
).
Divide both sides of the previous equation by
d
to get
(
a
/
d
)(
x x
0
) = (
b
/
d
)(
y
0
y
).
Proposition 7 tells us that (
a
/
d
,
b
/
d
) = 1, and we use proposition 13 to then show that
(
a
/
d
)|(
y
0
y
). Thus, we can write
an
/
d
=
y
0
y
for some integer
n
, and so
y
=
y
0
an
/
d
.
If we insert this value of
y
back into
a
(
x x
0
) =
b
(
y
0
y
)
we get
a
(
x x
0
) =
b
(
an
/
d
), and hence
x
=
x
0
+
bn
/
d
, as desired.
E
XAMPLE
.
The previous theorem allows us to find all solutions of the two equations presented
at the beginning of this chapter. Consider again the equation 12
x
+ 27
y
= 32. The gcd of 12
and 27 is 3, which does not divide 32. Thus, this equation has no integer solutions. But the
second equation, 12
x
+ 27
y
= 30, has infinitely many integer solutions since 3|30. We find
all the solutions by first finding a particular solution. First, note that integers
s
and
t
exist
which solve 12
s
+ 27
t
= (12, 27) = 3, and proposition 12 tells us how to compute them.
They are
s
=
2,
t
= 1. Thus, since 12(
2) + 27
1 = 3, we can multiply both sides of the
equation by 10 to get 12(
20) + 27
10 = 30. So a particular solution to 12
x
+ 27
y
= 30 is
x
0
=
20,
y
0
= 10. Proposition 16 says all of the solutions to 12
x
+ 27
y
= 30 are then given
by
x
=
20 + 27
n
/3 =
20 + 9
n
, and
y
= 10
12
n
/3 = 10
4
n
,
∀
integers
n
.
E
XAMPLE
.
Diophantine equations have real-world applications as well. Suppose you are at
the grocery store with 4 dollars and 27 cents. Apples sell for 35 cents, and oranges for 49
cents. What combination of apples and oranges (if any) will exhaust your money? (Assume
there is no sales tax.) We wish to find all integer solutions to the equation 35
x
+ 49
y
= 427.
First, compute (35, 49) = 7, and note that 427 = 61
7, so 7|427. Thus, the equation has infi-
nitely many solutions. We find a particular solution by first solving 35
s
+ 49
t
= 7, and get
s
= 3,
t
=
2. Multiply both sides of 35
3 + 49(
2) = 7 by 61 to get 35
183 + 49(
122)
= 427, and get a particular solution to our equation; that is,
x
0
= 183, and
y
0
=
122. The
Search WWH ::
Custom Search