# Elementary Number Theory

Written by: William Stein (University of Washington)

The author of this text is William Stein of the University of Washington. He has assigned it to his students at Harvard University, UC San Diego and the University of Washington.

Per his own description, “This is a textbook about prime numbers, congruences, basic public-key cryptography, quadratic reciprocity, continued fractions, elliptic curves, and number theory algorithms. We will mention groups, rings, and fields in passing at various places in this book, but much of the book should be comprehensible without a course in algebra.”

Another site suggested that students attempting this textbook should have a familiarity with groups, rings and fields as well as possess some programming experience.

Textbook available in HTML and PDF. Exercises are included at the end of each chapter with answers and hints.

1. Prime Numbers
1. Prime Factorization
1. Primes
2. The Greatest Common Divisor
3. Numbers Factor as Products of Primes
4. The Fundamental Theorem of Arithmetic
2. The Sequence of Prime Numbers
1. There Are Infinitely Many Primes
2. Enumerating Primes
3. The Largest Known Prime
4. Primes of the Form ax+b
5. How Many Primes are There?
2. The Ring of Integers Modulo n
1. Congruences Modulo n
1. Linear Equations Modulo n
2. Fermat’s Little Theorem
3. Wilson’s Theorem
2. The Chinese Remainder Theorem
1. Multiplicative Functions
3. Quickly Computing Inverses and Huge Powers
1. How to Solve ax=1 (mod n)
2. How to Compute am (mod n)
4. Primality Testing
5. The Structure of (Z/pZ)
1. Polynomials over Z/pZ
2. Existence of Primitive Roots
3. Artin’s Conjecture
4. Computing Primitive Roots
3. Public-Key Cryptography
1. The Diffie-Hellman Key Exchange
1. The Discrete Log Problem
2. Realistic Diffie-Hellman Example
3. The Man in the Middle Attack
2. The RSA Cryptosystem
1. How RSA works
2. Encoding a Phrase in a Number
3. Some Complete Examples
3. Attacking RSA
1. Factoring n Given [epsilon](n)
2. When p and q are Close
3. Factoring n Given d
4. Further Remarks
1. Statement of the Quadratic Reciprocity Law
2. Euler’s Criterion
3. First Proof of Quadratic Reciprocity
1. Euler’s Proposition
4. A Proof of Quadratic Reciprocity Using Gauss Sums
5. Finding Square Roots
5. Continued Fractions
1. Finite Continued Fractions
1. Partial Convergents
2. The Sequence of Partial Convergents
3. Every Rational Number is Represented
2. Infinite Continued Fractions
1. The Continued Fraction Procedure
2. Convergence of Infinite Continued Fractions
3. The Continued Fraction of e
1. Preliminaries
2. Two Integral Sequences
3. A Related Sequence of Integrals
4. Extensions of the Argument
1. Periodic Continued Fractions
2. Continued Fractions of Algebraic Numbers of Higher Degree
5. Recognizing Rational Numbers From Their Decimal Expansion
6. Sums of Two Squares
6. Elliptic Curves
1. The Definition
2. The Group Structure on an Elliptic Curve
3. Integer Factorization Using Elliptic Curves
1. Pollard’s (p-1) -Method
2. Motivation for the Elliptic Curve Method
3. Lenstra’s Elliptic Curve Factorization Method
4. Examples
5. A Heuristic Explanation
4. Elliptic Curve Cryptography
1. Elliptic Curve Analogues of Diffie-Hellman
2. The ElGamal Cryptosystem and Digital Rights Management
3. The Elliptic Curve Discrete Logarithm Problem
5. Elliptic Curves Over the Rational Numbers
1. The Torsion Subgroup of E(Q) and the Rank
2. The Congruent Number Problem

View this Free Online Material at the source:

Elementary Number Theory