Number TheoryIn Context and Interactive

Karl-Dieter Crisman

Previous Up Next

Previous Up Next

Front Matter

Copyright Information
To Everyone
To the Student
To the Instructor
About the Author
Dedication
Acknowledgements

1Prologue

A first problem
Review of previous ideas
Where are we going?
Exercises
How to use computation

2Basic Integer Division

The Division Algorithm
The GCD
The Euclidean Algorithm
The Bezout Identity
Exercises

3From 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

4Prime Time

To Infinity and Beyond
The Fundamental Theorem of Arithmetic
Exercises

5First Steps with Congruence

Introduction to Congruence
Going Modulo First
Properties of Congruence
Equivalence classes
Toward Congruences
Exercises

6Linear Congruences

Solving Linear Congruences
A bigger strategy
Systems of Linear Congruences
Using the Chinese Remainder Theorem
More complicated cases
Exercises

7Important Congruence Theorems

Prime fun and Square Roots
From Linear to General?
Wilson's Theorem and Fermat's Little Theorem
Polynomials and Lagrange's Theorem
Epilogue: Why congruences matter
Exercises

8The Group of Integers Modulo \(n\)

The integers modulo \(n\)
Powers
Essential Facts about Groups for Number Theory

9The Group of Units and the Euler \(\phi\) Function

Groups and Number Systems
The Euler Phi Function
Using Euler's Theorem
Exploring Euler's Function
Proofs and reasons
Exercises

10Primitive Roots

Primitive Roots
A better way to primitive roots
When is there a primitive root?
Prime numbers have primitive roots
A practical use of primitive roots
Exercises

11An Introduction to Cryptography

What is cryptography?
Encryption
A modular exponentiation cipher
An interesting application: key exchange
RSA Public Key
RSA and (lack of) security
Exercises

12Some theory behind cryptographic practice

Finding More Primes
Primes — Probably
Another primality test
Strong Pseudoprimes
Introduction to Factorization
A Taste of Modernity
Exercises

13Sums of Squares

Some First Ideas
Primes can be written in at most one way
A Lemma about Square Roots Modulo \(n\)
Primes as Sum of Squares
Proving sums of squares
All the squares fit to be summed
A One-Sentence Proof
Exercises

14Beyond Sums of Squares

A Complex Situation
More sums of squares
Related Questions about Sums
Exercises

15Points on Curves

Rational Points on Conics
More about points, rational and integer
Bachet and Mordell curves
More on Mordell
Points on Quadratic Curves
Making more and more and more points
The algebraic story
Exercises

16Solving Quadratic Congruences

Square Roots
General quadratic congruences
Quadratic residues
Send in the Groups
Euler's Criterion
The Legendre Symbol
Our First Full Computation
Exercises

17Quadratic Reciprocity

More Legendre Symbols
Another Criterion
Using Eisenstein's Criterion
Quadratic Reciprocity
Some Surprising Applications of QR
A Proof of Quadratic Reciprocity
Exercises

18An Introduction to Functions

Three questions
Three questions, again
Exercises

19Counting and Summing Divisors

Exploration: a new sequence of functions
Conjectures and proofs
The size of the sum of divisors function
Perfect Numbers
More regarding perfection
Odd Perfect Numbers
Exercises

20Long-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

21The Prime Counting Function

First Steps
Some history
The Prime Number Theorem
A slice of the Prime Number Theorem
Exercises

22More on Prime Numbers

Prime Races
Sequences and Primes
Types of Primes
Exercises

23New Functions from Old

The Moebius function
New Arithmetic Functions from Old
Making new functions
Generalizing Moebius
Exercises

24Infinite Sums and Products

Products and Sums
The Riemann Zeta Function
From Riemann to Dirichlet and Euler
Multiplication
Multiplication and Inverses
Four Facts
Exercises

25Further 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

Authored in MathBook XML

Chapter9The Group of Units and the Euler \(\phi\) Function

9.1Groups and Number Systems 9.2The Euler Phi Function 9.3Using Euler's Theorem 9.4Exploring Euler's Function 9.5Proofs and reasons 9.6Exercises