hp40g+.book Page 12 Friday, December 9, 2005 1:03 AM
GCD(cn,bn) =
Part 2
Given the equation:
b3 ⋅ x + c3 ⋅ y = 1
GCD(cn,2) = GCD(bn,2) = 1
[1]
where the integers x and y are unknown and b3 and c3 are defined as in part 1 above:
1.Show that [1] has at least one solution.
2.Apply Euclid’s algorithm to b3 and c3 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:
a ⋅ x + b ⋅ y = 1
Therefore, the equation b3 ⋅ x + c3 ⋅ y = 1 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:
b3 ⋅ 1000 + c3 ⋅
Therefore, we have a particular solution: x = 1000, y =
The rest can be done on paper: c3 = b3 + 2 , b3 = 999 ⋅ 2 + 1
|
| ||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|