Elementary number theory turns experiments with integers into proofs about divisibility and congruences. Stein develops that route with Euclidean algorithms, modular arithmetic and quadratic reciprocity. Shoup connects integer and finite-field arithmetic to algorithms and cryptography. Choose the first route to strengthen proof and congruence skills; choose the computational continuation when you can explain an algorithm's correctness as well as produce its output.
What to work on
Use the Euclidean algorithm and Bezout's identity.
Solve congruences and apply the Chinese remainder theorem.
Compute modular inverses and powers with stated coprimality conditions.
Use quadratic reciprocity and Euler's criterion.
A starting text
Elementary Number Theory: Primes, Congruences, and Secrets — William Stein. Read 1.1 on factorization and the Euclidean algorithm; 2.1-2.3 on congruences, the Chinese remainder theorem, inverses and powers; then 4.1-4.3 on quadratic reciprocity and Euler's criterion.
Choosing what to read
Run the extended Euclidean algorithm by hand and interpret its coefficients as a proof of a modular inverse. Solve a Chinese remainder problem, then verify the solution in every modulus. List small quadratic residues before applying reciprocity, keeping track of the parity signs. For an algorithmic example, separate correctness, termination and cost. Test a calculation on small inputs, but explain why the proof covers all permitted inputs rather than using numerical evidence as the final argument.
Connect Euclid's algorithm, modular inverses and quadratic residues.
How it reads
Proof-based arithmetic with explicit congruence and reciprocity calculations.
What it expects
Integer arithmetic and introductory proofs.
What to keep in mind
Cryptography and elliptic curves are optional continuations; the selected arithmetic route does not cover their full foundations.
Practice
Public exercises and an Answers and Hints section are present. It contains selected answers and proof hints, not a verified complete worked solution manual. Sections 1.3, 2.6 and 4.6 contain the exercise sets. Answers and Hints begins on printed page 149; match the chapter and exercise number.
Complete public PDF.
Edition, reading range and source
Read 1.1 on factorization and the Euclidean algorithm; 2.1-2.3 on congruences, the Chinese remainder theorem, inverses and powers; then 4.1-4.3 on quadratic reciprocity and Euler's criterion.
Congruence and quadratic-residue exercises with selected hints. Sections 1.3, 2.6 and 4.6 contain the exercise sets. Answers and Hints begins on printed page 149; match the chapter and exercise number.. Public exercises and an Answers and Hints section are present. It contains selected answers and proof hints, not a verified complete worked solution manual.
Try these before moving on
Try a proof or calculation before opening the hint. These solutions address the checks below, not the exercises in the linked textbooks.
Use the extended Euclidean algorithm to find the inverse of 17 modulo 43, and solve x=2 modulo 3, x=3 modulo 5 and x=2 modulo 7, with a uniqueness statement.
A hint
Back-substitute the Euclidean divisions. Combine the congruences modulo 3 and 7 first.
Work through the solution
The divisions are 43=2⋅17+9, 17=9+8, and 9=8+1. Back-substitution gives 1=2⋅9−17=2⋅43−5⋅17. Thus 17−1≡−5≡38(mod43), checked by 17⋅38=646=15⋅43+1.
The conditions modulo 3 and 7 together mean x=2+21k for some integer k, since these moduli are coprime. Modulo 5, this becomes 2+k≡3, hence k=1+5m. Therefore x=23+105m for m∈Z. The value 23 has residues 2,3,2 modulo 3,5,7. Any two solutions differ by an integer divisible by all three pairwise coprime moduli, hence by 105, proving uniqueness modulo 105.
Already comfortable with this? Skip the congruence review if you can justify the inverse and CRT constructions. Skip the residue selection if reciprocity, its sign and the supplementary laws are usable without a table.
Connects classical topics with computation, cryptography and elliptic curves. Broader than a minimal congruences course; later chapters benefit from abstract algebra.
Preparation: Proofs; basic algebra, rings and fields.
George E. Andrews · Textbook · Introductory · English · Purchase / institutional access
Purchase or institutional access required; previews are not the complete book.
A first-course presentation of integer arithmetic and classical number-theoretic problems. The linked publisher page is a purchase route, not an open full text.
Preparation: Integer arithmetic and proof-writing; extra algebra for advanced sections.
Wissam Raji · Open textbook · Introductory · English · Online text
Licensed CC BY HTML book on LibreTexts; full chapter/section reading pages opened without login.
An undergraduate text on primes, congruences, arithmetic functions, quadratic residues and continued fractions, with later introductions to analytic topics.
Preparation: Elementary algebra and proof-writing; later chapters need analysis and abstract algebra.
Use: A first structured number-theory reading route, followed by selected advanced chapters.
W. Edwin Clark; revised by Jim Hefferon · Textbook · Introductory · English · PDF
Reviser's university-hosted archive provides the complete 82-page PDF; its notice permits noncommercial redistribution.
Develops divisibility, prime numbers, congruences, arithmetic functions, primality tests and public-key cryptography through short theorem-based chapters.
Preparation: School algebra; basic sets and functions. Calculus I is suggested in the preface, chiefly for mathematical maturity.
Use: Build proof-writing skill while learning elementary arithmetic theory.
Victor Shoup · Textbook · Intermediate · English · Full-text access unverified
Connects integer and finite-field arithmetic with algorithms and cryptography. A computational route complementing a traditional proof-based number theory course.
Preparation: Integer arithmetic and proof-writing; extra algebra for advanced sections.
Kimball Martin · Long lecture notes · Intermediate · English · PDF
Full PDF opened publicly on the author or university host.
Moves from integer arithmetic to rings, quadratic and cyclotomic examples, factorization, congruences and sums of squares. Later chapters are drafts or outlines.
Preparation: Proof-writing and elementary algebra; rings and fields are introduced in the notes.
Use: Connect elementary number theory with algebraic structures without treating unfinished later chapters as a complete advanced course.