Skip to main content

\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Number TheoryIn Context and Interactive

Karl-Dieter Crisman

IndexPrev Up Next

Front Matter

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

1Prologue

A First Problem
Review of Previous Ideas
Where are we going?
Exercises
How to Use Computation

2Basic Integer Division

The Division Algorithm
The Greatest Common Divisor
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

4First Steps with Congruence

Introduction to Congruence
Going Modulo First
Properties of Congruence
Equivalence classes
Why modular arithmetic matters
Toward Congruences
Exercises

5Linear Congruences

Solving Linear Congruences
A Strategy For the First Solution
Systems of Linear Congruences
Using the Chinese Remainder Theorem
More Complicated Cases
Exercises

6Prime Time

Introduction to Primes
To Infinity and Beyond
The Fundamental Theorem of Arithmetic
First consequences of the FTA
Applications to Congruences
Exercises

7First 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

8The Group of Integers Modulo \(n\)

The Integers Modulo \(n\)
Powers
Essential Group Facts for Number Theory
Exercises

9The 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

10Primitive 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

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
Other applications
Exercises

12Some Theory Behind Cryptography

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
All the Squares Fit to be Summed
A One-Sentence Proof
Exercises

14Beyond Sums of Squares

A Complex Situation
More Sums of Squares and Beyond
Related Questions About Sums
Exercises

15Points 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

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 for Euler phi
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
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
Inverting Functions
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

Back Matter

List of Sage notes
Notation
References and Further Resources
Index

Authored in MathBook XML

Chapter9The Group of Units and Euler's Function¶ permalink

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

web analytics