文档介绍：William Stein
Elementary Number Theory:
Primes, Congruences,
and Secrets
putational Approach
123
William Stein
Department of Mathematics
University of Washington
Seattle, WA 98195
USA
Editorial Board
S. Axler . Ribet
Mathematics Department Department of Mathematics
San Francisco State University University of California
San Francisco, CA 94132 at Berkeley
USA Berkeley, CA 94720
******@ USA
******@
ISSN: 0172-6056
ISBN: 978-0-387-85524-0 e-ISBN: 978-0-387-85525-7
DOI -0-387-85525-7
Library of Congress Control Number: 2008939895
Mathematics Subject Classification (2000): 11-xx:11Axx
c Springer Science+Business Media, LLC 2009
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,
NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use
in connection with any form of information storage and retrieval, electronic adaptation, computer
software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they
are not identified as such, is not to be taken as an expression of opinion as to whether or not they are
subject to proprietary rights.
Printed on acid-free paper
To my wife Clarita Lefthand
Contents
Preface ix
1 Prime Numbers 1
Prime Factorization . . . . . . . . . . . . . . . . . . . . . . 2
The Sequence of Prime Numbers . . . . . . . . . . . . . . . 10
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 The Ring of Integers Modulo n 21
Congruences Modulo n . . . . . . . . . . . . . . . . . . . . . 22
The Chinese Remainder Theorem . . . . . . . . . . . . . . . 29
puting Inverses and Huge Powers . . . . . . . . 31
Primality T