[PDF] [PDF] Lectures on Number Theory

[PDF] Number Theory II: Worksheet —Solutions - Illinois

Math 347, Summer 2019 Number Theory II: Worksheet —Solutions The following problems illustrate some of the main applications of congruences Some of 

[PDF] 3 Congruence

Quantitative Reasoning: Computers, Number Theory and Cryptography Some Examples Thus c = br is a solution of the congruence ax ≡ b mod n

[PDF] Lectures on Number Theory

We now turn to the problem of efficiently calculating the greatest common divisor of two Theorem 3 1 The equation ax + by = c has integer solutions if and only if (a, b) c that a is not congruent to b modulo m and write a ≡ b (mod m)

[PDF] Congruence problems and questions regarding sequences of

Distribution of solutions to congruences: large boxes The use of exponential sum techniques is one of the cornerstones of modern analytic number theory

[PDF] Number Theory Problem Sheet 2 SOLUTION Solving Linear

(2) Solving a set of linear congruences in integers (a) Show that solving one linear congruence a1x1 + ··· + amxm ≡ b (mod n) in integers x1, ,xm is equivalent 

[PDF] 250 PROBLEMS IN ELEMENTARY NUMBER THEORY

Theory" presents problems and their solutions everyone interested in number theory Prove that if for integer a and b the congruence ax+b == 0 (mod m)

Congruences

congruence classes, where we simplify number-theoretic problems by replacing the congruence f(x) == 0 mod (n) has no solutions x, then the equation f(x) = 0

[PDF] Modular Arithmetic Practice

13 sept 2015 · Practice Problem Solutions 1 Given that 5x Find the number of integers n, 1 ≤ n ≤ 25 such that n2 + 3n + 2 is divisible by 6 [Solution: 13]

[PDF] SOLUTIONS TO PROBLEM SET 1 Section 13 Exercise - UBC Math

We will apply the theorem from class that fully describes the solutions of linear congruences a) Solve 3x ≡ 2 (mod 7) Since (3,7) = 1 there is exactly one solution 

[PDF] number to letter decrypter

[PDF] numbered list apa format example

[PDF] number_of_reviews_ltm

[PDF] numeric attributes in data mining

[PDF] numerical analysis 1

[PDF] numerical analysis 1 pdf

[PDF] numerical analysis book for bsc

[PDF] numerical analysis book pdf by b.s. grewal

[PDF] numerical analysis book pdf by jain and iyengar

[PDF] numerical analysis books indian authors

[PDF] numerical analysis bsc 3rd year

[PDF] numerical analysis handwritten notes pdf

[PDF] numerical analysis pdf download

[PDF] numerical analysis pdf for computer science

[PDF] numerical analysis pdf s.s sastry

Lectures on Number

Theory

Lars-

Ake Lindahl

2002

Contents

1 Divisibility 1

2 Prime Numbers 7

3 The Linear Diophantine Equation ax+by=c 12

4 Congruences 15

5 Linear Congruences 19

6 The Chinese Remainder Theorem 21

7 Public-Key Cryptography 27

8 Pseudoprimes 29

9 Polynomial Congruences with Prime Moduli 31

10 Polynomial Congruences with Prime Power Moduli 35

11 The Congruence x

2a (mod m) 38

12 General Quadratic Congruences 43

13 The Legendre Symbol and Gauss' Lemma 44

14 Quadratic Reciprocity 47

15 Primitive Roots 48

16 Arithmetic Functions 55

17 Sums of Squares 58

18 Pythagorean Triples 61

19 Fermat's Last Theorem 63

20 Continued Fractions 64

21 Simple Continued Fractions 70

22 Rational Approximations to Irrational Numbers 73

23 Periodic Continued Fractions 79

24 Continued Fraction Expansion of

pd 86

25 Pell's Equation 88

Preface

The present lecture notes contain material for a 5 credit points course in Elemen- tary Number Theory. The formal prerequisites for the material are minimal; in particular no previous course in abstract algebra is required. High school mathematics, familiarity with proofs by mathematical induction and with the basic properties of limits of sequences of real numbers (in particular the fact that a bounded monotone sequence of real numbers is convergent) are all that is needed. (The discussion of the prime number counting function(x) in sec- tion 2 requires more calculus skills, but this part could be skipped without any loss of continuity.) A preliminary version of these notes has been carefully reviewed by Joakim Elgh, and I would like to thank him for some very useful suggestions and improvements.

Uppsala, 2002

Lars-

Ake Lindahl

1 DIVISIBILITY1

1 Divisibility

Denition 1.1An integerbisdivisibleby an integera, writtenajb, if there is an integerxsuch thatb=ax. We also say thatbis amultipleofa, and thata is adivisorofb. Any integerahas1 andaas divisors. These divisors are calledtrivial. The proof of the following simple properties are left to the reader.

