Scribd
Upload
78 views11 pages

Elements of Number Theory

Uploaded by

neetmonths
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
78 views11 pages

Elements of Number Theory

Uploaded by

neetmonths
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Undergraduate Texts in Mathematics

Editors
S. Axler
F. W. Gehring
K.A. Ribet

Springer Science+Business Media, LLC


Undergraduate Texts in Mathematics

Abbott: Understanding Analysis. Childs: A Concrete Introduction to


Anglin: Mathematics: A Concise History Higher Algebra. Second edition.
and Philosophy. Chung: Elementary Probability Theory
Readings in Mathematics. with Stochastic Processes. Third
Anglin/Larnbek: The Heritage of edition.
Thales. Cox/Little/O'Shea: Ideals, Varieties,
Readings in Mathematics. and Aigorithms. Second edition.
Apostol: Introduction to Analytic Croorn: Basic Concepts of Aigebraic
Number Theory. Second edition. Topology.
Arrnstrong: Basic Topology. Curtis: Linear Algebra: An Introductory
Arrnstrong: Groups and Symmetry. Approach. Fourth edition.
Axler: Linear Algebra Done Right. DevIin: The Joy of Sets: Fundamentals
Second edition. of Contemporary Set Theory.
Beardon: Limits: A New Approach to Second edition.
Real Analysis. Dixmier: General Topology.
BaklNewrnan: Complex Analysis. Driver: Why Math?
Second edition. Ebbinghaus/FlumlThomas:
Banchoff/Werrner: Linear Algebra Mathematical Logic. Second edition.
Through Geometry. Second edition. Edgar: Measure, Topology, and Fractal
Berberian: A First Course in Real Geometry.
Analysis. EIaydi: An Introduction to Difference
Bix: Conics and Cubics: A Equations. Second edition.
Concrete Introduction to Algebraic Erdös/Suninyi: Topics in the Theory of
Curves. Numbers.
Brernaud: An Introduction to Estep: Practical Analysis in One Variable.
Probabilistic Modeling. Exner: An Accompaniment to Higher
Bressoud: Factorization and Primality Mathernatics.
Testing. Exner: Inside Calculus.
Bressoud: Second Year Calculus. Fine/Rosenberger: The Fundamental
Readings in Mathematics. Theory of Algebra.
Brickrnan: Mathematicallntroduction Fischer: Intermediate Real Analysis.
to Linear Programming and Game Flanigan/Kazdan: Calculus Two: Linear
Theory. and Nonlinear Functions. Second
Browder: Mathematical Analysis: edition.
An Introduction. Fleming: Functions of Several Variables.
Buchmann: Introduction to Second edition.
Cryptography. Foulds: Combinatorial Optimization for
Buskes/van Rooij: Topological Spaces: Undergraduates.
From Distance to Neighborhood. Foulds: Optirnization Techniques: An
Callahan: The Geometry of Spacetime: Introduction.
An Introduction to Special and General FrankIin: Methods ofMathematical
Relavitity. Economics.
Carter/van Brunt: The Lebesgue- Frazier: An Introduction to Wavelets
Stieltjes Integral: A Practical Through Linear Algebra.
Introduction.
Cederberg: A Course in Modem
Geometries. Second edition. (continued after index)
Jobn StillweIl

Eleßlents of N ußlber
Theory

With 35 figures

Springer
John Sti1lwell
Mathematics Department
University of San Francisco
2130 FultoR Street
San Francisco. CA 94117~1080
USA
stillwel1@[Link]

