Skip to main content
Number Theory:
In Context and Interactive
Karl-Dieter Crisman
x
Search Results:
No results.
☰
Contents
Index
You!
Choose avatar
▻
✔️
You!
😺
👤
👽
🐶
🐼
🌈
Font family
▻
✔️
Open Sans
AaBbCc 123 PreTeXt
Roboto Serif
AaBbCc 123 PreTeXt
Adjust font
▻
Size
12
Smaller
Larger
Width
100
narrower
wider
Weight
400
thinner
heavier
Letter spacing
0
/200
closer
f a r t h e r
Word spacing
0
/50
smaller gap
larger gap
Line Spacing
135
/100
closer
together
further
apart
Light/dark mode
▻
✔️
default
pastel
twilight
dark
midnight
Reading ruler
▻
✔️
none
underline
L-underline
grey bar
light box
sunrise
sunrise underline
Motion by:
✔️
follow the mouse
up/down arrows - not yet
eye tracking - not yet
<
Prev
^
Up
Next
>
🔍
\( \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)
Front Matter
Colophon
About the Author
Dedication
Acknowledgements
To Everyone
To the Student
To the Instructor
1
Prologue
1.1
A First Problem
1.2
Review of Previous Ideas
1.2.1
Well-Ordering
1.2.2
Induction
1.2.3
Divisibility
1.3
Where are we going?
1.4
Exercises
1.5
Using Sage for Interactive Computation
2
Basic Integer Division
2.1
The Division Algorithm
2.1.1
Statement and examples
2.1.2
Proof of the Division Algorithm
2.1.3
Uses of the division algorithm
2.2
The Greatest Common Divisor
2.3
The Euclidean Algorithm
2.4
The Bezout Identity
2.4.1
Backwards with Euclid
2.4.2
Proving the final characterization
2.4.3
Other gcd questions
2.4.4
Relatively prime
2.5
Exercises
3
From Linear Equations to Geometry
3.1
Linear Diophantine Equations
3.1.1
If
\(c\)
is not a multiple of
\(\gcd(a,b)\)
3.1.2
If
\(a\)
or
\(b\)
is zero
3.1.3
If
\(c=\gcd(a,b)\)
3.1.4
If
\(c\)
is a nontrivial multiple of the gcd
3.2
Geometry of Equations
3.3
Positive
Integer Lattice Points
3.3.1
Solution ideas
3.3.2
Toward the full solution
3.4
Pythagorean Triples
3.4.1
Definition
3.4.2
Characterizing Pythagorean triples
3.4.2.1
Preliminaries
3.4.2.2
An intricate argument
3.4.2.3
The punch line
3.4.3
Areas of Pythagorean triangles
3.4.3.1
Which areas are possible?
3.4.3.2
Which areas are square?
3.5
Surprises in Integer Equations
3.6
Exercises
3.7
Two facts from the gcd
4
First Steps with Congruence
4.1
Introduction to Congruence
4.2
Going Modulo First
4.3
Properties of Congruence
4.4
Equivalence classes
4.5
Why modular arithmetic matters
4.5.1
Starting to see further
4.5.2
Taking powers
4.6
Toward Congruences
4.7
Exercises
5
Linear Congruences
5.1
Solving Linear Congruences
5.2
A Strategy For the First Solution
5.3
Systems of Linear Congruences
5.3.1
Introducing the Chinese Remainder Theorem
5.3.2
The inverse of a number
5.4
Using the Chinese Remainder Theorem
5.4.1
Constructing simultaneous solutions
5.4.2
A theoretical but highly important use of CRT
5.5
More Complicated Cases
5.5.1
Moduli which are not coprime
5.5.2
The case of coefficients
5.5.3
A practical application
5.6
Exercises
6
Prime Time
6.1
Introduction to Primes
6.1.1
Definitions and examples
6.1.2
Prime fun
6.2
To Infinity and Beyond
6.2.1
Infinite primes
6.2.2
The sieve of Eratosthenes
6.3
The Fundamental Theorem of Arithmetic
6.3.1
Preliminaries and statement
6.3.2
Proof of the FTA
6.4
First consequences of the FTA
6.5
Applications to Congruences
6.5.1
Factoring the modulus
6.5.2
Moduli that are prime powers
6.6
Exercises
7
First Steps With General Congruences
7.1
Exploring Patterns in Square Roots
7.2
From Linear to General
7.2.1
Combining solutions
7.2.2
Prime power congruences
7.3
Congruences as Solutions to Congruences
7.4
Polynomials and Lagrange’s Theorem
7.5
Wilson’s Theorem and Fermat’s Theorem
7.5.1
Wilson’s Theorem
7.5.2
Fermat’s Little Theorem
7.6
Epilogue: Why Congruences Matter
7.7
Exercises
7.8
Counting Proofs of Congruences
7.8.1
Counting motivation
7.8.2
The combinatorial proofs
8
The Group of Integers Modulo
\(n\)
8.1
The Integers Modulo
\(n\)
8.1.1
Definition
8.1.2
Visualization
8.1.3
Inverses
8.2
Powers
8.2.1
Returning to visualizing
8.3
Essential Group Facts for Number Theory
8.3.1
Step-by-step notions to the definition
8.3.1.1
Sets
8.3.1.2
Binary operations
8.3.1.3
Closed operations
8.3.1.4
Associative operations
8.3.1.5
Identity
8.3.1.6
Inverses
8.3.2
What is a group?
8.3.3
Properties of groups we will need
8.3.3.1
Solutions to equations
8.3.3.2
Inverses of product
8.3.3.3
Finite groups
8.3.3.4
Order of a group
8.3.3.5
Order of an element
8.3.3.6
The connection
8.3.3.7
Cyclic groups
8.3.3.8
Abelian groups
8.4
Exercises
9
The Group of Units and Euler’s Function
9.1
Groups and Number Systems
9.1.1
Solving linear equations – again
9.1.2
A new group
9.1.2.1
The group of units
9.1.2.2
More facts and examples
9.2
The Euler Phi Function
9.2.1
Euler’s theorem
9.3
Using Euler’s Theorem
9.3.1
Inverses
9.3.2
Using Euler’s theorem with the CRT
9.4
Exploring Euler’s Function
9.5
Proofs and Reasons
9.5.1
Computing prime powers
9.5.2
Multiplicativity
9.5.3
Addition Formula
9.5.4
Even more questions
9.6
Exercises
9.7
The Conductor, solved
10
Primitive Roots
10.1
Primitive Roots
10.1.1
Definition
10.1.2
Two characterizations
10.1.3
Finding primitive roots
10.2
A Better Way to Primitive Roots
10.2.1
A useful lemma
10.2.2
Using the test lemma
10.3
When Does a Primitive Root Exist?
10.3.1
Primitive roots of powers of two
10.3.2
Two important lemmas
10.3.2.1
How the lemmas work
10.3.2.2
How the lemmas (don’t) fail
10.4
Prime Numbers Have Primitive Roots
10.5
A Practical Use of Primitive Roots
10.5.1
Finding a higher root
10.5.2
Discrete logarithms
10.6
Exercises
10.7
All the Primitive Roots
11
An Introduction to Cryptography
11.1
What is Cryptography?
11.1.1
Encoding and decoding
11.2
Encryption
11.2.1
Simple ciphers
11.2.2
Decryption and inverses
11.2.3
Getting more sophisticated
11.2.4
Linear algebra and encryption
11.2.5
Asymmetric key cryptography
11.3
A Modular Exponentiation Cipher
11.3.1
The Diffie-Hellman method
11.3.2
A bigger example
11.3.3
Recap
11.3.4
A brief warning
11.4
An Interesting Application: Key Exchange
11.4.1
Diffie-Hellman Key Exchange
11.4.2
In the Middle
11.5
RSA Public Key
11.5.1
The background
11.5.2
The practice of RSA
11.5.3
Why RSA works
11.6
RSA and (Lack Of) Security
11.6.1
Beating the man in the middle
11.6.2
A cautionary tale
11.6.3
The explanation
11.6.4
A solution
11.7
Other applications
11.7.1
Secret sharing
11.8
Exercises
12
Some Theory Behind Cryptography
12.1
Finding More Primes
12.1.1
Fermat primes
12.1.2
Primes from Fermat numbers
12.1.3
Mersenne primes
12.1.4
Primes from Mersenne numbers
12.2
Primes – Probably
12.2.1
Pseudoprimes
12.2.2
Prime impostors, and how to avoid them
12.3
Another Primality Test
12.3.1
Another pattern
12.3.2
Miller’s test
12.4
Strong Pseudoprimes
12.5
Introduction to Factorization
12.5.1
Factorization and the RSA
12.5.2
Trial division
12.5.3
Starting in the middle
12.6
A Taste of Modernity
12.6.1
The Pollard Rho algorithm
12.6.2
More factorization
12.7
Exercises
13
Sums of Squares
13.1
Some First Ideas
13.1.1
A first pattern
13.1.2
Geometry
13.1.3
Connections to some very old mathematics
13.2
At Most One Way For Primes
13.3
A Lemma About Square Roots Modulo
\(n\)
13.4
Primes as Sum of Squares
13.4.1
A useful plot
13.4.2
Primes which are sums of squares
13.4.3
Visualizing the proof
13.4.4
Finishing the proof
13.5
All the Squares Fit to be Summed
13.6
A One-Sentence Proof
13.7
Exercises
14
Beyond Sums of Squares
14.1
A Complex Situation
14.1.1
A new interpretation
14.1.2
Revisiting the norm
14.1.3
A different approach to sums of squares
14.2
More Sums of Squares and Beyond
14.2.1
Summing more squares
14.2.2
Beyond squares
14.2.3
Waring’s problem
14.3
Related Questions About Sums
14.4
Exercises
15
Points on Curves
15.1
Rational Points on Conics
15.1.1
Rational points on the circle
15.1.2
Parametrization in general
15.1.3
When curves don’t have rational points
15.2
A tempting cubic interlude
15.3
Bachet and Mordell Curves
15.3.1
Verifying points don’t exist
15.3.2
More on Mordell
15.4
Points on Quadratic Curves
15.4.1
Transforming conic sections
15.4.2
More conic sections
15.5
Making More and More and More Points
15.5.1
Toward integer points
15.5.2
A surprising application
15.6
The Algebraic Story
15.6.1
Computing the hyperbola
15.6.2
Yet more number systems
15.6.3
The general solution (any
\(n\)
)
15.7
Exercises
16
Solving Quadratic Congruences
16.1
Square Roots
16.1.1
Recalling existing answers
16.1.2
Finding more answers
16.2
General Quadratic Congruences
16.2.1
Completing the square solves our woes
16.3
Quadratic Residues
16.3.1
Some definitions
16.3.2
First try for new square roots
16.3.3
Some history
16.4
Send in the Groups
16.4.1
Quadratic residues form a group
16.4.2
Quadratic residues connect to primitive roots
16.5
Euler’s Criterion
16.6
Introducing the Legendre Symbol
16.7
Our First Full Computation
16.8
Exercises
17
Quadratic Reciprocity
17.1
More Legendre Symbols
17.2
Another Criterion
17.2.1
Laying the foundation
17.2.2
Getting the new criterion
17.2.3
The final form
17.3
Using Eisenstein’s Criterion
17.4
Quadratic Reciprocity
17.4.1
The theorem
17.4.2
Why is this theorem different from all other theorems?
17.4.2.1
What does it mean?
17.4.2.2
What does it do?
17.4.2.3
The Jacobi symbol
17.5
Some Surprising Applications of QR
17.5.1
Factoring, briefly
17.5.2
Primality testing
17.5.3
Yes, even cryptography
17.5.4
Solving equations
17.5.5
Artin’s conjecture
17.6
A Proof of Quadratic Reciprocity
17.6.1
Re-enter geometry
17.6.2
Proving proper parity
17.6.3
Postlude
17.7
Exercises
18
An Introduction to Functions
18.1
Three Questions for Euler phi
18.1.1
Formulas
18.1.2
Relations
18.1.3
Summation (and limits)
18.2
Three Questions, Again
18.2.1
Formulas
18.2.2
Relations
18.2.3
Limits (and summation)
18.3
Exercises
19
Counting and Summing Divisors
19.1
Exploring a New Sequence of Functions
19.2
Conjectures and Proofs
19.2.1
Prime powers
19.2.2
Multiplicativity
19.2.3
A very powerful lemma
19.3
The Size of the Sum of Divisors Function
19.4
Perfect Numbers
19.4.1
A perfect definition and theorem
19.4.2
Speculation and more terminology
19.4.3
The abundancy index
19.4.4
Amicable Numbers
19.5
Odd
Perfect Numbers
19.5.1
Are there odd perfect numbers?
19.5.2
The abundancy index and odd perfect numbers
19.5.3
Even more about odd perfect numbers, if they exist
19.6
Exercises
20
Long-Term Function Behavior
20.1
Sums of Squares, Once More
20.1.1
Errors, not just limits
20.1.2
Landau notation
20.2
Average of Tau
20.2.1
Beginnings
20.2.2
Heuristics for tau
20.2.3
Using sums to get closer
20.2.4
But Big-Oh isn’t enough
20.3
Digging Deeper and Finding Limits
20.3.1
Moving toward a proof
20.3.2
Getting a handle on error
20.3.3
The end of the story
20.4
Heuristics for the Sum of Divisors
20.4.1
Numbers instead of points
20.4.2
Order calculations and more
20.5
Looking Ahead
20.6
Exercises
21
The Prime Counting Function
21.1
First Steps
21.1.1
A funky formula
21.1.2
A very low bound
21.1.3
Knowledge from nowhere
21.2
Some History
21.2.1
The first really accurate estimate and errors
21.2.2
Exploring
\(Li\)
21.3
The Prime Number Theorem
21.3.1
Stating the theorem
21.3.2
Chebyshev’s contributions
21.4
A Slice of the Prime Number Theorem
21.4.1
Functions to know
21.4.2
Getting a formula with sleights of hand
21.4.3
Finish the proof
21.5
Exercises
22
More on Prime Numbers
22.1
Prime Races
22.1.1
Infinitude of types of primes
22.1.2
Back to bias
22.1.3
Other prime races
22.2
Sequences and Primes
22.2.1
Primes in sequences
22.2.2
Sequences in primes
22.3
Types of Primes
22.3.1
Twin primes
22.3.2
Heuristics for twin primes
22.3.3
Other types of primes
22.4
Exercises
23
New Functions from Old
23.1
The Moebius Function
23.1.1
Möbius mu
23.1.2
A formula
23.1.3
Another definition
23.2
Inverting Functions
23.2.1
Some useful notation
23.2.2
Proof of Moebius inversion
23.3
Making New Functions
23.3.1
First new functions
23.3.2
More new functions
23.4
Generalizing Moebius
23.4.1
The monoid of arithmetic functions
23.4.2
Bringing in group structure
23.4.3
More dividends from structure
23.5
Exercises
24
Infinite Sums and Products
24.1
Products and Sums
24.1.1
Products
24.1.2
Products that are sums
24.2
The Riemann Zeta Function
24.2.1
A fundamental function
24.2.2
Motivating the Zeta function
24.2.3
Being careful
24.3
From Riemann to Dirichlet and Euler
24.3.1
Dirichlet series
24.3.2
Euler products
24.4
Multiplication
24.5
More series and convergence
24.5.1
A series for Euler phi and a general theorem
24.5.2
A missing step: Convergence of Dirichlet series
24.6
Four Facts
24.6.1
Random integer lattice points
24.6.2
Dirichlet for the absolute Moebius
24.6.3
The prime harmonic series
24.6.4
The average value of Euler phi
24.7
Exercises
25
Further Up and Further In
25.1
Taking the PNT Further
25.2
Improving the PNT
25.3
Toward the Riemann Hypothesis
25.3.1
Zeta beyond the series
25.3.2
Zeta on some lines
25.4
Connecting to the Primes
25.4.1
Connecting to Moebius
25.5
Connecting to Zeta
25.5.1
Turning the golden key
25.5.2
Detailing the connections
25.6
Connecting to Zeros
25.6.1
Where are the zeros?
25.6.2
Analyzing the connection
25.7
The Riemann Explicit Formula
25.8
Epilogue
25.9
Exercises
Back Matter
A
List of Sage notes
B
List of Historical Remarks
C
Notation
D
List of Figures
E
References and Further Resources
E.1
Introduction to the References
E.2
General References
E.3
Proof and Programming References
E.4
Specialized References
E.5
Historical References
E.6
Other References
E.7
Useful Articles
Index
Dedication
Dedication
To my students and the Sage community;
let’s keep exploring together.