第1页 / 共766页
第2页 / 共766页
第3页 / 共766页
第4页 / 共766页
第5页 / 共766页
第6页 / 共766页
第7页 / 共766页
第8页 / 共766页
Elementary Number Theory and Its Applications(6th Ed).pdf
Cover
Preface
What Is Number Theory?
1. The Integers
1.1. Numbers and Sequences
1.2. Sums and Products
1.3. Mathematical Induction
1.4. The Fibonacci Numbers
1.5. Divisibility
2. Integer Representations and Operations
2.1. Representations of Integers
2.2. Computer Operations with Integers
2.3. Complexity of Integer Operations
3. Primes and Greatest Common Divisors
3.1. Prime Numbers
3.2. The Distribution of Primes
3.3. Greatest Common Divisors and their Properties
3.4. The Euclidean Algorithm
3.5. The Fundamental Theorem of Arithmetic
3.6. Factorization Methods and the Fermat Numbers
3.7. Linear Diophantine Equations
4. Congruences
4.1. Introduction to Congruences
4.2. Linear Congruences
4.3. The Chinese Remainder Theorem
4.4. Solving Polynomial Congruences
4.5. Systems of Linear Congruences
4.6. Factoring Using the Pollard Rho Method
5. Applications of Congruences
5.1. Divisibility Tests
5.2. The Perpetual Calendar
5.3. Round-Robin Tournaments
5.4. Hashing Functions
5.5. Check Digits
6. Some Special Congruences
6.1. Wilson’s Theorem and Fermat’s Little Theorem
6.2. Pseudoprimes
6.3. Euler’s Theorem
7. Multiplicative Functions
7.1. The Euler Phi-Function
7.2. The Sum and Number of Divisors
7.3. Perfect Numbers and Mersenne Primes
7.4. Möbius Inversion
7.5. Partitions
8. Cryptology
8.1. Character Ciphers
8.2. Block and Stream Ciphers
8.3. Exponentiation Ciphers
8.4. Public Key Cryptography
8.5. Knapsack Ciphers
8.6. Cryptographic Protocols and Applications
9. Primitive Roots
9.1. The Order of an Integer and Primitive Roots
9.2. Primitive Roots for Primes
9.3. The Existence of Primitive Roots
9.4. Discrete Logarithms and Index Arithmetic
9.5. Primality Tests Using Orders of Integers and Primitive Roots
9.6. Universal Exponents
10. Applications of Primitive Roots and the Order of an Integer
10.1. Pseudorandom Numbers
10.2. The ElGamal Cryptosystem
10.3. An Application to the Splicing of Telephone Cables
11. Quadratic Residues
11.1. Quadratic Residues and Nonresidues
11.2. The Law of Quadratic Reciprocity
11.3. The Jacobi Symbol
11.4. Euler Pseudoprimes
11.5. Zero-Knowledge Proofs
12. Decimal Fractions and Continued Fractions
12.1. Decimal Fractions
12.2. Finite Continued Fractions
12.3. Infinite Continued Fractions
12.4. Periodic Continued Fractions
12.5. Factoring Using Continued Fractions
13. Some Nonlinear Diophantine Equations
13.1. Pythagorean Triples
13.2. Fermat’s Last Theorem
13.3. Sums of Squares
13.4. Pell’s Equation
13.5. Congruent Numbers
14. The Gaussian Integers
14.1. Gaussian Integers and Gaussian Primes
14.2. Greatest Common Divisors and Unique Factorization
14.3. Gaussian Integers and Sums of Squares
Appendix A. Axioms for the Set of Integers
Appendix B. Binomial Coefficients
Appendix C. Using Maple and Mathematica for Number Theory
C.1. Using Maple for Number Theory
C.2. Using Mathematica for Number Theory
Appendix D. Number Theory Web Links
Appendix E. Tables
Answers to Odd-Numbered Exercises
Bibliography
Index of Biographies
Index
Photo Credits
List of Symbols
Deirdre Lynch
Kendra Bassi
Editor: William Hoffman
Editor: Caroline Celano
Editor-in-Chief·
Senior Acquisitions
Associate
Marketing Manager: Jeff Weidenaar
Marketing Assistant:
Senior Managing Editor: Karen Wernholm
Production
Project Manager: Paul C. Anagnostopoulos
Composition
Manufacturing Manager: Evelyn Beaton
Photo Research: Maureen Raymond
Senior Cover Designer:
Cover Design: Nancy Goulet, Studio;wink
Cover Image: Gray Numbers, 1958 (collage)© Jasper Johns (b. 1930) I Private
and Illustration: Windfall Software,
Project Manager: Beth Houston
Beth Paquin
using ZzTEX
Collection
I Licensed by VAGA, New York, N.Y.
Photo Credits: Grateful acknowledgment
biographical
photos, listed on page 7 52, which is hereby made part of this copyright
page.
is made to the copyright
holders of the
used by manufacturers
Many of the designations
are claimed as trademarks.
Wesley was aware of a trademark claim, the designations
caps or all caps.
Where those designations
and sellers
to distinguish
their products
appear in this book, and Addison
have been printed in initial
Library of Congress Cataloging-in-Publication
Data
Rosen, Kenneth H.
Elementary number theory and its applications
I Kenneth H. Rosen. - 6th ed.
p. cm.
references and index.
Includes bibliographical
ISBN-13: 978-0-321-50031-1
ISBN-10: 0-321-50031-8
(alk. paper)
1.Number theory-Textbooks.
QA241.R67 2011
512.7'2---dc22
I. Title.
(alk. paper)
2010002572
© 2011, 2005, 2000 by Kenneth H. Rosen. All rights reserved.
No part
may be reproduced,
Copyright
of this publication
in any form or by any means, electronic,
otherwise,
without the prior written permission
of the publisher.
States of America. For information on obtaining
permission
work, please submit a written request to Pearson Education,
Department,
(617) 848-7047, or e-mail at http://www.pearsoned
mechanical,
500 Boylston Street, Suite 900, Boston, MA 02116, fax your request to
.com/legal/permissions.htm.
stored in a retrieval system, or transmitted,
photocopying,
recording,
or
Printed in the United
in this
for use of material
Inc., Rights and Contracts
1 2 3 4 5 6 7 8 9
10-C\V-14 13 12 11 10
Addison-Wesley
is an imprint of
PEARSON
-------
www.pearsonhighered.com
ISBN 13: 978-0-321-50031-1
ISBN 10: 0-321-50031-8
Preface
I wanted to create an effective tool for teaching and learning.
My goal in writing this text has been to write an accessible
number theory. Foremost,
I hoped to capture the richness and beauty of the subject and its unexpected
Number theory is both classical
In this text, I have strived to capture these contrasting
worked hard to integrate
these aspects into one cohesive text.
and inviting
and modem, and, at the same time, both pure and applied.
aspects of number theory. I have
introduction
to
usefulness.
This book is ideal for an undergraduate
No formal
beyond college algebra are needed for most of the material, other than
This book is also designed to be a source book
number theory course
at any level.
prerequisites
some level of mathematical maturity.
for elementary
courses and as a primer for those interested
cryptography.
Because it is comprehensive,
as a lifetime reference
for elementary
number theory; it can serve as a useful supplement
in new developments
and
it is designed to serve both as a textbook and
for computer science
in number theory
number theory and its wide-ranging
applications.
This edition celebrates
the silver anniversary
of this book. Over the past 25 years,
worldwide have studied number theory from previous editions.
students,
close to 100,000 students
Each successive
many instructors,
approach as all previous editions,
invite instructors
to carefully examine the sixth edition.
exercise
careful and rigorous
for computational engines
available
sets, the fascinating
on the Web.
edition of this book has benefited
from feedback and suggestions
from
and reviewers.
This new edition follows the same basic
and enhancements.
unfamiliar with this book, or who have not looked at a recent edition,
but with many improvements
I
I have confidence
that you will appreciate
notes, the up-to-date
the rich
coverage,
biographical
and historical
proofs, the many helpful examples,
the rich applications,
the support
such as Maple and Mathematica,
and the many resources
Changes in the Sixth Edition
The changes in the sixth edition have been designed to make the book easier to teach and
learn from, more interesting
changes were suggested by users and reviewers
highlights
some of the more important changes in this edition.
Many of these
The following list
of the fifth edition.
and as up-to-date
and inviting,
as possible.
ix
x
Preface
• New discoveries
This edition tracks recent discoveries
the new computational discoveries reflected
and the latest evidence supporting
proving the existence
recent theoretical
of both a numerical
long arithmetic
of arbitrarily
many open conjectures.
in this edition.
discoveries
described
progressions
and a theoretical
nature. Among
in the sixth edition are four Mersenne primes
The Tao-Green theorem
of primes is one of the
• Biographies
and historical
notes
of Terence Tao, Etienne Bezout, Norman MacLeod Ferrers, Clifford Cocks,
Biographies
and Waclaw Sierpinski
collection
book. Surprising information about secret British cryptographic
the work of Rivest, Shamir, and Adleman has been added.
the already extensive
supplement
of biographies
in the
discoveries
predating
• Conjectures
The treatment
particularly
open conjectures
are addressed.
of conjectures
throughout
elementary number theory has been expanded,
those about prime numbers and diophantine
equations.
Both resolved and
• Combinatorial
number theory
a fascinating
number theory. This new section introduces
A new section of the book covers partitions,
combinatorial
Ferrers diagrams, partition
section,
generating
identies,
including
functions and bijections.
and Ramanujan's
Euler's important
topic in
such important topics as
work on congruences.
results,
In this
are proved using both
partition identities,
and accessible
• Congruent numbers and elliptic
curves
are the area of a right triangle
integers
a brief introduction
A new section is devoted to the famous congruent
positive
contains
to finding rational
number problem to arithmetic progressions
points on certain elliptic
to elliptic
of three squares.
number problem, which asks which
with rational
side lengths.
This section
curves and relates
the congruent
number problem
curves. Also, this section relates
the congruent
• Geometric reasoning
This edition introduces
problems.
In particular,
is equivalent
given integer as area is equivalent
curve.
to finding Pythgaorean
the use of geometric reasoning in the study of diophantine
new material shows that finding rational
points on the unit circle
triples, and that finding rational
with a
triangles
points on an associated
elliptic
to finding rational
• Cryptography
This edition eliminates
used to encrypt a plaintext
modulus in the key.
the unnecessary
restriction
that when the RSA cryptosystem
message this message needs to be relatively
is
prime to the
• Greatest common divisors
Preface xi
Greatest common divisors
two integers
used in the book.
are now defined in the first chapter,
to be relatively prime.
The term Bezout coefficients
as is what it means for
is now introduced and
• Jacobi symbols
More motivation
expanded discussion
symbols is now provided.
is provided for the usefulness of Jacobi symbols. In particular, an
on the usefulness of the Jacobi symbol
in evaluating
Legendre
• Enhanced exercise
sets
Extensive
new exercises,
computational
work has been done to improve exercise sets even farther. Several hundred
ranging from routine to challenging,
and exploratory
exercises
can be found in this new edition.
have been added. Moreover, new
• Accurancy
More attention
Two independent
exercises.
than ever before has been paid to ensuring the accuracy of this edition.
accuracy checkers have examined the entire text and the answers to
• Web Site, www.pearsonhighered.com/rosen
The Web site for this edition has been considerably
will find many new resources
features are an expanded collection
to explore number theory, and a Web page devoted to number theory news.
they can use in conjunction
of applets,
with the book. Among the new
a manual for using comptutional
engines
expanded. Students and instructors
Exercise Sets
are so important,
Because exercises
has been devoted to the exercise
learn mathematics
types of exercises
a large percentage
work
of my writing and revision
sets. Students should keep in mind that the best way to
I will briefly describe the
is to work as many exercises
found in this book and where to find answers and solutions.
as possible.
• Standard Exercises
are included to develop basic skills,
Many routine exercises
both odd-numbered
number of intermediate-level
form new results.
new concepts.
exercises
Many other exercises
and even-numbered
exercises
with care taken so that
A large
help students put several concepts together to
and blocks of exercises
of this type are included.
are designed to develop
• Exercise Legend
Challenging
difficult exercise
exercises
are in ample supply and are marked with one star ( *) indicating
a
and two stars ( * *) indicating
an extremely
difficult
exercise.
There are
xii Preface
some exercises
symbol (> ). These exercises
used later in the text; these are marked with a arrow
whenever possible.
should be assigned by instructors
that contain results
• Exercise Answers
The answers to all odd-numbered
complete solutions
can be found on the Web site for this book. All solutions
and rechecked
to ensure accuracy.
to these exercises
exercises
can be found in the Student's
Solutions
Manual that
have been carefully checked
are provided at the end of the text. More
• Computational
Exercises
designed to be done with a com
PARIIGP, or Sage, or using programs
There are routine computational
exercises
students
computations
and/or students.
and explorations
program, such as Maple, Mathematica,
Each section includes
putational
written by instructors
can do to learn how to apply basic commands (as described
Mathematica
questions
programming
projects
or the computational
and Explorations
students
designed to be done by students
program of their choice. The Student's
and on the Web site for PARI/GP and Sage),
tools to attack these exercises.
designed for experimentation
use computational
and creativity.
in Appendix D for Maple and
as well as more open-ended
Each section also includes
a set of
using a programming
language
Manual to Computations
on the Web site provides answers, hints, and guidance that will help
Web Site
will find a comprehensive
Students and instructors
book's Web site. Students (as well as instructors)
www .pearsonhighered.com/rosen.
cessed at www.pearsonhighered.com/irc;
instructors
resources
from Pearson.
Resources
collection
on this
can find a wide range of resources
of resources
at
intended for only instructor
use can be ac
can obtain their password for these
• External
Unks
to number theory.
is discussed.
The Web site for this book contains
relevant
material
convenience,
in Appendix D.
These locations
a list of the most important
a guide providing
annotated
links to many Web sites
These sites are keyed to the page in the book where relevant
are marked in the book with the icon (J. For
Web sites related
to number theory is provided
• Number Theory News
The Web site also contains
a section highlighting
the latest discoveries
in number theory.
• Student's
Solutions
Manual
Worked-out solutions
can be found in the online Student's
to all the odd-numbered
Solution
Manual.
exercises
in the text and sample exams
• Student's
Manual for Computations
and Explorations
Preface xiii
resources
supporting
A manual providing
found on the Web site for this book. This manual provides worked-out solutions
solutions
guidance for attacking
comptutional
others. This manual will support, to varying degrees, different
to many of these computational
Maple, Mathematica,
and explorations
can be
the computations
and exploratory
exercises, as
environments,
and PARl/GP.
well as hints and
including
or partial
• Applets
of applets are provided on the Web site. These applets can be used
collection
An extensive
by students for some common computations
concepts and explore conjectures.
a collection
tion, decryption,
ciphers and the RSA cryptosystem.
ual, group, and classroom activities.
of cryptographic
cryptanalysis,
in number theory and to help understand
Besides algorithms
applets is also provided.
for comptutions
in number theory,
These include applets for encyrp
and cryptographic protocols, adderssing
both classical
These cryptographic
applets can be used for individ
• Suggested
Projects
A useful collection
These projects
projects
can serve as final projects
of suggested
can also be found on the Web site for this book.
for students
and for groups of students.
• Instructor's
Manual
to all exercises
Worked solutions
and a variety of other resources
is not available
planning which sections
to students).
to cover, and a test bank.
in the text, including
the even-numbered
execises,
can be found on the Web site for instructors
advice on
are sample syllabi,
Among these other resources
(which
How to Design a Course Using this Book
This book can serve as the text for elementary number theory courses with many different
slants and at many different levels.
flexibility
core material in Chapter 1 (as needed), Section 2.1 (as needed), Chapter 3, Sections
4.1-4.3,
instructors will have a great deal of
will want to cover the
their syllabi with this text. Most instructors
Chapter 6, Sections 7.1-7.3,
and Sections 9.1-9.2.
Consequently,
designing
To fill out their syllabi,
instructors
can add material
on topics of interest.
Generally,
topics can be broadly classified
inversion (Section
continued fractions (Chapter 12), diophantine
integers
(Chapter 14).
7.4), integer partitions (Section
as pure versus applied. P ure topics include Mobius
roots (Chapter 9),
7.5), primitive
equations
(Chapter 13), and Guassian
Some instructors
calendar,
the perpetual
computer applications
may also want to include Sections 9.3 and 9.4, Chapter 10, and Section 11.5.
will want to cover accessible
and check digits (Chapter 5). Those instructors
and cryptography
applications
should cover Chapter 2 and Chapter 8. They
such as divisibility tests,
who want to stress
xiv
Preface
After deciding which topics to cover, instructors
may wish to consult the following
figure displaying
the dependency of chapters:
1
/I�
2
3 12
I
/i�
6
13 14
5
I
7 � -----
8� /9 -----
10
11
Although Chapter
2 may be omitted if desired,
the text to describe the complexity
it does explain the big-0 notation
of algorithms.
Chapter 12 depends
used throughout
only on Chapter 1, as shown, except for Theorem 12.4, which depends on material
from Chapter 9. Section 13.4 is the only part of Chapter 13 that depends on Chapter
12.Chapter 11 can be studied without covering Chapter 9 if the optional comments
involving
in conjunction
primitive roots in Section 9.1 are omitted.
Section 14.3 should also be covered
with Section 13.3.
For further assistance,
instructors
can consult the suggested
syllabi for courses with
different emphases provided in the Instructor's
Resource Guide on the Web site.
strong support and enthusiam of Bill Hoffman, my editor at
editor,
the continued
of the new edition.
of the mathematics division
far longer than any of the many editors
Acknowledgments
I appreciate
Pearson and Addison-Wesley
him, and Greg Tobin, president
tude goes to Caroline Celano, associate
production
and media team behind this book, including
Maureen Raymond (Photo Researcher),
(Executive
(Designer)
(composition),
Windfall Software.
work on the first five editions
tors at Addison Wesley and my management at AT&T Bell Laboratories
incarnations).
Marketing Manager), Kendra Bassi (Marketing
at Pearson, and Paul Anagnostopoulos
(project
and proofreader),
(Media Producer),
Assistant),
I also want to reiterate
Beth Houston (Production
Rick Camp (copyeditor
of this book, including
for all her assistance
Carl Cottrell
and Laurel Muller (artist) at
my thanks to all those who supported my
of my previous
edi
the multitude
My appreciation
also goes to the production,
marketing,
who have preceded
of Pearson. My special grati
with development
and
Project Manager),
Jeff Weidenaar
and Beth Paquin
manager), Jacqui Scarlott
(and its various
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
