Chapter 8 Number Theory218
Homework Problems
Problem 8.5.
Define the Pulverizer State machine to have:
statesWWDN^6
start stateWWD.a;b;0;1;1;0/ (whereab > 0)transitionsWWD.x;y;s;t;u;v/ !
.y;rem.x;y/; u sq; v tq; s; t/ (forqDqcnt.x;y/;y > 0):(a)Show that the following properties are preserved invariants of the Pulverizer
machine:
gcd.x;y/Dgcd.a;b/; (8.8)
saCtbDy;and (8.9)
uaCvbDx: (8.10)(b)Conclude that the Pulverizer machine is partially correct.(c)Explain why the machine terminates after at most the same number of transi-
tions as the Euclidean algorithm.
Problem 8.6.
Prove that the smallest positive integersabfor which, starting in state.a;b/,
the Euclidean state machine will makentransitions areF.nC1/andF.n/, where
F.n/is thenth Fibonacci number.
Hint:Induction.
In a later chapter, we’ll show thatF.n/ 'nwhere'is the golden ratio
.1C
p
5/=2. This implies that the Euclidean algorithm halts after at most log'.a/
transitions. This is a somewhat smaller than the 2 log 2 abound derived in the text
as a consequence of equation 8.4.
Problems for Section 8.3
Class Problems
Problem 8.7. (a)LetmD 295241171712 andnD 2372211211131179192. What
is the gcd.m;n/? What is theleast common multiple, lcm.m;n/, ofmandn?
Verify that
gcd.m;n/lcm.m;n/Dmn: (8.11)