Mathematics for Computer Science

Chapter 8 Number Theory304

Now supposep > 2is a prime of the form 2 sC 1. For example, 21 C1;2^2 C
1;2^4 C 1 are such primes.

(b) Conclude from part (a) that if0 < k < p, then ord.k;p/is a power of 2.

(c)Prove that ord.2;p/D2sand conclude thatsis a power of 2.^17

Hint: 2 k 1 fork 2 Œ1::rçis positive but too small to equal0 .Zp/.

Homework Problems

Problem 8.61.
This problem is about finding square roots modulo a primep.

(a)Prove thatx^2 y^2 .modp/if and only ifx y .modp/orx  y
.modp/.Hint:x^2 y^2 D.xCy/.xy/

An integerxis called asquare rootofnmodpwhen

x^2 n .modp/:

An integer with a square root is called asquaremodp. For example, ifnis con-
gruent to 0 or 1 modp, thennis a square and it is it’s own square root.
So let’s assume thatpis an odd prime andn60 .modp/. It turns out there is
a simple test we can perform to see ifnis a square modp:

Euler’s Criterion

i. Ifnis a square modulop, thenn.p1/=21 .modp/.

ii. Ifnis not a square modulopthenn.p1/=21 .modp/.

(b)Prove Case (i) of Euler’s Criterion.Hint:Use Fermat’s theorem.

(c)Prove Case (ii) of Euler’s Criterion.Hint:Use part (a)

(d)Suppose thatp3 .mod4/, andnis a square modp. Find a simple expres-
sion in terms ofnandpfor a square root ofn.Hint:WritepaspD4kC 3 and
use Euler’s Criterion. You might have to multiply two sides of an equation bynat
one point.

(^17) Numbers of the form 22 kC 1 are calledFermat numbers, so we can rephrase this conclusion as
saying that any prime of the form 2 sC 1 must actually be a Fermat number. The Fermat numbers are
prime forkD1;2;3;4, but not forkD 5. In fact, it is not known if any Fermat number withk > 4
is prime.