Proposition 1.2Leta,bandcbe integers.

(i) Ifajbandb6= 0, thenjaj jbj. (ii) Ifajb, thenajbc. (iii) Ifajbandbjc, thenajc. (iv) Ifcjaandcjb, thencj(ax+by)for all integersxandy. (v) Ifajbandbja, thena=b. (vi) Assumec6= 0. Thenajbif and only ifacjbc. Denition 1.3Every nonzero integerahas nitely many divisors. Conse- quently, any two integersaandb, not both = 0, have nitely many common divisors. The greatest of these is called thegreatest common divisorand it is denoted by (a;b). In order not to have to avoid the special casea=b= 0, we alsodene(0;0) as the number 0. (One good reason for this choice will appear in Theorem 1.9.) By denition, if at least one of the numbersaandbis nonzero, then d= (a;b),dja^djb^(xja^xjb)xd): Obviously, (b;a) = (a;b) = (a;b) = (a;b) = (a;b), so when calculat- ing the greatest common divisor of two numbers we may replace them by their absolute values. Example1 The number 102 has the positive divisors 1, 2, 3, 6, 17, 34, 51, 102, and the number170 has the positive divisors 1, 2, 5, 10, 17, 34, 85, and 170. The common positive divisors are 1, 2, 17, and 34. Hence (102;170) = 34. To determine the greatest common divisor by nding all common divisors is

obviously not a feasible method if the given numbers are large.Proposition 1.4For all integersn,(a;b) = (anb;b).

Proof.Writer=anb; thena=r+nb. Assumingcjbwe now see from Proposition 1.2 (iv) thatcjaif and only ifcjr. Consequently, the pairsa, banda,rhave the same common divisors. In particular, they have the same greatest common divisor.We can extend the denition of greatest common divisor in a straightforward way. Givennintegersa1;a2;:::;annot all zero, we dene theirgreatest common divisor(a1;a2;:::;an) to be the greatest integer which divides all the given numbers. Finally, we dene (0;0;:::;0) = 0. If (a;b) = 1 we say thataandbarerelatively prime. More generally, the integersa1;a2;:::;anare called relatively prime if (a1;a2;:::;an) = 1, and they are calledpairwise relatively primeif any two of them are relatively prime.

1 DIVISIBILITY2

Example2 The numbers 4, 6, and 9 are relatively prime but not pairwise relatively prime.Theorem 1.5(The Division Algorithm)Given integersaandbwitha >0there exist two unique integersqandrsuch thatb=aq+rand0r < a. The numberqis called thequotientandris called the(principal) remainder.

Obviously,q= [b=a] (= the greatest integerb=a).

Proof.Consider the arithmetic progression

:::;b3a;b2a;ba;b;b+a;b+ 2a;b+ 3a;::: This sequence contains a smallest non-negative numberr. By denition,r= bqafor some integerq, and clearly 0r < a. This proves the existence. To prove uniqueness, suppose we also haveb=aq0+r0with 0r0< a. Then rr0=a(q0q) anda < rr0< a: Thusaj(rr0), and it follows thatrr0= 0 orjaj jrr0j. Since the latter case is excluded, we conclude thatrr0= 0, that isr=r0. Therefore

a(qq0) = 0, which impliesqq0= 0, i.e.q=q0.More generally, we say thatr0is a remainder whenbis divided byawhenever

there is an integerq0such thatb=aq0+r0without any further restriction onr0. Ifr0is an arbitrary remainder andris the principal remainder then obviously r

0r=nafor some integern, and conversely. For the principal remainderr

we either have 0ra=2 ora=2< r < a, and in the latter case the remainder r

0=rasatises the inequalitya=2< r0<0. Hence, there is always a uniqe

remainderrsatisfying the inequalitya=2< ra=2. This is theremainder of least absolute value.We thus have the following division algorithm, which for some purposes is more ecient than the ordinary one. Theorem 1.5'(Modied Division Algorithm)Given integersaandbwitha >0 there exist two unique integersqandrsuch thatb=aq+randa=2< ra=2. Example3 37 = 213+11 = 3132. 11 is the principal remainder and2 is the remainder of least absolute value.We now turn to an important class of subsets ofZ. Denition 1.6A non-empty setAof integers is called anidealif it is closed under subtraction and under multiplication by arbitrary integers, that is if it has the following two properties: (i)x,y2A)xy2A (ii)x2A,n2Z)nx2A. Example4 The setsf0g,Z, andf0;3;6;9;:::gare ideals. More gener- ally, given any integerg, the setA=fngjn2Zgconsisting of all multiples of gis an ideal. This ideal is said to begeneratedby the numberg, and it will be denoted bygZ. Thus, using this notation, 3Z=f0;3;6;9;:::g. Note that the trivial idealf0gis generated by 0 and that the whole setZis generated by 1.

