Mathematics for Computer Science

8.13. References 291

Problems for Section 8.3

Homework Problems

Problem 8.22.
TBA: Chebyshvev lower bound in prime density, based on Shoup pp.75–76

Problems for Section 8.4

Practice Problems

Problem 8.23.
Prove by induction that ifpis prime, then for alla 1 ;a 2 ;:::;anwheren 1 , if
pja 1
a 2


an, thenpdivides someai. You may assume the case fornD 2
which was proved Lemma 8.4.2.
Be sure to clearly state and label your Induction Hypothesis, Base case(s), and
Induction step.

Class Problems

Problem 8.24. (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.31)

(b)Describe in general how to find the gcd.m;n/and lcm.m;n/from the prime
factorizations ofmandn. Conclude that equation (8.31) holds for all positive
integersm;n.

Homework Problems

Problem 8.25.
The set of complex numbers that are equal tomCn

p
5 for some integersm;n
is calledZŒ

p

5ç. It will turn out that inZŒ

p
5ç, not all numbers have unique
factorizations.
A sum or product of numbers inZŒ

p

5çis inZŒ

p

5ç, and sinceZŒ

p
5çis a
subset of the complex numbers, all the usual rules for addition and multiplication
are true for it. But some weird things do happen. For example, the prime 29 has
factors:

(a)Findx;y 2 ZŒ

p

5çsuch thatxyD 29 andx¤ ̇ 1 ¤y.