Mathematics for Computer Science

Chapter 8 Number Theory284

(a)What is gcd.x;y/?

(b)What is lcm.x;y/?

(lcm isleast common multiple.)

Problem 8.5.
Use the Well Ordering Principle to prove that the gcd of anintegers is an integer
linear combination of these integers.
You may assume that the gcd of two integers is an integer linear combination of
them, which was proved in Theorem 8.2.2. You may also assume the easily verified
fact that
gcd.A[B/Dgcd.gcd.A/;gcd.B//; (8.18)

for any finite setsA;Bof integers.
Be sure to define and clearly label the set of counterexamples that you are as-
suming is nonempty.

Problem 8.6.
Show that the equation
axb .modn/

is solvable iff gcd.a;n/jb

Class Problems

Problem 8.7.
Use the Euclidean Algorithm to prove that

gcd.13aC8b;5aC3b/Dgcd.a;b/:

Problem 8.8.

(a)Use the Pulverizer to find integersx;ysuch that

x30Cy22Dgcd.30;22/:

(b)Now find integersx^0 ;y^0 with 0 y^0 < 30such that

x^030 Cy^022 Dgcd.30;22/