1 DIVISIBILITY3

To show that a subsetAofZis an ideal it suces to verify that (i) holds, because we have the following result. Proposition 1.7A non-empty subsetAofZis an ideal ifx;y2A)xy2A. Proof.SupposeAis a non-empty subset with property (i) of Denition 1.6, and letx0be an element ofA. Since 0 =x0x0we rst note that 02A. Then we see thatx2A) x= 0x2Aand that x;y2A)x;y2A)x+y2A; i.e. the setAis closed under addition. Next assume that the implicationx2A)nx2Aholds for a certain nonnegative integern(this is certainly true forn= 0). Then we also have x2A)(n+ 1)x=nx+x2A. Hence, it follows by induction that the implicationx2A)nx2Aholds for each nonnegative integern. Finally, if x2Aandnis a negative integer, thennis positive, so it follows rst that (n)x2Aand then thatnx=(n)x2A. This shows that property (ii) of

Denition 1.6 holds forA.Remark.The ideal concept is aringconcept. A ring is a set with two operations,

addition and multiplication, satisfying certain natural axioms. The integersZform a ring, and another important example is given by the set of polynomials with ordinary polynomial addition and multiplication as operations. For ideals in general rings, property (ii) does not follow from property (i). Thus the ringZis special in that respect. The ideals that are listed in Example 4 are all generated by a single number g. We next show that all ideals ofZhave this property. Theorem 1.8Every idealAis generated by a unique nonnegative numberg, that isA=gZ=fngjn2Zg. IfAis not equal to the zero idealf0g, then the generatorgis the smallest positive integer belonging toA. Proof.The zero ideal is generated by 0, so assume thatAcontains some nonzero integerx0. Since by (ii),Aalso contains the numberx0(= (1)x0),Acer- tainly contains a positive integer. Letgbe the least positive integer belonging toA. We will prove thatAis generated by the numberg. Thatngbelongs toA for every integernfollows immediately from (ii), so we only have to prove that there are no other numbers inA. Therefore, letb2Aand dividebbyg. By the division algorithm, there exist integersqandrwith 0r < gsuch that bqg=r. Sinceqg2Ait follows from (i) thatr2A, and sincegis the least

positive integer inA, we conclude thatr= 0. Henceb=qgas claimed.We will now use Theorem 1.8 to characterize the greatest common divisor.

Letaandbbe two integers and consider the set

A=fax+byjx;y2Zg:

The setAis clearly closed under subtraction, i.e.Ais an ideal, and by the previous theorem,Ais generated by a unique nonnegative numberg. This number has the following two properties:

1 DIVISIBILITY4

(i) There exist integersx0,y0such thatax0+by0=g (ii) For all integersxandythere exists an integernsuch thatax+by=ng. Takingx= 1 andy= 0 in (ii) we see thata=ngfor some integernand hencegja. Similarly,gjb, sogis a common divisor ofaandb. Using (i), we see that every common divisor ofaandbis a divisor ofg. In particular, the greatest common divisord= (a;b) dividesgand hencedg. It follows thatg is the greatest common divisor, i.e.g= (a;b). This is also true in the trivial casea=b= 0, for theng= 0 and we have dened (0;0) to be the number 0. Our discussion is summarized in the following theorem. Theorem 1.9The idealfax+byjx;y2Zgis generated by the greatest common divisor(a;b), i.e. (i) There exist integersx0andy0such thatax0+by0= (a;b). (ii)ax+byis a multiple of(a;b)for all integersxandy. The proof of Theorem 1.9 is easily extended to cover the case ofnintegers a

1;a2;:::;aninstead of two integersaandb. The general result reads as follows.

Theorem 1.9'Leta1;a2;:::;anbe any integers. The ideal fa1x1+a2x2++anxnjx1;x2;:::;xn2Zg is generated by the greatest common divisord= (a1;a2;:::;an), i.e. (i) There exist integersy1;y2;:::;ynsuch thata1y1+a2y2++anyn=d. (ii)a1x1+a2x2++anxnis a multiple ofdfor all integersx1;x2;:::;xn. Corollary 1.10Ifcjaandcjb, thencj(a;b), i.e. every common divisor ofa andbis a divisor of the greatest common divisor(a;b). Proof.By Theorem 1.9 (i) we haveax0+by0= (a;b), and the conclusion of the

corollary now follows from Proposition 1.2 (iv).Corollary 1.11(i)(ca;cb) =c(a;b)for every nonnegative integerc.

