Elementary Number Theory (Math 780 instructors notes) (1996) WW

Math 780: Elementary Number Theory

(Instructor's Notes)*

What Is It?:

Elementary Number Theory is the study of numbers, and in particular the study of

the set of positive integers.

Does \elementary" mean \easy"? No.

Example.

Consider a positive integer

m <

, and view it as a four digit number

(with possible leading digit 0). Suppose all four digits are distinct. Let

be the number

obtained by putting the digits of

in increasing order, and let

be the number obtained

by putting the digits in decreasing order. Let

. Now repeat the process with

in place of

. Continue. What happens? How can this be explained?

Rational and Irrational Numbers:

Dene them.

Theorem 1.

is irrational.

Give typical proof.

Theorem 2.

An irrational number to an irrational power can be rational.

Proof:

Consider

and

Theorem 3.

is irrational.

Proof:

Assume

a=b

with

and

positive integers, and set

(

)

! =

Then

< <

(

+ 1)

= 1

On the other hand, the middle expression in (

) is an integer. Hence, we have a contra-

diction and

is irrational.

Open Problem.

irrational?

Open Problem.

irrational?

*These notes are from a course taught by Michael Filaseta in the Fall of 1997.

Homework:

(1) Let

denote the set of irrational numbers. Determine whether each of the

following is true or false. If it is true, simply state so. If it is false, state so and give a

counterexample.

(a)

and

implies

(b)

and

implies

(c)

and

implies

and

(d)

and

implies

(e)

and

implies

(2) Prove that

is irrational whenever

is a positive integer which is not a square.

Give an argument similar to that given for

2. Clarify where you feel we are using certain

properties of the integers that we should have perhaps discussed rst.

(3) Prove that

2 +

3 is irrational.

(4) Prove that

2 +

3 +

5 is irrational.

(5) Prove that log

3 is irrational.

(6) Prove that

is irrational using an argument similar to that given above for

Divisibility Basics:

Denition. Let

and

be integers. Then

divides

(or

is a divisor of

divisible by

) if there is an integer

such that

Notation. We write

divides

, and we write

does not divide

Denition. An integer

is prime (or is a prime) if it is

1 and divisible by no

other positive integer other than 1 and itself. (In Algebra, the condition that

1 is

replaced by

1.)

The division algorithm.

Theorem 4.

= 0

and

are any integers, then there exist unique integers

(called the

quotient) and

(called the remainder) with

r <

such that

Proof.

Let

be the least non-negative integer in the double sequence

:::;b

a;b

a;b;b

a;b

+ 2

a;::: :

Let

be such that

. Since (

)

is in the double sequence and

< b

we have (

)

0. Thus,

r <

. Also,

0. This proves the existence of

and

as in the theorem.

For

;

, suppose

and

are integers such that

and 0

Then
(

)

(

)

(

) = 0

This implies

(

). On the other hand,

(

;

). Hence,

. Now,

(

) implies

, establishing the uniqueness of

and

as in the theorem.

Denition and Notation. Let

and

be integers with at least one non-zero. The

greatest common divisor of

and

is the greatest integer dividing both

and

. We

denote it by gcd(

n;m

) or (

n;m

Note that if

is a non-zero integer, then (0

) =

Theorem 5.

and

are integers with at least one non-zero, then there exist

integers

and

such that

= (

a;b

)

. Moreover,

x;y

(

a;b

) :

Proof.

Let

x;y

. Let

denote the smallest positive integer in

Let

and

be integers for which

. Theorem 5 follows from the following

claims.

Claim 1.

Reason:

Clear.

Claim 2.

Reason:

Let

. By Theorem 4, we have integers

and

with

and 0

r < d

. On the other hand,

= (

)

(

)

(

) +

(

)

It follows that

= 0 and

Claim 3.

and

Reason:

Use Claim 2 together with

and

Claim 4.

= (

a;b

Reason:

Since

, (

a;b

)

so that (

a;b

)

. Since

and

is a common

divisor of

and

. By the denition of greatest common divisor,

= (

a;b

The Fundamental Theorem of Arithmetic (Unique Factorization):

Theorem 6.

Every integer

n >

can be written uniquely as a product of primes in

the form

;

where

< p

are distinct primes and

;::: ;e

and

are positive integers.

Comment:

In other words, every positive integer

can be written uniquely as a

product of primes except for the order in which the prime factors occur.

Lemma.

is a prime and

and

are integers such that

, then either

Proof of Lemma.

Let

be an integer such that

, and suppose

. We

wish to show

. By Theorem 5, there are integers

and

such that

= 1. Hence,

abx

pby

(

). Thus,

Proof of Theorem 6.

First, we prove that

is a product of primes by induction.

The case

= 2 is clear. Suppose it is true for

less than some integer

m >

2. If

prime, then

is a product of primes. If

is not prime, then

with

and

integers

in (1

). Since

and

are products of primes by the induction hypothesis, so is

Now, we prove uniqueness by induction. Again, one checks

= 2 directly. Suppose

uniqueness of the representation of

as a product of primes as in the theorem holds for

n <

. Let

;::: ;p

(not necessarily distinct) and

;::: ;q

(not necessarily distinct) denote

primes such that

. Observe that

. Hence, the lemma

implies

. This in turn implies

, or

. Continuing, we

deduce that

for some

;

;::: ;t

. As

and

are primes, we obtain

Now,

m=p

and the induction hypothesis imply that the

primes

;::: ;p

are the same as the primes

;::: ;q

in some order. This

implies the theorem.

Homework:

(1) Let

, and

denote positive integers. Prove each of the following:

(a)

and

implies

(b)

implies

(c)

and

implies

(2) Prove that if

is an integer

2 which is composite (i.e., not prime), then

has a

prime divisor which is

(3) Let

log

prime

. Prove that the elements of

are linearly independent

over the rationals. (This is an example of an innite set of real numbers which is linearly

independent over

(4) Observe that

+ 4

is prime if

= 1. Prove that

+ 4

is composite if

is an

integer

Euclidean Algorithm:

Review. In grade school, we learned to compute the greatest common divisor of two

numbers by factoring the numbers. For example, (77

;

119) = (7

;

17) = 7. Now,

try (3073531

;

304313) this way. What's the moral?

Theorem 7. (The Euclidean Algorithm)

Let

and

be positive integers. Set

and

. Dene

;::: ;r

and

by the equations

with

< r

with

< r

...

with

< r

with

= 0

where each

and

is in

. Then

(

a;b

) =

Back to examples. Compute (3073531

;

304313) this way. Not to be misleading,

compute (2117

;

3219) using the Euclidean Algorithm.

Proof:

Let

= (

a;b

). Then one obtains

for 0

+1 inductively, and hence

. Thus,

(since

0). Similarly, one obtains

divides

for 1

. It

follows that

is a divisor of

and

. By the denition of (

a;b

), we deduce

= (

a;b

Solutions to

. From Theorem 5, we need only consider

(

a;b

). One

can nd solutions when

= 1 by making use of the Euclidean Algorithm (backwards).

Show how the complete set of solutions for general

can be obtained from this. Also,

mention the connection with the simple continued fraction for

a=b

Example.

Solve 3219

+ 2117

= 29. The solutions are the (

x;y

) of the form

= 25

2117

and

38 +

3219

for

Theorem 8.

Let

and

be positive integers. The Euclidean Algorithm for calcu-

lating

(

a;b

)

takes

2([log

] + 1)

steps (i.e, divisions).

Proof:

Let

= [log

]+1. In the notation of Theorem 7, we want

. Assume

+ 1. We show rst that

< r

2 for

;

;::: ;n

. If

2, then

< r

2. If

> r

2, then

where

= 1. Hence, in

this case,

< r

2. Hence, in either case,

< r

2. We deduce that

< r

Therefore,

s <

log

. This contradicts that

= [log

] + 1

log

Homework:

(1) For each of the following, calculate (

a;b

) and nd a pair of integers

and

for which

= (

a;b

(a)

= 289 and

= 1003

(b)

= 3569 and

= 1333

(2) Find the complete set of integer solutions in

and

821

+ 1997

= 24047

Modulo Arithmetic:

Denition. Two integers

and

are congruent modulo an integer

(

Notation.

(mod

Examples.

What will be the time 1000 hours from now? On what day of the week

will September 3 be in 1998?

Theorem 9.

Let

, and

be integers. Then each of the following holds.

(i) If

(mod

)

and

(mod

)

, then

(mod

)

(ii) If

(mod

)

and

(mod

)

, then

(mod

)

(iii) If

(mod

)

and

(mod

)

, then

(mod

)

(iv) If

(mod

)

and

, then

(mod

)

Proof:

Give the obvious proofs. In particular, in (iii), observe that

and

for some integers

and

so that

= (

)

+ (

)

= (

)

and the result follows.

Comment:

Note that (iii) implies that if

(mod

) and

is a positive integer,

then

(mod

Theorem 10.

Let

be a positive integer, and let

be an integer relatively prime

. Then there is an integer

for which

1 (mod

)

Proof:

Use that there are integers

and

such that

= 1.

Comments:

The

in Theorem 10 is called the inverse of

modulo

. It is unique

modulo

since (

a;m

) = 1 and

mod

implies

(mod

). Also, note that

if (

a;m

)

= 1, then

does not have an inverse modulo

(since

1 =

would be

impossible).

Examples.

(1) Explain the usual tests for divisibility by each of 2, 3, 4, 5, 6, 9, and 11.

(2) What is the last digit of 7

1000

(3) Determine the last digits of the numbers in the sequence 23

;

2323

;

23(23

)

;:::

(4) Is 3752743877345287574827904870128487127731 a sum of two squares?

(5) Let

= 2(2

) + 1 (the

th Fermat number). Explain why 641

. Use that

641 = 2

+ 5

and 641 = 5

+ 1.

Comments:

A regular

-gon is constructible with straight-edge and compass if

and only if

= 2

3 where

and

are non-negative integers and

;::: ;p

are

distinct Fermat primes. The only known Fermat primes are

for 0

4 (i.e., 3, 5,

17, 257, and 65537), and it is believed that these are the only Fermat primes.

Homework:

(1) Prove that if

7 (mod 8)

;

then

is not a sum of 3 squares.

(2) Prove that for every non-constant polynomial

(

) with integer coecients, there is

an integer

such that

(

) is composite.

(3) A large furniture store sells 6 kinds of dining room suites, whose prices are $231,

$273, $429, $600.60, $1001, and $1501.50, respectively. Once a South American buyer

came, purchased some suites, paid the total amount due, $13519.90, and sailed for South

America. The manager lost the duplicate bill of sale and had no other memorandum of

each kind of suite purchased. Help him by determining the exact number of suites of

each kind the South American buyer bought. (Don't forget to show that your solution is

unique.)

(4) Find (with proof) the smallest integer

1 dividing at least one number in the sequence

;

331

;

3331

;

33331

;:::

Fermat's Little Theorem:

Theorem 11.

For any prime

and any integer

is divisible by

Comments:

In other words, with

and

as above,

(mod

). The theorem

is equivalent to: if

is a prime and

is an integer with (

a;p

) = 1 (in other words, with

not dividing

), then

1 (mod

Proof 1:

Use induction. The theorem holds with

= 1. If it holds for

, then

(

+ 1)

+ 1

+ 1 (mod

)

This proves the theorem for positive integers. Since every integer is congruent to a positive

integer modulo

, the result follows.

Proof 2:

Again, we may suppose

a >

0. Fix

colors. The number of necklaces

with

beads, each bead colored with one of the

colors (allowing repetitions), having at

least two beads colored dierently is (

)

. Here, we count necklaces as distinct if one

cannot be obtained from the other by a rotation (we don't allow ipping necklaces over).

Thus, (

)

, and the result follows.

Fermat's Little Theorem can be used for determining that a given integer

composite as follows:

(i) Check

for small prime factors (this step isn't necessary but is reasonable).

(ii) Write

in base 2, say

with

;

for each

and

[log

log 2] + 1.

(iii) Compute 2

(mod

) by squaring.

(iv) Calculate

;

;::: ;N

such that

(mod

)

(v) If

= 2, then

is composite. Otherwise the test is inconclusive.

Comments:

The algorithm works for establishing that \most" composite numbers

are composite (i.e., for most composite numbers,

= 2). If

= 2, then one can check if

3 (mod

). Note that the algorithm takes on the order of log

steps so that the

algorithm is a polynomial time algorithm (it runs in time that is polynomial in the length

of the input - elaborate on this). There are no polynomial time algorithms that determine

conclusively whether an arbitrary integer is composite.

Denitions. A

pseudo-prime

is a composite number

n >

1 satisfying 2

2 (mod

probable prime

is an integer

n >

1 satisfying 2

2 (mod

). (Explain the reasons

behind these denitions.)

Examples.

Explain why 341 = 11

31 is a pseudo-prime. Explain why

= 2

is a probable prime. (Note that for

n >

is really probably not a prime.)

Denition. An

absolute pseudo-prime

(or a

Carmichael number

) is a composite

number

n >

1 such that

(mod

) for every integer

Example.

Explain why 561 = 3

17 is an absolute pseudo-prime.

Comment:

Alford, Granville, and Pomerance have shown that there exist innitely

many absolute pseudo-primes. The much easier result that there exist innitely many

pseudo-primes is in the next list of homework problems.

Euler's Theorem:

Denition and Notation. For a positive integer

, we dene

(

) to be the number

of positive integers

which are relatively prime to

. The function

is called Euler's

-function.

Examples.

(1) = 1,

(2) = 1,

(3) = 2,

(4) = 2,

(

) =

1 for every prime

and

(

) = (

1)(

1) for all primes

and

Theorem 12.

For every positive integer

and every integer

relatively prime to

, we have

(

)

1 (mod

)

Proof:

= 1, the result is clear. We suppose as we may then that

n >

Let

;::: ;a

(

)

be the

(

) positive integers

relatively prime to

. Consider the

numbers
(

)

a;a

a;::: ;a

(

)

Note that no two numbers in (

) are congruent modulo

since (

a;n

) = 1 and

(mod

) implies

(mod

) so that

. Now, x

;

;::: ;

(

)

. There are

integers

and

such that

and 0

r < n

. Since (

a;n

) = 1 and

n >

1, we

obtain

= 0 and (

r;n

) = 1. Thus,

for some

;

;::: ;

(

)

. Hence, for each

;

;::: ;

(

)

, there is a

;

;::: ;

(

)

for which

(mod

). Since

the numbers

are distinct modulo

, we deduce that the numbers in (

) are precisely

;::: ;a

(

)

in some order. Therefore,

(

)

(

)(

)

(

)

(

)

(

)

(mod

)

Since gcd(

(

)

) = 1, we obtain

(

)

1 (mod

) as desired.

Wilson's Theorem:

Theorem 13.

For every prime

(

1)!

1 (mod

)

Proof:

= 2, the result is clear. We consider now the case

p >

2. Let

;

;::: ;p

. For every

, there is a unique

satisfying

1 (mod

= 1 or

1, then

. The converse statement also holds since

implies (

1)(

+ 1) =

1 is divisible by

so that

1 (mod

) or

(mod

). The remaining elements of

can be grouped in (

2 pairs (

a;a

), say

(

)

;::: ;

(

), so that

(

1)!

(

)

(

)

(

1 (mod

)

Comment:

The converse of Wilson's Theorem also holds (see homework problem

(4) below).

Homework:

(1) Prove that 1105 and 1729 are absolute pseudo-primes.

(2) Prove that if

is a pseudo-prime, then 2

1 is a pseudo-prime. (Note that this

implies that there are innitely many pseudo-primes.)

(3) Find the smallest positive integer

such that

1 (mod 756) for every integer

which is relatively prime to 756.

(4) Prove the converse of Wilson's Theorem. More specically, prove that if

is an integer

1 for which (

1)!

1 (mod

)

;

then

is a prime.

(5) Let

and

be integers with

p >

1 and

d >

Prove that

and

are both prime

if and only if

(

1)!

+ (

+ 1

is an integer.

Public-Key Encryption:

Example.

The following information is made public:

If someone wishes to send me, Jim, a message, use the following. Let

= 49601

and

= 247

. As your alphabet use

for a blank,

for \a",

for \b",

for \c", etc.

(Eg. \No" would be represented \1415".) Suppose your message is

. Let

(mod

)

where

E < N

. Then

is your actual message, and

is the encrypted message.

Publish

in the personals tomorrow, and I alone will know your actual message

Note: To do this properly, one needs

to be considerably larger. Here, only two letter

words can actually be sent (though a combination of two letter words including blanks can

make for a sentence).

The secret. The number

is a product of two large primes (suciently large so

only Jim knows how

factors). In the example above,

= 193

257. Since Jim knows

how

factors, he can also compute

(

). In this case,

(

) =

(193

257) = 192

256 = 49152

Using the Euclidean algorithm, for example, Jim also knows a positive integer

such that

1 (mod

(

))

Here,

= 199. Thus, Jim (and only Jim) can calculate

(

)+1

(mod

)

In other words, Jim can gure out

given the value of

Comment:

This approach makes for a good public-key encryption scheme because

the value of

(

) cannot

seemingly

be computed without the knowledge of how

factors.

To clarify, it is possible to compute

(

) without having the factorization of

, but

the fastest known methods at the time for computing

(

) when

is large involve rst

factoring

Further example. Someone has sent the encrypted message

= 48791 to Jim. What

should he do (assuming he wants to know what the message says)? Note that

= 199 = 2

+ 2

+ 2 + 1

By squaring, he computes

48791 (mod

)

11287 (mod

)

21001 (mod

)

39510 (mod

)

47029 (mod

)

18251 (mod

)

28286 (mod

)

33666 (mod

)

Hence,

(33666)(28286)(21001)(11287)(48791)

809 (mod

)

The message sent was, \Hi".

Homework:

(1) Someone wants to send Jim the message, \No". Compute the encrypted message

and then verify your work by decoding

. (Show your work using steps similar to that

shown above.)

Certied Signatures:

The problem. Jim has two friends, Brian and Jason. Jim just got an encrypted

message

in the personals. I won't specify what

was because it might upset Jim (since

you can now decode Jim's messages because you too know how

factors). The message

to Jim in the personals read:

Jim, I really like your idea for having secret messages sent to you so that no one else can

know what's being said in the personals besides you. In fact, I liked it so much that I

thought I would send you a quick note to let you know what I think of you. Here it is:

. Sincerely, Brian.

In the above message,

is actually some number. The problem is that when Jim decoded

, he was not very happy about what Brian had to say (and you wouldn't be either if

you happened to be the one the message

was intended for). As a consequence, Jim and

Brian never talked to each other again, and Jim's best friend became Jason. What Jim

never did gure out though was that Jason actually wrote the message.

Solution. One can sign a message simply by adding ones name to the end of a message

and then encrypting the whole message, name and all. Unfortunately, this is precisely

what Jason did; he added Brian's name to the end of the message sent to Jim. When Jim

read it, he actually thought that Brian must have sent it since no one else could possibly

have encrypted Brian's name. He never realized that actually anyone could encrypt Brian's

name. There is however a proper way to certify a signature in an encrypted message. Let's

suppose that Brian and Jason also decided to use the same encrypting scheme as Jim. In

particular, Brian has some number

that he alone knows how to factor and some number

, both of which he makes public. And suppose he has computed

(his secret exponent for

decoding messages sent to him) satisfying

1 (mod

(

)). Note that

= 0218090114

represents Brian's name. Brian computes the value of

(mod

) with 0

T < N

Since

is only known to Brian,

is something only Brian knows. If Brian wants to truly

sign a message to Jim (so that Jim knows it is from him) he now simply adds

to the

end of his message and then encrypts the entire message (with

). When Jim receives

the message, he decodes it. To verify the message is from Brian, he takes the value of the

signature

given at the end of the message and computes

modulo

(note that both

and

are known to him). Since

1 (mod

(

)), Jim obtains

this way (i.e.,

(mod

)). He then sees that the message is from Brian. The main point is that

since

is only known to Brian, he alone could have computed the value of

given at the

end of the message to Jim.

The rest of the story. Actually, Brian did have numbers

and

that he made

public, and Jason had such numbers as well. Jason sent a friendly message to Brian which

Jason signed with a certied signature. Brian responded with a message containing his

own certied signature. It was then that Jason sent his message to Jim. At that point,

Brian had given Jason the value of

(Brian's certied signature), so Jason used Brian's

certied signature in his message to Jim. So how might this problem be avoided? (Discuss

possible answers.)

The Chinese Remainder Theorem:

Theorem 14.

Let

;::: ;m

be pairwise relatively prime positive integers. Let

;::: ;b

be arbitrary integers. Then the system

(mod

)

...

(mod

)

has a unique solution modulo

Proof (Constructive):

Let

. For

;

;::: ;k

, dene

M=m

. If

and

are in

;

;::: ;k

with

, then (

) = 1. It follows that for

each

;

;::: ;k

, (

) = 1 so that there is an

such that

1 (mod

)

We set

. Then

(mod

)

for

;

;::: ;k

This proves the existence of a solution to the system of congruences in the statement of

the theorem.

For uniqueness, suppose that

also satises

(mod

) for each

;

;::: ;k

Then

0 (mod

) for each such

, and we deduce that each

divides

. As

the

are relatively prime, we obtain

(

). In other words,

(mod

Examples.

(1) Solve 17

3 (mod 210) by using the Chinese Remainder Theorem. Use that

210 = 2

7 and observe that solving 17

3 (mod 210) is equivalent to solving

the system

1 (mod 2),

0 (mod 3),

1 (mod 5), and

1 (mod 7). The

latter is equivalent to

1 (mod 14) and

9 (mod 15). Therefore,

1 + 9

(

111

99 (mod 210)

(2) If

and

are integers, then the point (

a;b

) is called a

lattice point

. A

visible

lattice point is one for which gcd(

a;b

) = 1 (it is visible from the origin). Prove that there

are circles (or squares) in the plane which are arbitrarily large and have the property that

each lattice point in the circles (or squares) is not visible. (Use that there are innitely

many primes.)

(3) Prove that there exists a positive integer

for which 2

+ 1 is composite for

all positive integers

. (It is known that

= 78557 has this property and it is an open

problem to determine whether or not 78557 is the smallest such

.) We use the Fermat

numbers

= 2

+ 1. Recall that

is prime for 0

4 and

is composite with

641 a \proper" divisor. Explain the following implications:

1 (mod 2) =

)

+ 1

0 (mod 3)

provided

1 (mod 3)

;

2 (mod 4) =

)

+ 1

0 (mod 5)

provided

1 (mod 5)

;

4 (mod 8) =

)

+ 1

0 (mod 17)

provided

1 (mod 17)

;

8 (mod 16) =

)

+ 1

0 (mod 257)

provided

1 (mod 257)

;

16 (mod 32) =

)

+ 1

0 (mod 65537) provided

1 (mod 65537)

;

32 (mod 64) =

)

+ 1

0 (mod 641)

provided

1 (mod 641)

;

0 (mod 64) =

)

+ 1

0 (mod

641) provided

1 (mod

641)

By the Chinese Remainder Theorem, there are innitely many positive integers

satisfying

the conditions on

on the right above (note that the last modulus is relatively prime to

the others). Also, every integer

can be seen to satisfy at least one of the congruences

involving

on the left. It follows that there are innitely many positive integers

such

that for every positive integer

, the number 2

+ 1 is divisible by one of 3, 5, 17, 257,

65537, 641, and

641. If

is suciently large with this property, then it will suce for

a value of

for this example

Comments:

If every integer

satises at least one of a set of congruences

(mod

), for

= 1

;::: ;k

, then the congruences are said to form a covering of the

integers. It is unkown whether or not there is a covering consisting of distinct odd moduli

1. Also, it is not known whether or not there is a constant

C >

0 such that every

covering using distinct moduli contains a modulus

< C

Homework:

(1) Find the smallest positive integer

n >

2 such that 2 divides

, 3 divides

+ 1, 4

divides

+ 2, 5 divides

+ 3, and 6 divides

+ 4. Prove your answer is the least such

(2) A

squarefree number

is a positive integer

which is not divisible by a square

1. For

example, 1, 2, 3, 5, and 6 are squarefree but 4, 8, 9, and 12 are not. Let

be an arbitrary

positive integer. Prove that there is a positive integer

such that

;::: ;m

are each NOT squarefree. (Use that there are innitely many primes.)

(3) Calculate the remainder when the number 123456789101112

:::

19781979 is divided by

1980.

(4) Let

and

be positive integers, and let

= 2

for all positive

integers

. Find relatively prime

and

such that every

, with

0, is composite.

(Hint: I used the system of congruences

0 (mod 2),

1 (mod 3),

3 (mod 4),

5 (mod 6), and

9 (mod 12). You should convince yourselves that this system

forms a covering of the integers. The idea is to make each

divisible by a prime where the

prime depends on which of these congruences

satises. For example, suppose I choose

and

so that

1 (mod 3) and

1 (mod 3). Then for

satisng

3 (mod 4),

which is one of the congruences in the system above, we will have that

is divisible by

3. To see this consider the sequence

modulo 3 keeping in mind that

1 (mod 3) and

1 (mod 3). The main problem should be guring out what primes to use.)

Euler's Phi Function Revisited:

Recall

(

) is the number of positive integers

that are relatively prime to

Lemma 1.

For every prime

and every positive integer

(

) =

Proof.

The number of multiples of

which are

. The result follows.

Lemma 2.

For relatively prime positive integers

and

(

) =

(

)

(

)

Proof.

= 1 or

= 1, then the result is clear; so we suppose

m >

1 and

n >

Let

;::: ;a

(

)

denote the positive integers

which are relatively prime to

, and

let

;::: ;b

(

)

denote the positive integers

which are relatively prime to

. Suppose

now that

;

;::: ;mn

and (

k;mn

) = 1. Dene

and

(mod

)

;

a < m; k

(mod

)

;

and 0

b < n:

Since

for some integer

and since (

k;m

) = 1, we deduce that (

a;m

) = 1.

Similarly, (

b;n

) = 1. Hence, there are

;

;::: ;

(

)

and

;

;::: ;

(

)

such

that

(mod

)

and

(mod

)

Since there are

(

)

(

) choices of pairs (

i;j

) and

is uniquely determined by the above

congruences (i.e., because of the Chinese Remainder Theorem), we get

(

)

(

)

(

Now, x a pair (

i;j

) with

;

;::: ;

(

)

and

;

;::: ;

(

)

, and consider the

integer

;

;::: ;mn

(that exists by the Chinese Remainder Theorem) which satises

(mod

) and

(mod

). There exists an integer

such that

so that, since (

) = 1, we obtain (

k;m

) = 1. Also, (

k;n

) = 1. Hence, (

k;mn

) =

1. Therefore, since each pair (

i;j

) corresponds to a dierent

(

)

(

)

(

Combining the inequalities, we get

(

) =

(

)

(

Theorem 15.

Suppose

, where

;::: ;e

, and

are positive

integers and

;::: ;p

are distinct primes. Then

(

) =

(

) =

Proof.

The second equality is clear and the rst follows from Lemma 1 and Lemma

2 (using

(

) =

(

)

(

)).

Examples.

Use the theorem to show that

(100) = 40 and

(140) = 48.

A \sieve" proof of Theorem 15 can be given that doesn't make use of the lemmas.

Observe that a positive integer

is not relatively prime to

if and only if

is divisible by

some

with

;

;::: ;r

. For distinct

;::: ;j

;

;::: ;r

, the number of positive

multiples of

which are

(

). The inclusion-exclusion principle

implies that the number of positive integers

which are not divisible by

;::: ;p

:::p

The theorem follows.

Comments:

An open problem due to Carmichael is to determine whether or not

there is a positive integer

such that if

is a positive integer dierent from

then

(

)

(

). If such an

exists, it is known that if must be

1000

. Some result in

this direction can be obtained as follows. Observe that

0 (mod 2) since otherwise

(

) =

). Now,

0 (mod 4) since otherwise

(

) =

(

2). Now,

0 (mod 3)

since otherwise

(

) =

2); and

0 (mod 9) since otherwise

(

) =

3). This

approach can be extended (apparently indenitely as long as one is willing to consider

branching o into dierent cases).

Homework:

(1) Calculate

(180) and

(1323).

(2) Prove that if

is a positive integer as in the comment above, then

n >

. (Hint:

Eventually consider two cases depending on whether 13

or 13

(3) During the year 1985, a convenience store, which was open 7 days a week, sold at least

one book each day, and a total of 600 books over the entire year. Must there have been a

period of consecutive days when exactly 129 books were sold?

Polynomial Basics:

Irreducible polynomials. A non-zero polynomial

(

)

[

] with

(

)

1 is

irreducible

(over

or in

[

]) if

(

) =

(

)

(

) with

(

) and

(

) in

[

] implies either

(

)

1 or

(

)

1. A non-zero polynomial

(

)

[

] with

(

)

1 is

reducible

(

) is not irreducible. A non-constant polynomial

(

)

[

] is

irreducible over

(or in

[

]) if

(

) =

(

)

(

) with

(

) and

(

) in

[

] implies either

(

) or

(

)

is a constant. A non-constant polynomial

(

)

[

] is

reducible over

(

) is not

irreducible over

Examples.

The polynomial

+1 is irreducible over

and over

. The polynomial

+ 2 is reducible over

and irreducible over

Comment:

Suppose

(

)

[

] and the greatest common divisor of the coecients

(

) is 1. Then

(

) is irreducible over the integers if and only if

(

) is irreducible

over the rationals.

Unique factorization in

[

]. It exists.

Division algorithm for polynomials. Given

(

) and

(

) in

[

] with

(

)

there are unique polynomials

(

) and

(

) in

[

] such that

(

) =

(

)

(

) +

(

) and

either

(

)

0 or deg

(

)

deg

(

). In the case where

(

) is monic, the polynomials

(

) and

(

) will be in

[

Examples.

(

) =

+ 2

+ 1 and

(

) =

+ 2, then

(

) =

and

(

) = 1.

(

) =

+ 4 and

(

) = 2

+ 2, then

(

) = 12

+ 34 and

(

) = 94

+ 52.

The Euclidean Algorithm. Illustrate by computing gcd(

+1). Note that

this example is not meant to be typical; in general the coecients might not be integral.

If we want gcd(

(

)

(

)) to be monic, then division by a constant may be necessary after

performing the Euclidean algorithm.

Given

(

) and

(

) in

[

], not both

0, there exist polynomials

(

) and

(

)

[

] such that

(

)

(

) +

(

)

(

) = gcd(

(

)

(

))

The Euclidean algorithm can be used to compute such

(

) and

(

The Remainder Theorem. The remainder when a polynomial

(

) is divided by

(

). Observe that the division algorithm for polynomials implies that there is

a polynomial

(

)

[

] and a rational number

such that

(

) = (

)

(

) +

; the

remainder theorem follows by letting

. As a corollary, we note that (

)

(

) if

and only if

(

) = 0.

The Fundamental Theorem of Algebra. A non-zero polynomial

(

)

[

] of degree

has exactly

complex roots when counted to their multiplicity. In other words, if

(

) =

[

] is a non-zero polynomial with roots (counted to their multiplicity)

;

;::: ;

, then

(

) =

(

)(

)

(

)

Elementary Symmetric Functions. Expanding the above factorization of

(

) in

terms of its roots, we deduce that

(

) =

+ (

where

;

; :::;

(in general,

is the sum of the roots of

(

) taken

at a time). We deduce the formula

= (

for each

;

;::: ;n

. Any rational symmetric function of the

roots

;

;::: ;

can be written in terms of the

elementary

symmetric functions

Examples.

Discuss the values of

when

(

) =

+ 2 = (

1)(

2).

Also, given

;

are the roots of

(

) =

+ 2

+ 5, compute the value of

) + (1

Congruences Modulo Polynomials. Is

+ 2

2 divisible

+ 1? If not, what's the remainder? Discuss the answer(s).

Homework:

(1) Calculate gcd(

+ 3

+ 2

+ 1)

(2) Let

;

and

be the roots of

+ 1 = 0

Calculate

for

= 1

;

;::: ;

(3) Determine whether

+ 1 is a factor of

+ 2

+ 1 using

arithmetic modulo

+ 1

(4) Consider all lines which meet the graph on

= 2

+ 7

+ 3

5 in four distinct

points, say (

)

= 1

;

Show that (

)

4 is independent of the line

and nd its value.

Polynomials Modulo Integers, Part I:

Theorem 16.

Let

be an odd prime. The congruence

+ 1

0 (mod

)

has a

solution if and only if

1 (mod 4)

Proof:

First suppose

1 (mod 4). Then

= 4

+ 1 for some positive integer

Thus, (

2 is even. By Wilson's Theorem, we obtain

(

1)!

+ 1

(

! (mod

)

Thus, in this case,

+ 1

0 (mod

) has the solution

= ((

2)!.

Now, suppose

3 (mod 4). Then (

2 is odd. Assume there is an integer

such

that

+ 1

0 (mod

). Then

1 (mod

) implies (since (

2 is odd) that

(

)

(

1 (mod

)

This contradicts Fermat's Little Theorem. Hence, the theorem follows.

Corollary.

There exist innitely many primes

1 (mod 4)

Before proving the corollary, we establish

Theorem 17.

There exist innitely many primes.

Proof 1 (Euclid's).

Assume there are only nitely many primes, say

;::: ;p

. Then

the number

+ 1 is not divisible by any of the primes

;::: ;p

, contradicting the

Fundamental Theorem of Arithmetic.

Proof 2.

The Fermat numbers

= 2

+ 1 are odd numbers

1 satisfying

2 =

Hence, they are relatively prime, so there must exist innitely many primes.

Proof of Corollary.

Consider the numbers

+ 1 where

is an integer. By

Theorem 16, the only primes dividing any such number are 2 and primes

1 (mod 4).

Thus, it suces to show there exist innitely many primes dividing numbers of the form

+1. Assume otherwise. Let

;::: ;p

be the primes which divide numbers of the form

+ 1. Since (

)

+ 1 is not divisible by any of the primes

;::: ;p

, we obtain a

contradiction.

Homework:

(1) Use an argument similar to Euclid's to prove there exist innitely many primes

(mod 4).

(2) Let

(

) be a non-constant polynomial in

[

]. Prove there exist innitely many

primes dividing numbers of the form

(

) where

(3) Let

be an odd prime, and let

be a positive integer. Let

= 2

1 = 2

(

)

(a) Prove that

does not divide

(b) Let

be a prime dividing

. Prove that

1 (mod

;

(

+ 2

(

+ 2

(

+ 2

+ 1

= 1.

(d) Observe that

1 = (

1)(

+ 1). Prove that there

is a prime dividing

which does not divide

(e) Prove there are innitely many primes

1 (mod

(4) Let

be an integer

3. Prove there exist innitely many primes

which are not

congruent to 1 modulo

Lagrange's Theorem:

Theorem 18.

Let

(

)

[

]

with

(

)

. Let

be a prime, and let

= deg

Then either the congruence

(

)

(

)

0 (mod

)

has at most

incongruent roots modulo

divides each coecient of

(

)

Proof.

The theorem is clearly true if

= 0. Let

be a positive integer, and

suppose the theorem holds for

n < m

. Consider

(

)

[

] with deg

. If (

)

has no solutions, then the desired conclusion follows for

(

). Suppose then that (

) has

a solution, say

. Hence, there is an integer

such that

(

) =

. This implies that

is a factor of

(

)

(by the Remainder Theorem). In other words, there is a

(

)

[

] such that

(

) = (

)

(

) +

. Clearly, deg

1. Observe that

(

)

(

)(

) (mod

). We deduce that

(

)

0 (mod

) if and only if

(

)

(mod

) or

(mod

). Since deg

1, we deduce that either there are at

most

1 incongruent integers

modulo

that can satisfy

(

)

0 (mod

) or every

coecient of

(

) is divisible by

. In either case, the theorem follows.

Comment:

Theorem 18 is not true if the prime

is replaced by a composite number

. For example,

0 (mod 8) has 4 incongruent solutions modulo 8. Also, 3

(mod 9) has 3 incongruent solutions modulo 9.

Corollary.

Let

(

)

[

]

be a monic polynomial of degree

, and let

be a prime.

Suppose

(

)

0 (mod

)

has

incongruent solutions modulo

, say

;::: ;a

. Then

(

)

(

)

(

) (mod

)

Proof.

Let

(

) =

(

)

(

)

(

). Since

(

) is monic, deg

Also,

(

)

0 (mod

) has the

incongruent solutions

;::: ;a

modulo

. Lagrange's

Theorem implies that

divides each coecient of

(

Wilson's theorem can be established with the aid of Theorem 18. Let

be a prime.

We want to prove (

1)!

1 (mod

). Let

(

) =

1. By Fermat's Little

Theorem and the above Corollary, we deduce

(

)

(

1)(

(

1)) (mod

)

Letting

= 0, we obtain the desired result.

Primitive Roots:

Denition. Let

be an integer, and let

be a positive integer with gcd(

a;n

) = 1.

The

order of

modulo

is the least positive integer

such that

1 (mod

Comment:

With

and

as above, the order of

modulo

exists since

(

)

(mod

). Furthermore, the order of

modulo

divides

(

). To see this, consider

integers

and

for which

(

)

= gcd(

(

)), where

is the order of

modulo

Then it follows easily that

gcd(

(

))

1 (mod

), and the denition of

implies that

= gcd(

(

)). This in turn implies

(

) as claimed.

Denition. If an integer

has order

(

) modulo a positive integer

, then we say

that

is a

primitive root

modulo

Comment:

Given a positive integer

, it is

not

necessarily the case that there exists

a primitive root modulo

. There exists a primitive root modulo

if and only if

is 2, 4,

, or 2

where

denotes an odd prime and

denotes a positive integer. The remainder

of this section deals with the case where

is a prime, and in this case we establish the

existence of a primitive root.

Theorem 19.

There is a primitive root modulo

for every prime

. Furthermore,

there are exactly

(

incongruent primitive roots modulo

Lemma.

Let

denote a positive integer. Then

(

) =

where the summation is over all positive divisors of

Proof of Lemma.

Write

where the

are distinct primes and

the

are positive integers. Note that

(

) =

1 +

(

) +

(

)

Since,

1 +

(

) +

(

) = 1 + (

1)(1 +

) =

;

we deduce that

(

) =

Theorem 19 is an apparent consequence of the next more general theorem.

Theorem 20.

Let

be a prime, and let

be a positive divisor of

. Then the

number of incongruent integers of order

modulo

(

)

Proof of Theorem 20.

We rst show that

0 (mod

) has exactly

incongruent solutions modulo

. By Lagrange's Theorem, it suces to show that there is

at least

incongruent solutions. Assume there are

< d

incongruent solutions. Observe

that

1 = (

(

) for some

(

)

[

] for degree

. A number is a

root of

0 (mod

) if and only if it is a root of

0 (mod

) or

(

)

(mod

). By Lagrange's Theorem,

(

)

0 (mod

) has at most

incongruent

solutions modulo

. Hence,

0 (mod

) has

< d

) =

1 incongruent

solutions modulo

. This contradicts Fermat's Little Theorem. Hence,

0 (mod

)

must have exactly

incongruent solutions modulo

Next, suppose

has order

modulo

. We show that

is a root of

0 (mod

)

if and only if

. If

, then

for some integer

so that

(

)

0 (mod

)

Hence,

is a root of

0 (mod

). Now suppose we know

is a root of

(mod

) and we want to prove

. There are integers

and

such that

and

r < d

. Since

(

)

(mod

)

;

we deduce that

= 0 and, hence,

as desired.

We proceed to prove the theorem by induction. If

= 1, then the theorem is clear.

Suppose the theorem holds for

d < D

. Then using the above information (including the

Lemma), we have

0 (mod

)

;

a < p

has order

;

a < p

(

) +

has order

a < p

(

)

(

) +

has order

a < p

(

) +

has order

a < p

The theorem follows.

Comment:

is a primitive root modulo

, then the numbers 1

;g;g

;::: ;g

are

incongruent modulo

. It follows that the numbers 1

;g;g

;::: ;g

are congruent modulo

to the numbers 1

;

;::: ;p

1 in some order.

Corollary.

For all odd primes

, there are exactly

(

non-zero incongruent

squares modulo

Proof.

(mod

) for some integer

with

0 (mod

), then

(

1 (mod

). Hence, Lagrange's Theorem implies that there are

(

2 non-zero

incongruent squares modulo

. On the other hand, if

is a primitive root modulo

, then

the numbers 1

;::: ;g

form (

2 non-zero incongruent squares modulo

Example.

Illustrate the above by considering

= 7. Here, 3 is a primitive root,

and the non-zero squares are 1, 2, and 4.

Comment:

It is not known whether 2 is a primitive root modulo

for innitely

many primes

. On the other hand, it is known that at least one of 2, 3, and 5 is a primitive

root modulo

for innitely many primes

Homework:

(1) (a) Using an argument similar to that given for the proof of the lemma to Theorem

20, show that if

and

(

) =

(i.e.,

(

) is the sum of the positive

divisors of

), then

(

) =

(b) Let

(

) =

1 (i.e.,

(

) is the number of positive divisors of

). With

above and using a similar argument to the above, show that

(

) = (

+ 1)(

+ 1)

(

+ 1)

(2) Let

be a positive integer. Given the notation in (1)(b) above, prove

(

)

(

)

(3) Let

be a prime, let

be a primitive root modulo

, and let

be an integer. Prove

that

is a primitive root modulo

if and only if gcd(

k;p

1) = 1.

(4) (a) Prove that if

is a prime

1 (mod 3), then there are exactly (

3 non-zero

incongruent cubes modulo

(b) Prove that if

is a prime

1 (mod 3), then there are exactly

1 non-zero

incongruent cubes modulo

. (Hint: If

doesn't look like a cube, maybe

+2(

will.)

th powers modulo a prime. In other words, nd a

precise description similar to the above for the number of

th powers modulo a prime.

Euler's Criterion:

Theorem 21.

Let

be an odd prime, and let

be an integer not divisible by

. If

is a square modulo

, then

(

1 (mod

)

. If

is not a square modulo

, then

(

1 (mod

)

Proof:

In the rst line of the proof of the Corollary to Theorem 20, we saw that

non-zero squares modulo

are roots of

0 (mod

). This is the rst half of

Theorem 21. It remains to prove now that if

is not a square modulo

, then

is a root

(

+ 1

0 (mod

). Observe that every integer in

;

;::: ;p

satises

(

1)(

(

+ 1)

0 (mod

)

so that if

;

;::: ;p

, then

is a root of either

(

0 (mod

) or

(

+ 1

0 (mod

) (and not both). By Lagrange's Theorem,

(

(mod

) can have at most (

2 incongruent roots. By the rst part of the proof,

these roots are the non-zero squares modulo

. It follows that the remaining integers in

;

;::: ;p

must satisfy

(

+ 1

0 (mod

), completing the proof.

Example.

Determine if 3 is a square modulo 31. Use that 3

4 (mod 31) =

)

16 (mod 31) =

)

2 (mod 31) =

)

1 (mod 31). By Euler's criterion,

3 is not a square modulo 31.

Quadratic Residues:

Denition. Let

be a prime, and let

be an integer not divisible by

. If

is a

square modulo

, then

is said to be a

quadratic residue modulo

. Otherwise, we say

that

is a

quadratic nonresidue modulo

Denition. Let

be a prime, and let

be an integer. The Legendre symbol

dened by

1 if

is a quadratic residue mod

0 if

0 (mod

)

1 otherwise

Comment.

For

an odd prime and

an integer, Euler's criterion is equivalent to

(

(mod

Theorem 22.

Let

and

be integers, and let

be a prime. Then the following

hold.

(i) If

(mod

)

, then

(ii) If

0 (mod

)

, then

= 1

(iii)

(iv) If

is odd, then

= 0

Proof.

The denition of the Legendre symbol immediately implies (i) and (ii).

Euler's criterion implies (iii) (deal with

= 2 separately). Finally, (iv) follows from the

fact that if

is odd, then there are (

2 quadratic residues and (

2 quadratic

nonresidues in the sum (see the Corollary to Theorem 20).

Evaluating the Legendre symbol. One can evaluate the Legendre symbol directly

from the denition or with the aid of Euler's criterion. The latter done correctly is quite

ecient. Another method which works somewhat better (especially by hand) is to make

use of the following three theorems.

Theorem 23.

For

an odd prime,

1 (mod 4)

Theorem 24.

For

an odd prime,

1 (mod 8)

3 (mod 8)

Theorem 25.

and

are odd primes, then

1 (mod 4)

Comment.

In some sense, only Theorem 25 is needed here as it can be shown that

Theorem 23 and Theorem 24 follow as a consequence of Theorem 25.

Theorem 23 is an immediate consequence of previous material. Euler's criterion

implies

= (

(

1 if

1 (mod 4)

1 if

1 (mod 4)

Theorem 23 is also equivalent to Theorem 16.

Examples.

Show that

= 1 using the above results. Hence,

17 is a

quadratic residue modulo 79. Also, discuss whether

1 factors modulo 7 and

modulo 11. Describe the primes

for which

1 factors modulo

A further example. Here we show that there are no integers

and

satisfying the

Diophantine equation
(

)

+ 11

Assume integers

and

exist satisfying (

). By considering (

) modulo 4, we deduce that

1 (mod 4) (i.e., since 0 and 1 are the only squares modulo 4). Observe that (

) implies

+ 16 =

+ 27 = (

+ 3)(

+ 9)

Since

1 (mod 4), we deduce

+ 9

3 (mod 4). This implies that there is a

prime

3 (mod 4) dividing

+9 and, hence,

+16. This implies

(mod

). This contradicts Theorem 23. Hence, (

) has no integer solutions.

Homework:

(1) Calculate the Legendre symbols

and

103

(2) Let

denote a prime. Prove that there is a solution to

0 (mod

) if and

only if

= 3 or

1 (mod 3).

(3) Prove that for every prime

, there is an

;

;::: ;

such that both

and

+ 1

are squares modulo

(4) Prove that there are no integers

and

such that

+ 7.

(5) (a) For every odd prime

, prove either

= 1,

= 1, or

= 1.

(b) Prove that

+ 1 is reducible modulo

for every prime

(6) Prove that for every positive integer

, there is an integer

such that

is not a

square modulo

for every odd prime

. (Hint: Use a major theorem from earlier in

this course.)

(7) Note that 107 and (107

2 = 53 are primes.

(a) Calculate the Legendre symbol

107

(b) The value of 15

is either 1 or

1 modulo 107. Use Euler's criterion together

with part (a) to determine (with explanation) whether 15

1 (mod 107) or 15

(mod 107).

Gauss' Lemma and the Proof of Theorem 24:

Theorem 26.

Let

be an odd prime, and let

be an integer not divisible by

. Let

denote the number of integers in the set

a;::: ;

((

which have a

remainder

> p=

when divided by

. Then

= (

Comment:

Observe that Theorem 23 is a consequence of Theorem 26.

Before proving Theorem 26, we explain its connection to Theorem 24.

Proof of Theorem 24 assuming Theorem 26.

Here

= 2 and

;

;::: ;p

1 (mod 4), then the elements of

which have a remainder

> p=

2 when divided by

are ((

2) + 2

for

= 1

;

;::: ;

(

4. Hence,

= (

4 and we obtain

= (

(

1 if

1 (mod 8)

1 if

3 (mod 8)

3 (mod 4), then the elements of

which have a remainder

> p=

2 when divided by

are ((

2) + 2

1 for

= 1

;

;::: ;

(

+ 1)

4. Thus,

= (

+ 1)

4 and we obtain

= (

(

+1)

1 if

1 (mod 8)

1 if

3 (mod 8)

This completes the proof.

Proof of Theorem 26.

Let

;::: ;a

be the elements of

which have a remainder

> p=

2 when divided by

. Let

;::: ;b

be the remaining elements of

. Let

(for

) and

(for 1

) be dened by

(mod

)

;

< p; b

(mod

)

;

and 0

< p:

Let

: 1

[

: 1

We begin by showing that

;

;::: ;

(

. Note that

;

;::: ;

(

and that

= (

2. Hence, it suces to show the

elments dening

are distinct. If

and

are in

;

;::: ;

(

and

(mod

), then

(mod

). It follows that the

values of

are distinct and the

values of

are

distinct. Assume

;

;::: ;n

and

;

;::: ;m

are such that

. Then

there are

and

;

;::: ;

(

such that

(mod

). This implies

(

)

0 (mod

) which contradicts that

and 2

1. We deduce that

;

;::: ;

(

From

;

;::: ;

(

, we obtain

(

)

(

)

(

)(3

)

(

! (mod

)

Therefore, by Euler's criterion,

(

(mod

)

;

and Theorem 26 follows.

The Quadratic Reciprocity Law:

Lemma.

is an odd prime and

is an odd integer with

not dividing

, then

= (

(

[

ka=p

]

where

[]

denotes the greatest integer function.

Proof. We use the notation given in the proof of Theorem 26. For each

;

;::: ;

(

, we have

with 1

;

where if

> p=

2 then

is some

and if

< p=

2 then

is some

. Observe that

= [

ka=p

]. Thus,

(

)

(

Recall that

: 1

[

: 1

;

;::: ;

(

Hence,

(

) +

Combining this with (

) gives

(

+ 1)

(

+ 2

Since

and

are odd, we obtain

(

(mod 2). The result now follows from

Theorem 26.

Proof of Theorem 25. If

, then the result is clear. So suppose

. It suces

to prove in this case that

= (

Consider the rectangle

in the

-plane with vertices (0

;

0), (

;

0), (

;q=

2), and

;q=

2). The number of lattice points strictly inside

2 . We now count

these points in a dierent way. Let

denote the diagonal joining (0

;

0) to (

;q=

2). Thus,

is a segment of the line

. If (

) is a lattice point on this line, then

Therefore, (

) is not strictly inside

. It follows that the number of lattice points

strictly inside

is the number of such points below

plus the number of such points

above

. The number of such lattice points below

(

, and the number of

such lattice points above

(

. We deduce that

(

The lemma now implies

= (

(

= (

;

completing the proof.

Homework:

(1) Let

(

) denote the number of incongruent solutions to

1 (mod 2

). Observe

that

(1) = 1,

(2) = 2, and

(3) = 4. Prove that

(

) = 4 for all

3. (Indicate

clearly where you use that

3.)

Sums of Two Squares:

Theorem 27.

A positive integer

is a sum of two squares if and only if every

prime

3 (mod 4)

satises

for some even number

Proof.

First, we show that if

is a sum of two squares and

for some non-

negative integer

, then either

= 2 or

1 (mod 4). Write

for some integer

not divisible by

. Let

and

be such that

. Let

be the non-negative

integer satisfying

, and write

so that

and

. If

+ 1, then

(

)

(

)

This is impossible since

does not divide

(

)

and

)

Thus,

and

(

). In other words,

where

is an integer not divisible

. From

and

, we deduce (

)

+ (

)

0 (mod

). Hence,

(

)

1 (mod

). By Theorem 23, we conclude as desired that either

= 2 or

1 (mod 4).

Now, suppose that every prime

3 (mod 4) satises

for some even number

Observe that 2 = 1

+ 1

(i.e., 2 is a sum of two squares). We want to show that

is a

sum of two squares. It suces to show (i) if

and

are both sums of two squares, then so

, (ii) if

3 (mod 4), then

is the sum of two squares, and (iii) if

1 (mod 4),

then

is the sum of two squares. To prove (i), let

, and

be integers such that

and

= (

)

+ (

)

. Then

= (

i)(

i) and

= (

i)(

i) so

that

= (

i)(

= ((

) + (

)i)((

)

(

)i) = (

)

+ (

)

To prove (ii), simply observe that

= 0

is the sum of two squares. We now turn to

establishing (iii). Since

1 (mod 4), there is an integer

such that

1 (mod

Let

= [

]+1 so that

p < m <

+1. In particular,

> p

which implies

+1.

Let

. Since

= 2

1 and 2

(

2) =

we can nd

2 sets

;::: ;S

satisfying

[

(

;

(

;::: ;

;

;::: ;p

with each

consisting of

consecutive integers and with every two

and

with

i < j

1 being disjoint. Observe that for every integer

there is a unique

;

;::: ;m

such

is congruent modulo

to some element of

. Consider the

numbers

where 0

1. By the pigeonhole principal, some two of these, say

and

, are congruent modulo

to elements in the same

. Fix such

, and

. If

= 1 and

= 0, then reassign the value of

so that

= 0. It follows that (

)

congruent modulo

to some element in

. Let

so that

;

;::: ;m

and

is congruent modulo

to some element in

. Let

(mod

) with

and set

. Then

(

+ 1)

0 (mod

)

Also,

(

+ (

(

)

+ (

)

= 2

Since

1, we obtain

;

). Since

is divisible by

, we deduce

. This completes the argument for (iii) and completes the proof of the theorem.

Polynomial Congruences Modulo Composite Numbers:

Reduction to prime powers. We have dealt with solving quadratic polynomials

modulo primes; we deal now with the general congruence

(

)

0 (mod

) where

(

)

[

] and

with the

denoting distinct primes and the

denoting positive

integers. Given an integer

, it is easy to see that

(

)

0 (mod

) if and only if

(

)

0 (mod

) for every

;

;::: ;r

. In other words, solving the congruence

(

)

0 (mod

) is the same as solving the system of congruences

(

)

0 (mod

)

with

;

;::: ;r

. We discuss an approach to solving

(

)

0 (mod

). Once this

congruence can be solved, we can piece together the solution with dierent prime powers

by using the Chinese Remainder Theorem. The third example below illustrates how this

is done.

Solving congruences modulo prime powers. Let

(

)

[

], and let

be a prime. To

nd the roots of

(

) modulo a power of

, we rst nd the solutions to

(

)

0 (mod

)

and inductively increase the exponent of

in the modulus. For this purpose, suppose

that

is an integer

2, we know the solutions to the congruence

(

)

0 (mod

and we want to know the solutions to

(

)

0 (mod

). We begin with an integer

satisfying

(

)

0 (mod

) and determine the integers

(mod

) for which

(

)

0 (mod

). All integers

satisfying

(

)

0 (mod

) can be obtained this way

as such

also satisfy

(

)

0 (mod

). Since

(mod

), there is an integer

such that

. We may further suppose that

;

;::: ;p

since

(

)

0 (mod

) holds if and only if

(

)

0 (mod

) holds for every integer

From Calculus, we can write

(

) =

(

) +

(

)

(

)

2! (

)

Observe that there are a nite number of terms on the right-hand side above and that

(

)

(

)

[

] for every positive integer

. Note that

2 implies 2(

. Hence,

(

)

(

)

(

) +

(

)

(mod

)

(

)

0 (mod

) and

(

)

0 (mod

), then (

) is true for all integers

. If

(

)

0 (mod

) and

(

)

0 (mod

), then (

) is not true regardless of

. If

(

)

0 (mod

), then

(

) has an inverse modulo

. Also,

(

)

0 (mod

) so

(

). In this case, (

) has the unique solution

;

;::: ;p

given by

(

)

(

)

(

)

(mod

)

Summarizing, we have that for a given solution

(

)

0 (mod

), one of the

following occurs:

(i)

(

)

0 (mod

) and

(

)

0 (mod

) and there are

incongruent solutions

modulo

(

)

0 (mod

) with

(mod

) and they are given by

where

;

;::: ;p

(ii)

(

)

0 (mod

) and

(

)

0 (mod

) and there do not exist solutions

(

)

0 (mod

) with

(mod

), or

(iii)

(

)

0 (mod

) and there is exactly one solution

modulo

(

)

0 (mod

) with

(mod

) and it is given by

with

satisfying

(

Two examples. Let

(

) =

+ 1 and

= 3. Then

(1)

0 (mod 3). In fact,

every integer satisfying

(

)

0 (mod 3) is congruent to 1 modulo 3. Since

(

) = 2

+1,

we deduce that

(1)

0 (mod 3) and

(1)

0 (mod 3

). By (ii),

(

)

0 (mod 3

)

has no solutions and so neither does

(

)

0 (mod 3

) for each

Now, suppose

(

) =

+ 4

+ 4 and

= 3. Note that modulo 3,

(

) is the same

here as in the previous problem. Again, all solutions to

(

)

0 (mod 3) are 1 modulo 3.

Also,

(1)

0 (mod 3) and

(1)

0 (mod 3

). Thus, by (i), there are three incongruent

solutions to

(

)

0 (mod 3

) given by 1, 4, and 7. Observe that if

represents any one

of these three solutions, then

(

)

(1)

0 (mod 3). Also,

(1)

0 (mod 3

(4)

0 (mod 3

), and

(7)

0 (mod 3

). By (i) and (ii), there exist exactly

three incongruent solutions to

(

)

0 (mod 3

) given by 7, 16, and 25. Observe that

solving

(

)

0 (mod 3

) is actually easy since

(

) = (

+ 2)

. If

is the least integer

greater than or equal to

2, then

(

)

0 (mod 3

) if and only if

+ 2

0 (mod 3

It follows that

(

)

0 (mod 3

) has exactly 3

solutions given by 3

2 where

;

;::: ;

A third example. Here we calculate all incongruent solutions modulo 175 to

+ 2

0 (mod 175)

Since 175 = 5

7, we consider

(

)

0 (mod 25) and

(

)

0 (mod 7) where

(

) =

+ 2

6. Since

(

)

(

3)(

+ 2) (mod 5) and

1, the only

solutions of

(

)

0 (mod 5) are 3 modulo 5. Since

(3)

0 (mod 5) and

(3) = 45, we obtain from (iii) that the all solutions to

(

)

0 (mod 25) are congruent

to 3 + 5(

8 modulo 25. One checks directly that the incongruent solutions modulo

7 to

(

)

0 (mod 7) are 2, 4, and 6. It follows that there are exactly three incongruent

solutions modulo 175, say

, and

, satisfying

8 (mod 25)

;

8 (mod 25)

;

8 (mod 25)

2 (mod 7)

;

4 (mod 7)

;

6 (mod 7)

By the proof of the Chinese Remainder Theorem,

(

7) + 2

392 + 100

292

58 (mod 175)

;

(

7) + 4

+ 100

158 (mod 175)

;

and

(

7) + 6

+ 100

83 (mod 175)

Thus,

(

)

0 (mod 175) has exactly three incongruent solutions modulo 175 given by

58, 83, and 158.

Homework:

(1) Find all the incongruent solutions modulo 135 to

+ 5

+ 15

0 (mod 135).

Do this in the method described above showing your work as in the third example.

Tossing Coins Over The Phone:

Two people

and

agree over the phone to get together at either

's house or

's house, but each is too lazy to volunteer going over to the other's house. Since

thinking rather quickly, he says, \I'll toss a coin and you call heads or tails. If you are

right, I'll come over to your house. If you are wrong, you have to come over here." It so

happens that

is thinking even better, and she suggests the following fair way to toss a

coin over the phone.

Step 1:

forms a number

where

and

are distinct large primes congruent to

3 modulo 4. The primes are small enough that they can pass current primality tests and

large enough so that

cannot be factored using current factoring methods.

tells

what

the value of

is.

Step 2:

chooses

;

;::: ;n

, computes

(mod

) with

;

;::: ;n

and tells

what

is. (We suppose that gcd(

k;pq

) = 1; since

and

are large, this is very

likely. In any case, the coin toss is not perfect because of this assumption.)

Step 3:

tries to gure out what

is. She knows

(mod

) and

(mod

Note that

3 (mod 4) so that (

+ 1)

. The value of

modulo

can be

determined by computing

(

+1)

(mod

). To see this, observe that

(

+1)

(

+1)

(

(mod

)

Note that Lagrange's Theorem implies the incongruent solutions of

(mod

) are

precisely

modulo

. Hence,

(mod

). Also,

computes

(

+1)

(mod

)

so that

(mod

). Observe that the solutions modulo

(mod

) are

given by

(i)

(mod

) and

(mod

)

(ii)

(mod

) and

(mod

)

(iii)

(mod

) and

(mod

)

(iv)

(mod

) and

(mod

)

computes

;

;::: ;n

satisfying (i) and

;

;::: ;n

satisfying (iii).

Then the solution to (ii) is

(mod

) and the solution to (v) is

(mod

Note that

(mod

) as

is not divisible by

and

is not divisible by

Since

(mod

), we deduce that either

(mod

) or

(mod

) but

not both.

selects one of

, say

, and tells

that she is guessing that

is one of

and

Step 4:

checks if

is one of

and

. If it is, then

admits it (so he has to go

over to her place). If

is not one of

and

, then

tells

that she was incorrect. In

this event the conversation continues as

must convince

that he is not lying. To prove

that

is telling the truth,

tells

how

factors.

determines this as follows. Suppose

(in the case that

, the factorization of

is determined in a similar way) so

that

(mod

). From the denition of

and

, it follows that

is divisible

by exactly one of

and

. Hence,

can determine

by computing gcd(

n;w

(Observe that

does not know which of the two numbers

and

given to him is

, but either one can be used since gcd(

n;n

) is also either

.) This easily

enables

to factor

. Thus, in the event that

claims that

's guess of

for

is incorrect,

veries that

is incorrect by giving

the factorization of

Denitions and Notations for Analytic Estimates:

Let

and

be real-valued functions with domain containing an interval [

) for

some real number

. We say that

(

)

is big oh of

(

) and write

(

) =

(

)) if there

is a constant

C >

0 such that

(

)

(

) for all

suciently large. We say

(

)

is less

than less than

(

) and write

(

)

(

) if

(

) =

(

)), and we say

(

)

is greater

than greater than

(

) and write

(

)

(

) if

(

) =

(

)). We say

the asymptotic

order of

(

)

(

) and write

(

)

(

) (or

(

)

(

)) if

(

)

(

)

(

). We

say that

(

)

is little oh of

(

) and write

(

) =

(

)) if lim

(

)

(

) = 0. We say that

(

)

is aymptotic to

(

) and write

(

)

(

) if lim

(

)

(

) = 1. Analogous denitions

exist if the domain is in the set of positive integers.

Examples.

Discuss each of the following:

;

+ 1

log

1 + 1

)

Comment:

The expression

(

)) in an equation represents a function

(

) =

(

)). To clarify, the last equation in

(

)

does not assert that a function is

if and only if it is

(

) but rather there is a

function

(

) that satises

(

) =

and

(

) =

(

). Indeed, in the equation

above, the big oh expressions both represent the same function

(

) =

An estimate using integrals. Explain why

log

Homework:

(1) Let

and

. Find all possible implications between the

following. In each case, give a proof or a counterexample.

(a)

(

)

(

)

(b)

(

) =

(

) +

(1)

(c)

(

)

(

)

(d)

(

) =

(

) +

(

))

(2) (a) Prove that

1 + log

for all

(b) Prove that

log

= log

(1).

(3) (a) How many positive integers

210 are not divisible by each of the primes 2, 3, 5,

and 7? For example, 11 would be such an integer but 39 would not be.

(b) Let

(

) =

: each of 2

;

and 7 does not divide

. Prove that

(

)

for some constant

and determine the value of

(4) Let

be a real number. Suppose

: [

)

has the property that for every

there exists an

(

) such that

(

)

(

) for all

[

a;t

]. Suppose

: [

)

has the property that for every

, there exists an

(

)

0 such that

(

)

(

) for all

[

a;t

]. Finally, suppose that

(

)

(

). Prove that there is a constant

C >

0 such

that

(

)

(

) for all

(5) Let

and

be Riemann integrable functions. Suppose that

(

) =

(

)). Prove or disprove that

(

)

(

)

Sums and Products Involving Primes:

Lemma.

log

for all

x >

Proof.

The lemma follows from

1 + 1

+ 1

log

Comment:

Observe that the lemma gives another proof that there are innitely

many primes.

Theorem 28.

The series

prime

diverges. In fact,

log log

Proof.

For

x >

1, the lemma implies

log

log log

On the other hand,

log

+ 1

(

)

;

where

(

)

(

1) = 1

Hence,

log

log log

Comment:

The sum of the reciprocals of every prime ever written down is

Theorem 29.

log

Proof.

Observe that

log

since the sum consists of [

] terms each

log

. Therefore,

log

The result follows.

Theorem 30.

log

Proof.

The lemma implies the

part of the asymptotic relation. We begin in a

manner similar to the proof of the lemma. We use that

1 + 1

+ 1

where

is an arbitrary number

1 and where

k>y

)

k>y

)

log

= 1

log

k>y

)

log

= 1

log

k>y;p

)

log

)

= 1

log

By Theorem 29, there is a constant

c >

0 such that

log

Setting

and using the previous homework problem (2)(a), we deduce

that

1 + log

(log

)

log

)

log

1 + log

Taking

, we obtain (3

1 + 4

log

from which

log

follows. This

implies the

part of the asymptotic relation in the statement of the theorem.

Theorem 31.

= log log

(1)

Proof.

From the proof of Theorem 28,

log

(

)

where

(

)

By Theorem 30, there exist constants

0 and

0 (and we may in fact take

= 1)

such that

log

x <

< c

log

provided

is suciently large (but note that problem (3) in the previous homework implies

2 will do). Hence, for

suciently large, it follows that

log

loglog

(1)

We deduce then that

log

(

) = log log

(1)

Homework:

(1) (a) Prove that (log

)

(

) for every

" >

0 and every

k >

(b) Part (a) implies that log

to any power grows slower than

for every

" >

0. Find

a function which grows slower than

for every

" >

0 and also grows faster than log

any power. In other words, nd an explicit function

(

) such that

(

) =

(

) for every

" >

0 and (log

)

(

)) for every

k >

0. Justify your answer. (Hint: Try

(

) =

(

)

for some appropriate

(

).)

)

((log

)

) for every

" >

0 and every

k >

(d) Find with proof a function

such that

log

(

)) and

(

)

diverges.

(2) Let

denote the

th prime. It is known that

log

for some constant

Using this information and Theorem 31, prove that

= 1.

The Number of Prime Divisors of

Notation. The number of distinct prime divisors of

is denoted by

(

Denition. Let

and

. Then

(

) is said to have normal

order

(

) if for every

" >

0, the number of positive integers

satisfying

)

(

)

< f

(

)

(1 +

)

(

)

is asymptotic to

(i.e., for almost all positive integers

(

)

((1

)

(

)

;

(1+

)

(

))).

Theorem 32.

(

)

has normal order

log log

Lemma.

(

)

log log

Proof.

We examine each term on the right-hand side of the equation

(

)

log log

(

)

(

)

log log

(log log

)

For the third term, we easily obtain

(log log

)

(log log

)

((loglog

)

For the second term, we use that

(

) =

1 =

0 (mod

)

1 =

(

) =

(loglog

(1)) +

(

) =

log log

(

)

For the rst term, we take advantage of the estimate we just made to obtain

(

)

1 +

1 =

1 +

log log

(

)

We proceed by observing that

1 =

(

) =

(

)

Theorem 31 imlies that each of the sums

) and

) is log log

(1) so that

(log log

)

(loglog

) =

= (log log

)

(loglog

)

Also,

) =

(1) since

) converges (by comparison with

)). We

deduce that

(

)

(loglog

)

(

loglog

)

Combining the above information, we obtain

(

)

log log

(

(loglog

))

Proof of Theorem 32.

Assume

(

) does not have normal order loglog

. Then

there exist

" >

0 and

0 such that there are arbitrarily large values of

for which the

number of positive integers

satisfying

(

)

(

)

log log

> x

. If

< n

, then

log log

n >

log log(

) = log log

If, in addition,

satises (

), then

(

)

log log

(

)

log log

> "

log log

(1 +

)

We consider

satisfying (

) for

> x

positive integers

with

suciently large so

that

2 log log

x >

1 +

and

In particular,

loglog

(1 +

)

> "

2 log log

We deduce that there are

> x

(

positive integers

(

] for which

(

)

log log

> "

2 log log

Hence,

(

)

log log

2 log log

(loglog

)

Observe that we can nd

arbitrarily large satisfying this inequality. We obtain a contra-

diction to the lemma since it implies that there is a constant

C >

0 for which

(

)

log log

for all

suciently large.

Homework:

(1) Prove that for every

" >

0, there is a constant

(

)

0 such that the number of

positive integers

for which

)log log

n < !

(

)

(1 +

)log log

does not hold is

(

)

log log

for all

suciently large.

(2) Let

;

and suppose that

(

) has normal order log log

. Prove or disprove

that the average value of

(

) for

is asymptotic to log log

. More specically, prove

or disprove that

(

)

log log

(Comment: In the proof of the lemma in this section, we showed a result that is even

stronger than this in the case that

(

) =

(

).)

Chebyshev's Theorem:

Background. Let

(

) denote the number of primes

. Chebyshev's Theorem

asserts that for all

suciently large

log

(

)

log

He used his result to give the rst proof of Bertrand's Hypothesis that for every

there is a prime in the interval (

]. More specically, the above implies that there is

such that if

, then

)

(

)

log(2

)

log

Combining such an estimate with knowledge of a specic

and computations verifying

Bertrand's Hypothesis for

x < x

, a proof of Bertrand's Hypothesis follows. Similar work

by others has been obtained. In particular, Ramanujan gave an argument for Bertrand's

Hypothesis and noted that there are at least 5 primes in (

] for

5. Our next

theorem is a variation of Chebyshev's Theorem. The proof below is due to Erd}os.

Theorem 33.

is a suciently large positive integer, then

log

(

)

log

Proof.

Let

be a positive integer. We begin with the inequalities

The rst of these inequalities follows from noting that one can choose

objects from a

collection of 2

objects by rst randomly deciding whether each of the rst

objects is

to be included in the choice or not. The second inequality follows from

= (1 + 1)

From the above inequalities, we deduce that
(

)

log 2

log((2

)!)

2log(

< m

log 4

We use that if

is a prime and

!, then

= [

k=p

] + [

k=p

] +

. Therefore,

(

)

log((2

)!)

2log(

!) =

log

It is easy to verify that [2

]

;

for every real number

. Hence, (

) and (

)

imply

log 2

log(2

)

log

log(2

) =

)log(2

)

Thus, if

= 2

, then

(

)

log2

log

Also, if

= 2

+ 1, then

(

)

log(2

)

+ 1

log(2

+ 1)

log

This establishes the lower bound in the theorem (for all positive integers

For the upper bound, we use that if

m < p

, then [2

m=p

]

m=p

] = 1. Thus, (

)

and (

) imply

log 4

m<p

log

m<p

log

m<p

log

)

(

)

log

Hence,

)

(

)

(log 4)

log

We consider positive integers

and

satisfying 2

n <

and 2

Observe that

tends to innity with

. Taking

= 2

above, we deduce

)

(log 4) 2

log(2

)

(log 4) 2

log(2

)

for

s;s

+ 1

;::: ;r

Summing over

, we obtain

(

)

log 4

log(2

)

+ 2

(log 4)2

log(2

)

2(log4)

log 2 = 2(log 4)

+ 1

(

+ 1)log 2

2(log4)

+ 1

log

= 40log 4

+ 1

log

n <

+ 1

log

For

and, hence,

suciently large, we deduce

(

)

log

95 + log

log

n <

log

;

completing the proof.

The Prime Number Theorem and Its Generalizations:

The Prime Number Theorem asserts that

(

)

log

. Observe that this is

stronger than Chebyshev's theorem. In this section, we mention some theorems without

proving them. The rst two are variations of the Prime Number Theorem.

Theorem 34.

(

) =

log

Denition and Notation. We dene the logarithmic integral of

by Li(

) =

log

This varies slightly (by a constant) from historic denitions of the logarithmic integral, but

the results below will not be aected by this change.

Theorem 35.

For every

k >

, we have

(

) =

(

) +

log

where the

implied constant depends on

Theorem 35 implies Theorem 34 and more. Using integration by parts and the

estimate
(

)

log

explain why Theorem 35 implies

(

) =

log

+ 2

log

Dirichlet's Theorem asserts that if

and

are positive relatively prime integers,

then there are innitely many primes of the form

. Set

(

;

b;a

) =

(mod

)

Then a strong variation of Dirichlet's Theorem is the following.

Theorem 36.

and

are positive relatively prime integers and

k >

, then

(

;

b;a

) = 1

(

)

(

) +

log

where the implied constant depends only on

and

Homework:

(1) Prove (

(2) There is a constant

such that

(

)

(log

) +

log

. Determine with proof

the value of

(3) (a) Let

and

be positive real numbers. Prove that

= log(

) +

(b) Let

;:::

where

;:::

are integers satisfying 0

< m

Dene

(

) =

(so

(

) is the number of elements in

which are

Suppose that

converges. Prove that almost all integers are not in

. In other

words, show that

lim

(

)

= 0

x<p

log

. (Alternatively, one can use

Theorem 31, but Theorem 33 is simpler.)

(d) Let

;:::

where

;:::

are primes satisfying

< p

. Dene

(

) =

. Suppose that

converges. Is it necessarily true that

lim

(

)

(

) = 0

(i.e., that almost all primes are not in

Riemann-Stieltjes Integrals:

Denitions and Notations. Suppose

: [

a;b

]

. Let

;::: ;x

denote a

partition of [

a;b

] with

< x

. Let

(

) = max

Let

[

] for

;

;::: ;n

. Consider

(

;f;

) =

(

)(

)

(

;f;

) tends to a limit

(independent of the

) as

(

) tends to zero, then we

write

(

)

and say that the Riemann integral of

(

) on [

a;b

] exists and equals

. Let

: [

a;b

]

With the notations above, we set

(

;f;g;

) =

(

)

(

)

(

)

(

;f;g;

) tends to a limit

(independent of the

) as

(

) tends to zero, then

we write

(

)

(

) =

and say that the Riemann-Stieltjes integral of

(

) with respect to

(

) on [

a;b

] exists and

equals

Comments:

The properties of Riemann integrals and Riemann-Stieltjes integrals

are very similar. Note in fact that if

(

) =

, then the denitions coincide. If

(

) is

dierentiable on [

a;b

], then one can show

(

)

(

) =

(

)

(

)

dx:

We will mainly be interested in the case when

(

) is a step function.

Example:

t d

[

] =

[

]

We will make use of an integration by parts formula for Riemann-Stieltjes integrals.

For a proof of this and other properties of Riemann-Stieltjes integrals (dened somewhat

dierently), see the instructor's notes at:

http://www.math.sc.edu/~filaseta/courses/Math555/Math555.html

Lemma:

(

)

(

)

exists, then so does

(

)

(

)

and

(

)

(

) =

(

)

(

)

(

)

(

) =

(

)

(

)

(

)

(

)

(

)

(

)

Example:

We apply integration by parts to the integral in the previous example.

We obtain

t d

[

] = [

]

[1]

[

]

) =

[

]

)

t dt

[

]

) = log

)

Observe that

= 1

. It follows that

exists. Also,

= 1

Combining the above, we deduce

t d

[

] = log

) = log

)

From the previous example, we obtain

= log

)

where

= 1

= 0

5772157

::: :

More precisely, the analysis above gives

= log

(

)

where

(

) =

dt:

Recall that this last integral is

so that we can deduce

(

)

. Thus, for exam-

ple,

can be computed to within 10

by considering log

= 14

392726

:::

Comment:

The constant

is called Euler's constant. It is unknown whether or

not

is irrational.

Sums and Products of Primes Revisited:

We combine the lemma from the previous section with the Prime Number Theorem

to arrive at improvements to some earlier results.

Theorem 37:

There exist constants

, and

such that

(i)

= log log

log

(ii)

log

= log

log

, and

(iii)

log

Proof of parts (i) and (iii):

For (i), we use integration by parts and Chebyshev's

Theorem to obtain

t d

(

) =

(

)

(

)

log

t dt

(

)

where

(

) =

(

)

log

dt:

By a previous homework problem and Theorem 34,

(

)

log

t dt

It follows that

(

)

log

= lim

(

)

exists. Also, observe that

(

)

log

t dt

log

Hence,

(

) =

(

)

log

(

)

log

(

)

log

Since

log

t dt

= log log

log log 2

;

we obtain (i) with

(

)

log

log log 2

For (iii), we argue along the lines of the proofs of Theorem 28 and 31. Note that

log

(

)

;

where

(

) =

(

We deduce that lim

(

) exists. Also,

p>x

n>x

(

1) =

[

]

It follows that

(

) =

p>x

We deduce from (i) that

log

log log

log

log log

log

where

. We obtain

log

)

log

where

Comments:

The proof of (ii) is omitted (but note the related problem in the next

homework). The constants in Theorem 37 are

= 0

261497212847643

::: ;

33258

::: ;

and

= 0

561459

::: :

Also, the number

in the argument above can be shown to be Euler's constant. Ignoring

the big-oh term in (i), it is not hard to see that if one could print a million primes per

second, then it would take over 1000 years to print enough primes (assumed distinct) to

make the sum of their reciprocals exceed 4. A more rigorous estimate is possible (where

the error term is not ignored).

Homework:

For the problems below, you are to make use of Theorems 34, 35, and 36 as well as

Riemann-Stieltjes integrals.
(1) Prove that

log

= log

(1).

(2) Prove that

log

(3) Let

and

be positive integers with gcd(

a;b

) = 1

Prove that

(mod

)

(

) log log

(4) Let

denote the

prime. Prove that

log

(5) Prove that there are innitely many primes which begin and end with the digit 9.

More specically, show that there are innitely many primes which can be written in the
form

where

= 9 and

;

;::: ;

for each

Integers With Large Prime Factors:

Denitions. Let

(

) denote the number of positive integers

having a property

. Then we say that a positive proportion of the positive integers satises

if there is

a constant

C >

0 such that

(

)

> Cx

for all suciently large

. If there is a constant

0 for which

(

)

, then we say the proportion of positive integers satisfying

. If this proportion is 1, then we say that almost all positive integers satisfy

Examples.

Almost all positive integers are composite. It follows as a consequence

of our next result that the proportion of positive integers

having a prime factor

log 2.

Theorem 38.

The number of positive integers

having a prime factor

(log 2)

log

Proof.

The desired quantity is

n<p

1 =

x;n<p

1 =

n<p

x<p

(

x<p

(

)

x<p

(

))

Chebyshev's Theorem implies that the error terms (the big-oh terms) are both

(

log

Theorem 37 (i) implies

x<p

= log log

log log

log

= log2 +

log

The theorem follows.

The Sieve of Eratosthenes:

We begin by illustrating the approach with an easy consequence of Theorem 33. It

should be noted that some similarities exist with the argument below and the sieve proof

given for Theorem 15.

Theorem 39.

(

) =

(

)

Proof.

The number of positive integers

divisible by a product of primes

::: p

is [

(

::: p

)]. The inclusion-exclusion principal implies that the number

of positive integers

with each prime factor of

being greater than

[

]

1 +

(

)

(

)

(

)

The big-oh term is

(

)

. We take

= log

and use Theorem 37 (iii) to deduce

that

log log

Also, this choice of

gives 2

log 2

. We obtain that the number of positive integers

with each prime factor of

being greater than log

(

). This accounts for all

the primes

except those which are

log

. There are clearly

(

) such primes and

the result follows.

A closer look at the argument. We estimated

(

) using the inequality

(

)

(

z;x

)

where

(

z;x

) =

)

p > z

(so that

(

z;x

) denotes the number of positive integers

having each of its prime

divisors

> z

). We used that

(

z;x

) = [

]

This last identity can be justied as follows. For

a positive integer, dene

(

) = 1

1 +

Write

in the form

where

is a non-negative integer,

;::: ;q

are

distinct primes

m;e

;::: ;e

are positive integers, and every prime divisor of

> z

= 0, then clearly

(

) = 1. If

r >

0, then

(

) = 1

= (1

= 0

Thus, we deduce that

(

) =

1 if every prime divisor of

> z

0 otherwise

Hence,

(

z;x

) =

(

) =

1 +

= [

]

We will modify our choice for

(

) slightly for other applications. The basic approach we

used to estimate

(

z;x

) is called the sieve of Eratosthenes. We give two more examples.

Theorem 40.

The number of squarefree numbers

is asymptotic to

)

Proof.

We make use of the identity

(

)

= 6

One can obtain (

) from

1 + 1

+ 1

Denote by

(

z;x

) the number of

that are not divisible by

for every

. Let

(

z;x

) denote the number of such

that are not squarefree. In other words,

(

z;x

) =

)

p > z

and

(

z;x

) =

)

p > z;

such that

By the sieve of Eratosthenes,

(

z;x

) =

1 +

= [

]

(

)

Taking

= log

, we obtain

(

z;x

) =

log

Thus,

(

z;x

)

(with

= log

). Since the number of squarefree numbers

(

z;x

)

(

z;x

), it suces to show

(

z;x

) =

(

). We use that

(

z;x

)

p>z

1 =

p>z

1 =

p>z

The series

converges by comparison with

. Since

= log

and

p>z

is the tail end of a convergent series, we deduce that

p>z

(1). It follows that

(

z;x

) =

(

), completing the proof.

Comment:

Let

(

) =

. An argument similar to the above shows that for

every integer

k >

1, the number of

-free numbers

is asymptotic to

(

Theorem 41.

Let

be a set of positive integers with the property that for every odd

prime

, every suciently large multiple of

is in

. In other words,

is such that if

an odd prime, then there is a

(

)

for which

for every positive integer

(

)

Dene

(

)

as the number of elements of

that are

. Then

(

)

Comments.

It will follow from the proof that the existence of

(

) only needs

to hold for a set of primes

having the property that

) diverges. Theorem 41 is

connected to Fermat's Last Theorem. Explain this connection.

Proof.

Fix

" >

0. It suces to show that there is an

(

) such that if

(

then

(

)

The upper bound is obvious. For

z >

0, dene

(

) = max

(

) : 2

< p

. Then

for each prime

and each integer

, we have

. Let

and dene

(

) =

. Thus,

(

) = [

]

(

)

For each

z >

0 and each odd prime

, there are

(

) multiples of

in S. The

remaining elements of

are not multiples of any odd prime

. In other words, the

remaining elements of

have all their odd prime factors

> z

. Thus,

(

)

(

z;x

) where

(

z;x

) =

)

= 2 or

p > z

Now,

(

z;x

) =

1 +

= [

]

(

)

= 2

Taking

and using the lemma to Theorem 28, we deduce that

(

)

(

) +

(

z;x

)

+ 2

log

(1)

where the implied constant depends on

and

(but note that

only depends on

). For

suciently large, we obtain

(

)

1 so that

(

) = [

]

(

)

(

1) = (1

)

This completes the proof.

Homework:

(1) (a) Let

be a set of primes for which

) diverges. Explain why

log

diverges.

(b) Given the set

in (a), explain why lim

z;p

= 0.

(2) (a) For

z >

1, dene

(

) = 1

3 (mod 4)

1 +

3 (mod 4)

1 +

Prove that

(

) = 1 if

0 (mod

) has a solution and that

(

)

0 for all positive

integers

(b) Use a sieve argument to show that for almost all positive integers

+ 1

(mod

) does not have a solution. In other words, show that the number of

for

which

+ 1

0 (mod

) has a solution is

(

The Pure Brun Sieve:

The idea. The sieve of Eratosthenes was based on estimating

(

) where

(

)

is something like (depending on the application)

(

) = 1

1 +

One major goal of sieve methods is to take

as large as possible without causing the

error terms that arise to exceed what one expects the main term to be. In the sieve of

Eratosthenes, we took

= log

which caused the error term

not to be too large.

The choice of

(

) above has the property that

(

) =

1 if every prime divisor of

> z

0 otherwise

so that

)

p > z

(

). We x a positive integer

and dene a

new quantity

(

) = 1

1 +

We will show that
(

)

p > z

(

)

The advantage of using

(

) over

(

) can be seen as follows. Recall that in using

(

), we were led to considering sums of expressions of the form [

(

)] where

the

denoted primes satisfying

< p

. In that approach, we then

replaced this expression with

(

) +

(1). We can see immediately that this is

too wasteful if

(and, hence,

) is large. For example, if

= (log

)

and

(

) are

large, then

(log

)

is so large that [

(

)] = 0 and

[

(

)] is very close to the value of

(

). Our method used an error of

(1) when in fact the true error was much smaller. By limiting the number of primes one

considers as in the denition of

(

), one can better control the lost made by omitting

the greatest integer function. This in turn allows us to choose

larger than before. In

particular, in the application we describe shortly, we will take

(24 loglog

)

Comments:

A lower bound similar to the upper bound given in (

) can be ob-

tained by considering 2

+ 1 instead of 2

primes in the denition of

(

). Further sieve

methods, due independently to Brun and Selberg, allow one to take

even larger than

that mentioned above. Typically, one can

where

is a positive constant depending

on the application.

A property of

(

). We show that

(

) = 1 if every prime divisor of

> z

and that

(

)

0 for all

. Observe that (

) follows as a consequence. The rst part is

obvious for if every prime factor of

> z

, then all the sums in the denition of

(

) are

empty and only the term 1 is non-zero in this denition. Now, suppose

where the

are distinct primes

, each of

r;e

;::: ;e

are positive integers, and every

prime factor of

> z

. It follows that

(

)

(

) = 1

;

where we interpret

as 0 is

b > a

. To show that

(

)

0, consider three cases: (i)

, (ii) 2

k < r

, and (iii)

r >

. Case (i) is dealt with by using (1

= 0 to

show

(

) = 0. For Case (ii), use (1

= 0 to obtain

(

) =

+ 1

+ 2

+ 1

+ 2

+ 3

+ 4

For Case (iii), use (

) directly to show that

(

)

1 (by again grouping the binomial

coecients in pairs).

An estimate concerning twin primes. A twin prime is a prime

for which

2 or

+2 is also prime. Thus, 3, 5, 7, 11, 13, 17, 19, 29, and 31 are all twin primes. We denote

the number of twin primes

(

). We will show

Theorem 42.

(

)

log

(loglog

)

More generally, we denote by

(

) the number of primes

for which

is also prime. We prove our next theorem from which Theorem 42 follows.

Theorem 43.

Let

be a positive integer. Then

(

)

log

(log log

)

where the

implied constant depends on

Proof.

We dene

(

z;x

) =

(

) =

)

p > z

Observe that for

suciently large (eg.,

+ 2 so that

(

) +

), we have

(

)

(

z;x

) +

. We seek a good estimate for

(

z;x

). We use that

(

z;x

)

(

))

(

)

1 +

(

)

(

)

We x momentarily

so that if

, then

. For a given

, we consider two

possibilities,

and

. If

, then the number of

for which

(

) is [

x=p

which is within 1 of

x=p

. If

, then the number of

for which

(

) is within

2 of 2

x=p

. In general, if

;::: ;p

are distinct primes dividing

and

;::: ;p

are

distinct primes not dividing

, then the number of

for which

(

) is divisible

is within 2

of 2

(this can be seen by using the Chinese

Remainder Theorem and considering the number of such

in a complete system of residues

modulo

). It follows that

(

z;x

)

a;p

a;:::;p

;

where

1 + 2

(

)

+ 4

(

)

+ 2

(

)

(

)

1 + 2 + 2

2! +

+ 2

(

)

and

2k +1

2k +2

2log log

+ 2

;

where

is some appropriate constant. Using

! and choosing

= [6log log

], we obtain

log log

+ 2

< x

(log

)

for

suciently large. We also have

(

)

12 loglog

for

suciently large. We now choose

(24 loglog

)

and consider

suciently large

to deduce that

(

z;x

)

where

(log

)

. Observe that, for some constants

and

depending on

(log

)

(log log

)

Theorem 43 follows.

Brun's Theorem. Brun introduced his pure sieve and used it to establish

Theorem 44.

a twin prime

)

converges.

Proof.

We use Riemann-Stieltjes integrals to obtain

a twin prime

t d

(

) =

(

)

(

)

dt:

Clearly,

(

)

1. Also, Theorem 43 implies

(

)

(log log

)

(log

)

(log

)

so that

(

)

(log

)

Thus,

a twin prime

is a bounded innite series with positive terms. The theorem follows.

Homework:

(1) Let

denote the

th prime.

(a) Explain why the Prime Number Theorem implies that limsup

(

) =

(b) Use Theorem 43 to prove that for every positive integer

limsup

min

;::: ;p

(Note that this would follow from part (a) if \min" were replaced by \max"; the problem

is to gure out how to handle the \min" situation.)

Wyszukiwarka

Podobne podstrony:
Algebraic Number Theory (Math 784 instructors notes) (1997) WW
Computational Number Theory (math 788 instructors notes) (1986) WW
Elementary Number Theory Notes D Santos (2004) WW
Clark Elementary Number Theory
Elementary Number Theory And Primality Tests [unkn] WW
Chen Elementary & Analytic Number Theory (1981) [sharethefiles com]
12 ELEMENTY ANALITYKI GEOCHEMICZNEJ d same metody instrumentalneid 13444
Ooguri What string theory has taught us (notes)
Algebra and Number Theory A Baker (2003) WW
Analytic Number Theory D Newman (Springer, 1998) WW
Algebra and Number Theory A Baker
FLEXIBLE PREDICATES OF FORMAL NUMBER THEORY
Group Theory [jnl article] J Milne (1996) WW
Everest G ANALITIC NUMBER THEORY
Presenting Toxicology Results G Nohynek (1996) WW
US Army course Basic Math II (Decimal Fractions) QM0114 WW
501 Math Word Problems (LearningExpress, 2003) WW

więcej podobnych podstron