Mathematics for Computer Science

Chapter 8 Number Theory292

On the other hand, the number 3 is still a “prime” even inZŒ

p
5ç. More pre-
cisely, a numberp 2 ZŒ

p

5çis calledirreducibleoverZŒ

p
5çiff whenxyDp
for somex;y 2 ZŒ

p

5ç, eitherxD ̇ 1 oryD ̇ 1.

Claim.The numbers3;2C

p

 5 , and 2 

p

 5 are irreducible overZŒ

p

5ç.

In particular, this Claim implies that the number 9 factors into irreducibles over
ZŒ

p

5çin two different ways:

3 
 3 D 9 D.2C

p

5/.2

p

5/: (8.32)

SoZŒ

p
5çis an example of what is called anon-unique factorizationdomain.
To verify the Claim, we’ll appeal (without proof) to a familiar technical property
of complex numbers given in the following Lemma.

Definition.For a complex numbercDrCsiwherer;s 2 Randiis

p
1 , the
norm,jcj, ofcis

p

r^2 Cs^2.

Lemma.Forc;d 2 C,
jcdjDjcjjdj:
(b)Prove thatjxj^2 ¤ 3 for allx 2 ZŒ

p

5ç.

(c)Prove that ifx 2 ZŒ

p

5çandjxjD 1 , thenxD ̇ 1.

(d)Prove that ifjxyjD 3 for somex;y 2 ZŒ

p

5ç, thenxD ̇ 1 oryD ̇ 1.

Hint:jzj^22 Nforz 2 ZŒ

p

5ç.

(e)Complete the proof of the Claim.

Problems for Section 8.6

Practice Problems

Problem 8.26.
Prove that ifab .mod14/andab .mod5/, thenab .mod70/.

Class Problems

Problem 8.27. (a)Prove ifnis not divisible by 3, thenn^2 1 .mod3/.

(b)Show that ifnis odd, thenn^2 1 .mod8/.

(c)Conclude that ifpis a prime greater than 3, thenp^2  1 is divisible by 24.