Mathematics for Computer Science

8.13. References 283

Problems for Section 8.1

Practice Problems

Problem 8.1.
Prove that a linear combination of linear combinations of integersa 0 ;:::;anis a
linear combination ofa 0 ;:::;an.

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.^16

Problems for Section 8.2

Practice Problems

Problem 8.3.
Let

xWWD21212121;

yWWD12121212:

Use the Euclidean algorithm to find the GCD ofxandy.Hint:Looks scary, but
it’s not.

Problem 8.4.
Let

xWWD 1788  315  372  591000

yWWD 19 .9

(^22) /
 3712  533678  5929 :
(^16) 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.