Skip to main content
\( \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)
Number Theory:
In Context and Interactive
Karl-Dieter Crisman
Contents
Index
Prev
Up
Next
Contents
Prev
Up
Next
Front Matter
Colophon
About the Author
Dedication
Acknowledgements
To Everyone
To the Student
To the Instructor
1
Prologue
A First Problem
Review of Previous Ideas
Where are we going?
Exercises
Using Sage for Interactive Computation
2
Basic Integer Division
The Division Algorithm
The Greatest Common Divisor
The Euclidean Algorithm
The Bezout Identity
Exercises
3
From Linear Equations to Geometry
Linear Diophantine Equations
Geometry of Equations
Positive
Integer Lattice Points
Pythagorean Triples
Surprises in Integer Equations
Exercises
Two facts from the gcd
4
First Steps with Congruence
Introduction to Congruence
Going Modulo First
Properties of Congruence
Equivalence classes
Why modular arithmetic matters
Toward Congruences
Exercises
5
Linear Congruences
Solving Linear Congruences
A Strategy For the First Solution
Systems of Linear Congruences
Using the Chinese Remainder Theorem
More Complicated Cases
Exercises
6
Prime Time
Introduction to Primes
To Infinity and Beyond
The Fundamental Theorem of Arithmetic
First consequences of the FTA
Applications to Congruences
Exercises
7
First Steps With General Congruences
Exploring Patterns in Square Roots
From Linear to General
Congruences as Solutions to Congruences
Polynomials and Lagrange's Theorem
Wilson's Theorem and Fermat's Theorem
Epilogue: Why Congruences Matter
Exercises
Counting Proofs of Congruences
8
The Group of Integers Modulo \(n\)
The Integers Modulo \(n\)
Powers
Essential Group Facts for Number Theory
Exercises
9
The Group of Units and Euler's Function
Groups and Number Systems
The Euler Phi Function
Using Euler's Theorem
Exploring Euler's Function
Proofs and Reasons
Exercises
10
Primitive Roots
Primitive Roots
A Better Way to Primitive Roots
When Does a Primitive Root Exist?
Prime Numbers Have Primitive Roots
A Practical Use of Primitive Roots
Exercises
11
An Introduction to Cryptography
What is Cryptography?
Encryption
A Modular Exponentiation Cipher
An Interesting Application: Key Exchange
RSA Public Key
RSA and (Lack Of) Security
Other applications
Exercises
12
Some Theory Behind Cryptography
Finding More Primes
Primes – Probably
Another Primality Test
Strong Pseudoprimes
Introduction to Factorization
A Taste of Modernity
Exercises
13
Sums of Squares
Some First Ideas
At Most One Way For Primes
A Lemma About Square Roots Modulo \(n\)
Primes as Sum of Squares
All the Squares Fit to be Summed
A One-Sentence Proof
Exercises
14
Beyond Sums of Squares
A Complex Situation
More Sums of Squares and Beyond
Related Questions About Sums
Exercises
15
Points on Curves
Rational Points on Conics
A tempting cubic interlude
Bachet and Mordell Curves
Points on Quadratic Curves
Making More and More and More Points
The Algebraic Story
Exercises
16
Solving Quadratic Congruences
Square Roots
General Quadratic Congruences
Quadratic Residues
Send in the Groups
Euler's Criterion
Introducing the Legendre Symbol
Our First Full Computation
Exercises
17
Quadratic Reciprocity
More Legendre Symbols
Another Criterion
Using Eisenstein's Criterion
Quadratic Reciprocity
Some Surprising Applications of QR
A Proof of Quadratic Reciprocity
Exercises
18
An Introduction to Functions
Three Questions for Euler phi
Three Questions, Again
Exercises
19
Counting and Summing Divisors
Exploring a New Sequence of Functions
Conjectures and Proofs
The Size of the Sum of Divisors Function
Perfect Numbers
Odd
Perfect Numbers
Exercises
20
Long-Term Function Behavior
Sums of Squares, Once More
Average of Tau
Digging Deeper and Finding Limits
Heuristics for the Sum of Divisors
Looking Ahead
Exercises
21
The Prime Counting Function
First Steps
Some History
The Prime Number Theorem
A Slice of the Prime Number Theorem
Exercises
22
More on Prime Numbers
Prime Races
Sequences and Primes
Types of Primes
Exercises
23
New Functions from Old
The Moebius Function
Inverting Functions
Making New Functions
Generalizing Moebius
Exercises
24
Infinite Sums and Products
Products and Sums
The Riemann Zeta Function
From Riemann to Dirichlet and Euler
Multiplication
Multiplication and Inverses
Four Facts
Exercises
25
Further Up and Further In
Taking the PNT Further
Improving the PNT
Toward the Riemann Hypothesis
Connecting to the Primes
Connecting to Zeta
Connecting to Zeros
The Riemann Explicit Formula
Epilogue
Exercises
Back Matter
A
List of Sage notes
B
List of Historical Remarks
C
Notation
D
List of Figures
E
References and Further Resources
Introduction to the References
General References
Proof and Programming References
Specialized References
Historical References
Other References
Useful Articles
Index
Authored in PreTeXt
A
List of Sage notes
B
List of Historical Remarks
C
Notation
D
List of Figures
E
References and Further Resources
Index