(ii) Ifd= (a;b)6= 0, thenad ;bd = 1. Proof.(i) Writed= (a;b). By Theorem 1.9, the idealfax+byjx;y2Zg is generated byd. Nowcax+cby=c(ax+by), so it follows that the ideal fcax+cbyjx;y2Zgis generated bycd. But the latter ideal is according to Theorem 1.9 also generated by the number (ca;cb). Since the nonnegative generator is unique, we conclude that (ca;cb) =cd. (ii) By (i),dad ;bd = (a;b) =d. The result now follows upon division byd.Theorem 1.12If(a;b) = 1andajbc, thenajc. Proof.Assume (a;b) = 1 andajbc. Since clearlyajac, it follows thatais a common divisor ofacandbc. By Corollary 1.11, (ac;bc) =c(a;b) =c, and the conclusionajcnow follows from Corollary 1.10.Theorem 1.13Ifajc,bjcand(a;b) = 1, thenabjc.

1 DIVISIBILITY5

Proof.By assumption,c=amfor some integerm. Sincebjamand (b;a) = 1, we conclude from Theorem 1.12 thatbjm, that ism=bnfor some integern. Hence,c=abn, i.e.abjc.Theorem 1.14If(a;b) = (a;c) = 1, then(a;bc) = 1. Proof.By Theorem 1.9 there are integersx,yandz,wsuch thatax+by= 1 andaz+cw= 1. Thenbycw= (1ax)(1az) = 1an, wheren=x+zaxz is an integer. Hence,an+bcyw= 1, and we conclude from Theorem 1.9 that (a;bc) = 1.We now turn to the problem of eciently calculating the greatest common divisor of two integersaandb. We can of course assume that both are non- negative and thatab. Ifb= 0 then (a;b) = (a;0) =aand there is nothing more to do. Otherwise, we use Proposition 1.4 to see that (a;b) = (anb;b) for all integersn. In particular, using the ordinary division algoritma=qb+rwith 0r < bwe obtain (1) (a;b) = (aqb;b) = (r;b) = (b;r): Ifr= 0, then we are nished, because (a;b) = (b;0) =b. Otherwise, (1) allows us to replace the pair (a;b) with the smaller pair (b;r), wherer < b < a, and we can repeat the whole procedure. Since at each step we get a new pair with smaller integers, we must nally reach a stage where one of the numbers is 0.

The whole procedure may be summarized as follows.

The Euclidean Algorithm

Letaandbbe integers withab0. Puta0=aandb0=b.

(i) Ifb0= 0, then(a;b) =a0. (ii) Otherwise, using the division algorithm calculateqandrsuch thata0= qb

0+rwith0r < b0.

(iii) Puta0=b0andb0=rand go to (i). The algorithm must terminate, because the successiveb0:s form a decreasing sequence of non-negative integers. Instead of using the principal remainder, we could also use the remainder of least absolute value at each step. In general, this procedure will require fewer iterations. This modied algorithm runs as follows: The Euclidean Algorithm with least absolute remainder

Letaandbbe integers withab0. Puta0=aandb0=b.

(i) Ifb0= 0, then(a;b) =a0. (ii) Otherwise, using the division algorithm calculateqandrsuch thata0= qb

0+rwithjrj b0=2.

(iii) Puta0=b0andb0=jrjand go to (i). In (iii) we use the fact that (a0;b0) = (a0;b0) so it does not matter that we usejrjin order to get a nonnegative numberb0. Again, the algorithm must terminate because at each step the newb0is at most half of the old one.

1 DIVISIBILITY6

Example5 Let us calculate (247;91). The ordinary division algorithm gives

247 = 291 + 65

91 = 165 + 26

65 = 226 + 13

26 = 213:

Hence (247;91) = (91;65) = (65;26) = (26;13) = (13;0) = 13. By instead using least absolute remainders, we obtain the following sequence as a result of the division algorithm:

247 = 39126

91 = 326 + 13

26 = 213:

Hence (247;91) = (91;26) = (26;13) = (13;0) = 13.By Theorem 1.9, we know that the linear equation ax+by= (a;b) has at least one integer solutionx0andy0. (We will see later that there are in fact innitely many integer solutions.) As a by-product of the Euclidean Algorithm we have an algorithm for nding such a solution. Denoting the successive pairs (a0;b0) obtained during the process by (a0;b0), (a1;b1), (a2;b2), ..., (an;bn), withbn= 0, we have a

0=a; b0=b

a i=bi1; bi=ai1qibi1for suitable integersqi,i= 1, 2, ...,n a n= (a;b): It follows that each of the numbersaiandbiis a linear combination of the previous onesai1andbi1and hence ultimately a linear combination ofaquotesdbs_dbs20.pdfusesText_26