Mathematics for Computer Science

8.9. What has SAT got to do with it? 217

Class Problems

Problem 8.2.
A number isperfectif it is equal to the sum of its positive divisors, other than itself.
For example, 6 is perfect, because 6 D 1 C 2 C 3. Similarly, 28 is perfect, because
28 D 1 C 2 C 4 C 7 C 14. Explain why 2 k^1 .2k1/is perfect when 2 k 1 is
prime.^7

Problems for Section 8.2

Class Problems

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

x
 50 Cy
 21 Dgcd.50;21/:

(b)Now find integersx^0 ;y^0 withy^0 > 0such that

x^0 
 50 Cy^0 
 21 Dgcd.50;21/

Problem 8.4.
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)Ifpjabfor some prime,p, thenpjaorpjb.

(d)Letmbe the smallest integer linear combination ofaandbthat is positive.
Show thatmDgcd.a;b/.

(^7) Euclid proved this 2300 years ago. About 250 years ago, Euler proved the
converse: every even perfect number is of this form (for a simple proof see
http://primes.utm.edu/notes/proofs/EvenPerfect.html)..) As is typical in
number theory, apparently simple results lie at the brink of the unknown. For example, it is not
known if there are an infinite number of even perfect numbers or any odd perfect numbers at all.