8.13. References 285
Problem 8.9. (a)Use the Pulverizer to find gcd.84;108/
(b)Find integersx,ywith 0 y < 84such that
x 84 Cy 108 Dgcd.84;108/:(c)Is there a multiplicative inverse of 84 inZ 108? If not briefly explain why,
otherwise find it.
Problem 8.10.
Circle true or false for the following statements about the greatest
common divisor, andprovide counterexamplesfor those that are false.
(a)If gcd.a;b/¤ 1 and gcd.b;c/¤ 1 , then gcd.a;c/¤ 1. true false(b)Ifajbcand gcd.a;b/D 1 , thenajc. true false(c)gcd.an;bn/D.gcd.a;b//n true false(d)gcd.ab;ac/Dagcd.b;c/. true false(e)gcd.1Ca;1Cb/D 1 Cgcd.a;b/. true false(f)If an integer linear combination ofaandbequals 1, then so does some integer
linear combination ofaandb^2. true false
(g)If no integer linear combination ofaandbequals 2, then neither does any
integer linear combination ofa^2 andb^2. true false
Problem 8.11.
For nonzero integers,a,b, prove the following properties of divisibility and GCD’S.
(You may use the fact that gcd.a;b/is an integer linear combination ofaandb.
You maynotappeal to uniqueness of prime factorization because the properties
below are needed toproveunique factorization.)
(a)Every common divisor ofaandbdivides gcd.a;b/.
(b)Ifajbcand gcd.a;b/D 1 , thenajc.(c)Ifpjbcfor some prime,p, thenpjborpjc.(d)Letmbe the smallest integer linear combination ofaandbthat is positive.
Show thatmDgcd.a;b/.