EJilflriu[ B(jard

s. Axler F.W. Gchring K.A, Ribet


Mathematics DL"Partment Malhcmatics Dcpartmcnt Mathematics Departmcnt
San Francisco State Eallt Hali University ofCalifomia.
Univcrsity University of Michigan Berkeley
San Francisco, CA 94132 Ann Arbor, MI 48109 Berkeley, CA 94720·3840
USA USA USA
axlcr@.[Link] fgehrin~[Link] ribet@[Link]:[Link]

ISBN 978-1-4419-3066-8 ISBN 978-0-387-21735-2 (eBook)


DOI 10.1007/978-0-387-21735-2
Mathcmatics Subjcct ClassifiClllion (2000): il-III

or
library Congrcss Cataloging-in-!>ublication Data
Stil1wcl1, John.
E1crnents ofnumber tbeory f John Slillwel1.
p. cm. - (1lndeqvaduate tcxlţ in mathematics)
Includcs bibliuwaphical references ane! index.

QA241 .SRI) 2002


512'.7- Je21 2002030569

Prinled o:: acid-frec paper.

@ 2003 Springer Scîence+Business Media New York


Originally publîshed by Springer-Verlag New York. lnc in 2003
Softcover reprint of tbe hardcover Ist edition 2003
AII rights reserved. This work lllay not be trans1ated or copied in wbole or in part WItbout tbe written
pennission ofthe publisher (Springer Science+8usiness Media, LLC), except for brief excerpts in
connec:ion with reviews or scbolarly analysis. Use inconnectioo witb any form of information storage
and retrieval. electronic adaptation, computcrsoftware, or by similar or dissimilar methodology now
known or bereafter developed is [Link] use in this publication oftrade [Link]. trademarks.
service t: l arks, and similar tenns, even ifthey are not identified as sueh, is not to be taken as an
expression of oplllion as to whetber or not tbey are subject to proprielary [Link].

9 8 76 54 3 2 I

[Link]
ToElaine
Preface

This book is intended to complement my Elements oi Algebra, and it


is similarly motivated by the problem of solving polynomial equations.
However, it is independent of the algebra book, and probably easier. In
Elements oi Algebra we sought solution by radicals, and this led to the
concepts of fields and groups and their fusion in the celebrated theory of
Galois. In the present book we seek integer solutions, and this leads to the
concepts of rings and ideals which merge in the equally celebrated theory
of ideals due to Kummer and Dedekind.
Solving equations in integers is the central problem of number theory,
so this book is truly a number theory book, with most of the results found
in standard number theory courses. However, numbers are best understood
through their algebraic structure, and the necessary algebraic concepts-
rings and ideals-have no better motivation than number theory.
The first nontrivial examples of rings appear in the number theory
of Euler and Gauss. The concept of ideal-today as routine in ring the-
ory as the concept of normal subgroup is in group theory-also emerged
from number theory, and in quite heroic fashion. Faced with failure of
unique prime factorization in the arithmetic of certain generalized "inte-
gers" , Kummer created in the 1840s a new kind of number to overcome
the difficulty. He called them "ideal numbers" because he did not know
exactly what they were, though he knew how they behaved. Dedekind in
1871 found that these "ideal numbers" could be realized as sets of actual
numbers, and he called these sets ideals.
Dedekind found that ideals could be defined quite simply; so much so
that a student meeting the concept today might wonder what all the fuss
is about. It is only in their role as "ideal numbers", where they realize
Kummer's impossible dream, that ideals can be appreciated as a genuinely
brilliant idea.

vii
viii Preface

Thus solution in integers-like solution by radicals-is a superb set-


ting in which to show algebra at its best. It is the right place to introduce
rings and ideals and the right place first to apply them. It even gives an
opportunity to introduce some exotic rings, such as the quatemions, which
we use to prove Lagrange's theorem that every natural number is the sum
of four squares.
The book is based on two short courses (about 20 lectures each) given
at Monash University in recent years; one on elementary number theory
and one on ring theory with applications to algebraic number theory. Thus
the amount of material is suitable for a one-semester course, with some
variation possible through omission of the optional starred sections. A
slower-paced course could stop at the end of Chapter 9, at which point
most ofthe standard results have been covered, from Euclid's theorem that
there are infinitely many primes to quadratic reciprocity.
It should be stressed, however, that this is not meant to be a standard
number theory course. I have tried to avoid the ad hoc proofs that once
gave number theory a bad name, in favor of unifying ideas that work in
many situations. These inc1ude algebraic structures but also ideas from
elementary number theory, such as the Euc1idean algorithm and unique
prime factorization. In particular, I use the Euclidean algorithm as a bridge
to Conway's visual theory of quadratic forms, which offers a new approach
to the Pell equation.
There are exercises at the end of almost every section, so that each
new idea or proof receives immediate reinforcement. Some of them focus
on specific ideas, while others recapitulate the generalline of argument (in
easy steps) to prove a similar result. The purpose of each exercise should be
c1ear from the accompanying commentary, so instructors and independent
readers alike will be able to find an enjoyable path through the book.
My thanks go to the Monash students who took the courses on which
the book is based. Their reactions have helped improve the presentation in
many ways. I am particularly grateful to Ley Wilson, who showed that it
is possible to master the book by independent study.
Special thanks go to my wife Elaine, who proofread the first version
of the book, and to John Miller and Abe Shenitzer, who carefully read the
revised version and saved me from many mathematical and stylistic errors.

JOHN STILLWELL
South Melbourne, July 2002
Contents

Preface vii

1 Natural numbers and integers 1


1.1 Natural numbers . 2
1.2 Induction . . . . . . . . 3
1.3 Integers . . . . . . . . . 5
1.4 Division with remainder 7
1.5 Binary notation . . . . . 8
1.6 Diophantine equations 11
1.7 The Diophantus chord method 14
1.8 Gaussian integers 17
1.9 Discussion...... 20

2 The Euclidean algorithm 22


2.1 The gcd by subtraction . . . . . . . 22
2.2 The gcd by division with remainder 24
2.3 Linear representation of the gcd .. 26
2.4 Primes and factorization . . . . . . 28
2.5 Consequences of unique prime factorization 30
2.6 Linear Diophantine equations. . . 33
2.7 *The vector Euclidean algorithm 35
2.8 *The map of relatively prime pairs 38
2.9 Discussion. . . . . 40

3 Congruence arithmetic 43
3.1 Congruence mod n . . . . . . . . . . . 44
3.2 Congruence c1asses and their arithmetic 45
3.3 Inverses mod p . . . . . ..... 48

ix
x Contents

3.4 Fennat's litde theorem . . . . . . . . . . . . . 51


3.5 Congruence theorems of Wilson and Lagrange . 53
3.6 Inverses mod k . . . . . . .. . 55
3.7 Quadratic Diophantine equations 57
3.8 *Primitive roots . . . . . . . 59
3.9 *Existence of primitive roots 62
3.10 Discussion . . . . . 63

4 The RSA cryptosystem 66


4.1 Trapdoor functions 66
4.2 Ingredients of RSA 69
4.3 Exponentiation mod n . 70
4.4 RSA encryption and decryption . 72
4.5 Digital signatures . . . . . 73
4.6 Other computational issues 74
4.7 Discussion. . 74

5 The Pell equation 76


5.1 Side and diagonal numbers 77
5.2 The equation:xl - 2l = 1 78
5.3 The group of solutions .. 80
5.4 The general Pell equation and Z[vIn] 81
5.5 The pigeonhole argument . . . 84
5.6 *Quadratic fonns . . . . . . . . . 87
5.7 *The map of primitive vectors .. 90
5.8 *Periodicity in the map of:xl - nl 95
5.9 Discussion. . . . 99

6 The Gaussian integers 101


6.1 Z[i] and its norm . . . . . . . . . . 102
6.2 Divisibility and primes in Z[i] and Z 103
6.3 Conjugates . . . . . . . . . 105
6.4 Division in Z[i] . . . . . . . 107
6.5 Fennat's two square theorem 109
6.6 Pythagorean tripies . . . . 110
6.7 *Primes of the fonn 4n + 1 113
6.8 Discussion......... 115
Contents xi

7 Quadratic integers 117


7.1 The equation y3 = :;2- + 2 118
7.2 The division property in Z[Al 119
7.3 The gcd in Z[Al . . . . . . . 121
7.4 Z[Hl and Z[s3l . . . . . . . . 123
7.5 *Rational solutions of x 3 + y3 = z3 + w 3 126
7.6 *TheprimeHinZ[S3l . . . . 129
7.7 *Fermat's last theorem for n = 3 132
7.8 Discussion. . . . . . 136

8 The four square theorem 138


8.1 Real matrices and C . 139
8.2 Complex matrices and 1HI 141
8.3 The quaternion units 143
8.4 Z[i,j, kl . . ..... 145
8.5 The Hurwitz integers 147
8.6 Conjugates . . . . . 149
8.7 A prime divisor property 151
8.8 Proof of the fOUf square theorem 152
8.9 Discussion. . . . 154

9 Quadratic reciprocity 158


9.1 Primes :;2- + y2, :;2- + 2y2, and :;2- + 3 y2 159
9.2 Statement of quadratic reciprocity 161
9.3 Euler's criterion . . . . . . . . . 164
9.4 The value of (~) . . . . . . . . 167
9.5 The story so far . . . . . . . . . 169
9.6 The Chinese remainder theorem 171
9.7 The full Chinese remainder theorem 173
9.8 Proof of quadratic reciprocity . 175
9.9 Discussion . 178

10 Rings 181
10.1 The ring axioms . 182
10.2 Rings and fields . 184
10.3 Algebraic integers . 186
10.4 Quadratic fields and theirintegers 189
10.5 Norm and units of quadratic fields 192
10.6 Discussion. . . . . . . . . . . . . 194
xii Contents

11 Ideals 196
11.1 Ideals and the gcd . 197
11.2 Ideals and divisibility in Z 199
11.3 Principal ideal domains . . 202
11.4 A nonprincipal ideal of Z [Hl 205
11.5 A nonprincipal ideal of Z[Hl 207
11.6 Ideals of imaginary quadratic fields as lattices 209
11. 7 Products and prime ideals . 211
11.8 Ideal prime factorization 214
11.9 Discussion. 217

12 Prime ideals 221


12.1 Ideals and congruence. . . . . . . . . . . 222
12.2 Prime and maximal ideals. . . . . . . . . 224
12.3 Prime ideals of imaginary quadratic fields 225
12.4 Conjugate ideals. . . . . . . 227
12.5 Divisibility and containment 229
12.6 Factorization of ideals . . . . 230
12.7 Ideal classes . . . . . . . . . 231
12.8 Primes of the form :x2 + 5y2 . 233
12.9 Discussion. 236

Bibliography 239

Index 245

Common questions

Powered by AI

The Euclidean algorithm serves as a bridge to Conway's visual theory of quadratic forms, offering a novel approach to solving Pell's equation. By utilizing the algorithm, the solutions to quadratic equations become more tangible and tractable, enriching the conceptual understanding by aligning classical number theory methods with advanced visual frameworks . This integration underscores the algorithm's utility beyond simple gcd calculations, extending its reach into visual and geometric interpretations .

Kummer introduced 'ideal numbers' to address the failure of unique prime factorization in certain number arithmetics, which were inherently linked to specific algebraic structures. Dedekind then formalized these 'ideal numbers' into the concept of ideals, which act similarly to normal subgroups in group theory, allowing the extension of algebraic techniques to the realm of number theory . Their development laid foundational concepts used in modern algebraic number theory, merging ideas about rings and advanced algebraic structures .

Rings provide a framework to introduce and apply algebraic concepts effectively because they encompass structures such as Gaussian integers and allow exploration of Diophantine equations and their solutions. They serve as a context to showcase algebra's capability in deriving integer solutions and facilitating understanding of more exotic number systems like quaternions used in Lagrange's theorem proofs . This highlights algebra's versatility and applicability, which is effectively utilized in the book to cement foundational knowledge .

Gaussian integers expand traditional divisibility concepts by introducing a complex plane where integers combine real and imaginary units, facilitating explorations of primes in two dimensions. This leads to novel insights into factorization, divisibility, and primality that can't be achieved with real integers alone. They allow for new interpretations and extensions of classic theorems, such as Fermat's two-square theorem, adding depth to the integer concept by including solutions that incorporate complex numbers . This dual-dimensional approach unveils deeper algebraic truths within arithmetic .

Lagrange's Four Square Theorem states that every natural number can be expressed as the sum of four squares, a proof involving quaternions, an example of exotic rings. Quaternions allow for complex manipulations in spatial rotations and algebraic calculations, offering a more intuitive framework to prove the theorem by using quaternionic integers, thus demonstrating the power of these non-standard rings in addressing classic number theory problems . This utilization exemplifies the versatility and reach of algebraic structures in solving classical mathematical problems .

The RSA cryptosystem employs number theory concepts, particularly the difficulty of factoring large primes and the relationship between modular arithmetic and exponentiation, to establish secure encryption and decryption processes. It uses 'trapdoor functions' based on Fermat’s Little Theorem and congruence arithmetic, creating a system where public encryption keys can be shared, but private keys remain secure, hinging on the computational difficulty of reversing the process without key information . This illustrates number theory's impact on modern cryptography, ensuring data integrity and confidentiality .

Fermat's Little Theorem is foundational in number theory because it provides critical insight into congruences modulo primes, which is central to understanding congruence classes and arithmetic operations under moduli. It backs many important theories and methods, enabling significant simplifications and proofs regarding numbers and their reciprocals in modular arithmetic, as discussed in the RSA cryptosystem section for its role in cryptographic security . This theorem's applicability renders it a pivotal tool in both theoretical and practical fields of mathematics .

The book differentiates itself from standard number theory courses by emphasizing unifying algebraic concepts over ad hoc methods, integrating foundational principles such as the Euclidean algorithm with advanced structures like rings and ideals. It avoids traditional proofs in favor of broader conceptual frameworks, offering a unique perspective that highlights both standard results and their applications through algebraic lens. This structure provides depth and cohesion, facilitating a holistic understanding of number theory that transcends typical curricula .

The Chinese remainder theorem is significant because it provides a method to solve systems of modular congruences, facilitating computations in number theory. It showcases how congruences can be managed efficiently when segmented into simpler parts, leveraging the algorithm's properties to address broader mathematical challenges. The book uses it to illustrate foundational principles of modular arithmetic and their role in complex problem-solving, such as computing systems of Diophantine equations or simplifying proofs by breaking them into manageable components .

The book's pedagogical approach in using algebraic structures to tackle Diophantine equations offers students a multifaceted view of number theory by showing the practical applications of theoretical concepts. By bridging abstract algebra with tangible problem-solving in number theory, it allows students to appreciate the interconnectedness of mathematical disciplines. This approach fosters deep understanding and promotes the utility of structures like rings and ideals in unveiling solutions to equations typically restricted to integers, enriching the standard number theory curriculum .

You might also like