Number Theory Links
for Rosen’s Elem. Number Theory and Applications
1.1Numbers, Sequences, and Sums
Page 8
To learn more about figurate number consult
Page 9
You can use Neil Sloane's On-Line Encyclopedia of Integer Sequences Web site to determine the possible identity of an integer sequence from its first few terms. You can also check out some "hot sequences" and puzzle sequences that are quite challenging.
1.2 Numbers, Sequences, and Sums
Page 23
A picture of the 19th century original box cover for the Tower of Hanoi puzzle and the text of the original instructions in French, and translated into English, can be seen at the site of Paul K. Stockmeyer, a computer science professor at William and Mary College at
Several interesting papers about the Tower of Hanoi problem and its generalizations written by Paul K. Stockmeyer can be downloaded from
1.3 The Fibonacci Numbers
Page 25
A variety of ways that Fibonacci number arise in nature, including counting rabbits, can be found on Ron Knott's page at the Department of Computing, University of Surrey site:
1.4 Divisibility
Page 37
You can find the excellent expository article by Jeff Lagarias on the Collatz conjecture, which goes by many different names, including the "3x+1 problem" at
2.1 Representations of Integers
Page 47
Interesting information concerning Kaprekar's constant and related topics can be found at
3.1 Prime Numbers
Page 66
A wealth of information about primes can be found at the Prime Page
An excellent survey about prime numbers can be found at the St Andrews History of Mathematics Archive at
Page 67
Biographical information about Eratosthenes can be found at the MacTutor History of Mathematics Archive at
You can find an applets for running the sieve of Eratosthenes at
Information about the sieve of Eratosthenes and links for implementations in C, Java, and Perl can be found at
Page 75
A description of some of the open questions about primes can be found on the Prime Pages at
You can learn more about the twin prime conjecture and related conjectures at
Information about the current status of numerical evidence supporting Golbach's conjecture can be found at
3.2 Greatest Common Divisors
Page 80
An excellent starting place for learning about greatest common divisors is
Page 85
Information about Farey series and about Farey himself can be found at
Programs for computing Farey series can be found at
3.3 The Euclidean Algorithm
Page 92
You can find source code for a C program implementing the extended Euclidean algorithm at
3.5 Factorization Methods and the Fermat Numbers
A succinct report on modern factorization methods can be found as part of the RSA Labs FAQ at
Another good place to learn about different factorization methods is in Eric Weisstein's World of Mathematics at
Page 113
You can learn about the RSA Factoring Challenge at the following Web page at the RSA Data Security site:
Page 114
The currently known data about the factorization of Fermat numbers can be found on the following page created and maintained by Wilfrid Keller
Cash prizes are offered for finding prime factors of certain Fermat numbers. See
Page 115
Information about the Cunningham project, including the "most wanted" numbers awaiting
factorization can be found at
3.6 Linear Diophantine Equations
Page 120
An interactive applet for solving linear diophantine equations can be found at
4.1 Introduction to Congruences
Page 127
Modular arithmetic is discussed at the Cut-the-Knot site at
You can find source code for a C program implementing the algorithm for modular
exponentiation by repeated squaring and multiplying at
4.2 Linear Congruences
Page 139
You can find an approach for solving linear congruences at
Page 140
You can find source code for a C program that computes modular inverses at
4.3 The Chinese Remainder Theorem
Page 143
You can learn more about the Chinese remainder theorem at
You can calculate your biorhythms using the program at
4.5 Systems of Linear Congruences
Page 169
An excellent starting point for exploring Magic squares on the Web is
4.6 Factoring Using the Pollard Rho Method
Page 170
Source code for the Pollard rho factorization method can be found at
5.1 Divisibility Tests
Page 173
You can find a clear explanation, written by Robert L. Ward, why different divisibility tests
work for numbers in decimal notation at
Page 177
Information on repunits, including the repunits known to be prime, can be found at
5.2 The Perpetual Calendar
Page 179
A perpetual calendar implemented by Michael Bertrand in Java can be found at
5.3 Round-Robin Tournaments
Page 184
An interesting algorithm for scheduling double round-robin tournaments where each team plays each other twice so that each time plays at home, and so that a variety of constraints can be met, can be found at
5.4 Hashing Functions
Page 186
A definition of hashing functions can be found at
A discussion of hashing functions from a cryptographic standpoint is available as part of the
RSA Laboratories cryptography FAQ at
5.5 Check Digits
Page 191
A comprehensive discussion of various schemes used to construct check digits can be found at
Page 192
You can find a Java applet for computing the check digits for ISBNs at
Page 195
You can find a Java applet for computing check digits for UPCs at
7.3 Perfect Numbers and Mersenne Primes
Page 239
A survey article about perfect numbers can be found at the St. Andrews History of Mathematics site at
Page 241
A wealth of information about Mersenne primes can be found at
Page 244
The history of the search for Mersenne primes is described in detail at
Luke Welsh, one of the discoverers of the 29th Mersenne prime, has an excellent site containing a wealth of information about Marin Mersenne and the search for Mersenne primes at
Page 245
You can learn about the Great Internet Mersenne Prime Search, download software to look for
new Mersenne primes, and join the search itself at
You can learn about progress with the search for Mersenne primes over PrimeNet and obtain
software for joining PrimeNet which is associated with the Great Internet Prime Search at
Page 248
To learn more about amicable numbers you can consult
To access a list of all known amicable pairs go to
Information about multiply perfect numbers can be found at
8.1 Character Ciphers
Page 260
You can learn more about cryptography by checking out the Frequently Asked Questions
(FAQs) on cryptography at
RSA Laboratories has compiled their own highly informative set of Frequently Asked Questions
(FAQs) in cryptography which are accessible at
The basic terminology and concepts of cryptography is described on the page
An excellent introduction to cryptographic terminology and concepts can be found at
8.2 Block and Stream Ciphers
Page 268
The basic concept of a block cipher is described in detail at
Page 269
An excellent description of the Vigenere cipher can be found at
An on-line program for cryptanalysis of ciphertext encrypted using the Vigenere cipher is
available at:
Page 274
The complete specification of the DES is available from the National Institute of Standards and
Technology (NIST) at
You can learn more about the DES by consulting
Page 275
You can learn more about the AES by consulting
The concept of a stream cipher is described in detail at
8.3 Exponentiation Ciphers
You can find some information about exponentiation ciphers and many related topics in a special publication from NIST about public-key cryptography at
8.4 Public-Key Cryptography
Page 285
A description of public-key cryptography, private-key cryptography, and the advantages and
disadvantages of each can be found in the RSA Laboratories Cryptography FAQ at
Page 286
Information about the RSA Cryptosystem can be found at the RSA Laboratories Cryptography
FAQ at
You can find Ronald L. Rivest's home page which contains a photograph and links to many sites related to cryptography at
Adi Shamir's home page at the Weizmann Institute, currently containing only basic contact
information, can be accessed at
You can find Leonard Adleman's home page which contains a photograph, links to his papers,
and a commentary on his involvement in the movie Sneakers at
The RSA public key cryptosystem is implemented in C++ as part of the Crypto++ Library
which is accessible at
8.5 Knapsack Ciphers
Page 293
A discussion of knapsack ciphers (which are special cases of lattice-based cryptosystems) can
be found at
8.6 Cryptographic Protocols and Applications
Page 299
You can learn more about the Diffie-Hellman scheme for key agreement at
The Diffie-Hellman key agreement scheme is implemented in C++ as part of the Crypto++
Library which is accessible at
Page 300
The concept of a digital signature is explained at
Page 303
The basic concepts of secret sharing are described at
You can learn about some particular secret sharing schemes at
Shamir's secret sharing scheme implemented in C++ is available as part of the Crytpo++
Library which is accessible at
9.1 The Order of an Integer and Primitive Roots
Page 308
Source code for a C program that computes the order of an integer with respect to an integer
modulus can be found at
9.2 Primitive Roots for Primes
Page 317
Data concerning the least primitive root of primes not exceeding 8910000000000 have been
calculated by Tomás Oliveira e Silva and are accessible at
9.3 The Existence of Primitive Roots
Page 327
Source code for a program that finds a primitive root of an integer when one exists can be found at
9.4 Index Arithmetic
Page 332
A discussion of the discrete logarithm problem can be found as part of the RSA Labs FAQ at
9.5 Primality Tests Using Orders of Integers and Primitive Roots
You can download software that runs on PCs for running Proth's primality test, and check out
the latest discoveries made using this test at
Page 345
To find out more about Sierpinski numbers and the quest to show that 78,557 is the smallest
Sierpinski number, see
9.6 Universal Exponents
Information about minimal universal exponents, which are the same as the values of the
Carmichael function, can be found at Eric Weisstein's World of Mathematics at
10.1 Pseudorandom Numbers
A useful exposition about random number generators can be found in the RSA Laboratories
Cryptography FAQ at
A useful resource for the study of the generation of random numbers is the pLab Server on the
Theory and Practice of Random Number Generation at
10.2 The ElGamal Cryptosystem
Page 367
You can find the Federal Information Processing Standard (FIPS) 186 on the NIST Web site at
A C++ implementation of the ElGamal cryptosystem is included in the Crypto++ Library at
10.3 An Application to the Splicing of Telephone Cables
Page 371
To learn about splicing of coaxial cables, you may want to consult
11.2 The Law of Quadratic Reciprocity
Page 392
Close to 200 different proofs of the law of quadratic reciprocity are listed by Franz Lemmermeyer. He lists the author, year, and method of each proof, and provides references
and links to reviews in Mathematical Reviews and Zentralblatt. Go to
An excellent account of Eisenstein's simplification of Gauss's third proof of the law of quadratic reciprocity can be found in "Gauß, Eisenstein, and the "third" proof of the Quadratic Reciprocity Theorem: Ein kleines Schauspiel" by Reihard Laubenbacher - David J. Pengelley. This article originally appeared in the Mathematical Intelligencer in 1994 and can be accessed at
11.3 The Jacobi Symbol
Page 404
You can find source code for a C program that computes Jacobi symbols at
11.4 Euler Pseudoprimes
Page 413
Additional information about Euler pseudoprimes and related types of pseudoprimes can be found at
11.5 Zero-Knowledge Proofs
Page 421
You can learn more about zero-knowledge proofs and interactive proofs at
12.1 Decimal Fractions
Page 431
You can find programs that you can run online for converting fractions to decimals and decimals
to fractions at
Page 434
You can find an excellent exposition written by Helmut Richter concerning the period length of
decimal fractions at
12.2 Finite Continued Fractions
Page 443
You can learn more about continued fractions at the site
12.3 Infinite Continued Fractions
Page 458
The best rational approximations of real numbers are discussed at
12.4 Periodic Continued Fractions
Page 463
Continued fractions for square-roots are discussed at
12.5 Factoring Using Continued Fractions
Page 477
An implementation of factoring using continued fractions can be found at
13.2 Fermat's Last Theorem
Page 488
An excellent survey of the history of Fermat's last theorem can be found at
Information about Fermat's last theorem can be found at NOVA Web site on the pages
accompanying their episode devoted to Wiles's proof :
To begin exploring the mathematics behind Wiles's proof of Fermat's last theorem, you should look at a page developed by Charles Daney at
Page 491
You can learn more about the Wolfskehl prize by downloading the article by Barner from the
Notices of the American Mathematical Society at
or by reading an account of the award ceremony and the history of the prize written by Simon Singh the author of the best selling book Fermat's Last Theorem at (At last, Fermat can rest in peace)
13.3 Sums of Squares
Page 502
Information about Waring's problem can be found on the following pages:
13.4 Pell's Equation
Page 507
An interactive program for solving Pell's equation can be found at the site
Appendix A
Axioms for the Set of Integers
Page 515
You can learn more about the Peano axioms at
Appendix C
Using Maple and Mathematica for Number Theory
Page 527
The Maple home page is a good place to starting learning more about Maple:
Page 528
Maple worksheets written by John Cosgrave for a course in number theory and cryptography at
St. Patrick's College in Dublin, Ireland can be found at
You can find a Maple worksheet on the Collatz problem at
Page 530
Information on Mathematica can be found at
Mathematica packages can be accessed at
Page 531
A program for implementing the iterations in the Collatz 3x+1 problem in Mathematica can be found at
Page 532
You can find an implementation of the RSA Public-Key Cryptosystem in Mathematica at
Appendix E
TABLES
Page 537
You can find a table of the first 100,008 primes on the Prime Pages at