HP 40gs User Manual
Page 286
16-12
Step-by-Step Examples
Part 2
Given the equation:
[1]
where the integers x and y are unknown and b
3
and c
3
are defined as in part 1 above:
1. Show that [1] has at least one solution.
2. Apply Euclid’s algorithm to b
3
and c
3
and find a
solution to [1].
3. Find all solutions of [1].
Solution: Equation [1] must have at least one solution,
as it is actually a form of Bézout’s Identity.
In effect, Bézout’s Theorem states that if a and b are
relatively prime, there exists an x and y such that:
Therefore, the equation
has at least
one solution.
Now enter
IEGCD(B(3),
C(3)).
Note that the
IEGCD
function can be found on
the
INTEGER submenu of
the
MATH menu.
Pressing
a number
of times returns the result
shown at the right:
In other words:
Therefore, we have a particular solution:
x = 1000, y = –999.
The rest can be done on paper:
,
GCD c
n
b
n
,
(
)
GCD c
n
2
,
(
) GCD b
n
2
,
(
)
1
=
=
=
b
3
x c
3
y
1
=
⋅
+
⋅
a x
⋅
b y
⋅
+
1
=
b
3
x
⋅
c
3
y
⋅
+
1
=
b
3
1000
×
c
3
999
–
(
)
×
+
1
=
c
3
b
3
=
2
+
b
3
999 2 1
+
×
=
hp40g+.book Page 12 Friday, December 9, 2005 1:03 AM