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