NOTES ON NUMBER THEORY

1. The Integers, Integer Division, Primes and Composites, and Linear Diophantine Equations

1.1. Integer Division

Integer Division
Greatest Common Divisor
The Division Algorithm for Positive Integers
The Euclidean Algorithm
Linear Diophantine Equations
Solutions to Linear Diophantine Equations

1.2. Prime Numbers, Composite Numbers, and Unique Factorization

Primes Numbers
Composite Numbers
Unique Factorization
Prime Power Decomposition
Example Questions Regarding Primes and Composites

2. Modular Arithmetic, Congruences, Linear Congruences, Fermat's and Wilson's Theorem

2.1. Congruent Integers Modulo m

Congruences Modulo m
Basic Properties of Congruences Modulo m 1
Basic Properties of Congruences Modulo m 2
Examples Problems Involving Congruences
Tests for Divisibility
Determining the Last Digit of Large Numbers

2.2. Linear Congruences

Linear Congruences
Existence of Solutions to Linear Congruences
Solving Linear Congruences 1
Solving Linear Congruences 2
Solving Linear Congruences 3
Solving Linear Diophantine Equations with Linear Congruences
Systems of Linear Congruences
The Chinese Remainder Theorem
Solving Systems of Linear Congruences 1
Solving Systems of Linear Congruences 2

2.3. Hensel's Lemma

Hensel's Lemma
Examples of Applying Hensel's Lemma
Solving f(x) ≡ 0 (mod p^k) without Hensel's Lemma

2.4. RSA Encryption

RSA Encryption
Additional Examples of Creating RSA Decryption Keys
Additional Examples of Finding RSA Decryption Keys
Examples of Encrypting with RSA $C \equiv P e (mod n)$
Examples of Decrypting with RSA $P \equiv C d (mod n)$

2.5. Fermat's Little Theorem and Wilson's Theorem

Fermat's Little Theorem
Wilson's Theorem
Determining the Remainder of Large Factorials

3. The d, σ, and ϕ Functions

3.1. The d Function

The Number of Positive Divisors of an Integer ( Examples 1 | Examples 2 )

3.2. The σ Function

The Sum of Positive Divisors of an Integer ( Examples 1 )
k-Perfect, Abundant, and Deficient Numbers ( Examples 1 )
Aliquot Sequences, Amicable Pairs, and Sociable Numbers ( Examples 1 )

3.3. Euler's ϕ Function

Euler's Totient Function ( Examples 1 | Examples 2 )
Euler's Totient Function on Odd and Even Natural Numbers
Euler's Totient Theorem

4. Quadratic Reciprocity

4.1. The Order of n (mod m)

The Order of a Natural Number Modulo m
The Primitive Roots of a Natural Number
The Number of Primitive Roots of a Natural Number
Determining the Primitive Roots of a Natural Number

4.2. Quadratic Congruences

Quadratic Congruences
Euler's Criterion

4.3. Legendre Symbols

Legendre Symbols
Gauss's Lemma
- Example Questions Regarding Gauss's Lemma
Legendre Symbol Rules for (-1/p) and (2/p)
Legendre Symbol Rules for (3/p) and (6/p)
The Quadratic Reciprocity Theorem
- Additional Examples of Evaluating Legendre Symbols

4.4. Jacobi Symbols

Jacobi Symbols
Examples of Computing Jacobi Symbols

5. Binary Quadratic Forms

5.1. Binary Quadratic Forms

Binary Quadratic Forms
The Discriminant of a Binary Quadratic Form
Indefinite, Semidefinite, and Definite Binary Quadratic Forms
IFF Criterion for a Binary Quadratic Form to Have a Discriminant d

5.2. Sums of Two Squares

A Product of a Sum of Two Squares is a Sum of Two Squares
Expressing Integers as a Sum of Two Squares
Examples of Expressing Integers as a Sum of Two Squares

5.3. Equivalence and Reduction of Binary Quadratic Forms

Proper Representation Criterion for Binary Quadratic Forms
Equivalent Binary Quadratic Forms
Example Problems Regarding Equivalent Binary Quadratic Forms
The Class Number H(d) of a Discriminant d
Reduced Binary Quadratic Forms
Reducing Binary Quadratic Forms
Examples of Reducing Binary Quadratic Forms 1
Examples of Reducing Binary Quadratic Forms 2
Computing the Class Number H(-3)
Computing the Class Number H(-11)
Computing the Class Number H(-39)
Expressing Integers Properly as a Sum of Two Squares
The Functions R(n), r(n), P(n), and N(n)
A Formula for P(n) = N(n)

6. Arithmetic Functions and Dirichlet Convolutions

6.1. Arithmetic Functions

Arithmetic Functions (Additive and Multiplicative)

6.2. Dirichlet Convolutions

The Dirichlet Convolution of Two Arithmetic Functions
Examples of Dirichlet Convolutions of Two Arithmetic Functions

6.3. The Möbius Inversion Formula

The Möbius Function
The Dirichlet Convolution μ * 1 = ꙇ
The Möbius Inversion Formula

7. Approximation

7.1. Farey Sequences and Dirichlet's Approximation Theorem

Farey Sequences
Theorems Regarding Farey Sequences
Dirichlet's Approximation Theorem
Dirichlet's Approximation Theorem by Farey Sequences

7.2. Irrational Number Approximation

Irrational Number Approximation by Rational Numbers
Hurwitz's Theorem
An Example of a Series Converging to an Irrational Numbers

7.3. Algebraic Number Approximation

Algebraic and Transcendental Numbers
Algebraic Number Approximation
An Example of a Series Converging to a Transcendental Number

7.4. Irrational Numbers

The Rational Roots Theorem
Rational and Irrational Values of cosθ, sinθ, and tanθ
Proof that e is Irrational
Proof that Pi is Irrational

7.5. Geometry of Numbers

Blichfeldt's Principle
Lattices in Rn
Minkowski's Convex Body Theorem
Proof that if p ≡ 1 (mod 4) then p is the Sum of 2 Squares by Minkowski's Convex Body Theorem
Lagrange's Four Square Theorem

7.6. Continued Fractions

Continued Fractions
Finite Continued Fractions and Rational Numbers
The Sequences (hn) and (kn)
The nth Convergent of an Infinite Continued Fraction
Convergence of Infinite Continued Fractions
Infinite Continued Fractions and Irrational Numbers
Examples of Computing Infinite Continued Fractions
Irrational Number Approximation by Infinite Continued Fractions

The Order of a (mod m)
Primitive Roots
- Determining the Number of Primitive Roots a Prime Has
- Determining if r is a Primitive Root of n
- Finding Other Primitive Roots (mod p)

Quadratic Congruences $x 2 \equiv a (mod p)$
Euler's Criterion If p is an odd prime and $p ∤ a$ , then $a p - 1 2 \equiv 1 (mod p)$ or $a p - 1 2 \equiv - 1 (mod p)$ .
Legendre Symbols $(a / p) = \pm 1$
Gauss's Lemma (a/p)=(−1)g
- Example Questions Regarding Gauss's Lemma
Legendre Symbol Rules for (-1/p) and (2/p)
Legendre Symbol Rules for (3/p) and (6/p)
The Quadratic Reciprocity Theorem (p/q)=−(q/p) if [p≡q≡3(mod4), otherwise (p/q)=(q/p)
- Additional Examples of Evaluating Legendre Symbols
Pythagorean Triangles x2+y2=z2 for x,y,z∈Z.
- Examples of Pythagorean Triangle Questions

Submit an Error: Do you think that you see an error in any of the pages? Click the link and let us know so that we can fix it as soon as possible! All help is greatly appreciated with there being so many possibilities that can be overlooked.

Queue

Congruences a≡b(modm).
- Example Questions Regarding Congruences
Divisibility Tests
Last Digits of Large Numbers
Linear Congruences ax≡b(modm).
- Additional Examples of Solving Linear Congruences
- Additional Examples of Solving Linear Congruences 2

Fermat's Theorem If p is prime, and (a, p) = 1, then $a p - 1 \equiv 1 (mod p)$ .
Wilson's Theorem p is prime if and only if $(p - 1)! \equiv - 1 (mod p)$ .

Solving Linear Diophantine Equations with Congruences

The Number of Positive Divisors of an Integer n, d(n) d(n)=∑d∣n1
- Additional Examples of Calculating d(n) for Large Integers
The Sum of Positive Divisors of an Integer n, σ(n) σ(n)=∑d∣nd
- Additional Examples of Calculating σ(n) for Large Integers $σ (p n) = p n + 1 - 1 p - 1$ .
Euler's Theorem and Euler's Totient Function (Euler's Φ-Function) If (a, m) = 1, then aϕ(m)≡1(modm).
- Examples Using Euler's Theorem
- Examples of Finding Remainders of Large Numbers
Calculating Φ for Large Positive Integers $ϕ (p n) = p n - 1 (p - 1)$ .

Additional Examples of Calculating Φ for Large Integers
k-Perfect, Abundant, and Deficient Numbers σ(n)=kn, σ(n)≥2n, and σ(n)≤2n.
- Example Questions Regarding k-Perfect, Abundant, and Deficient Numbers
Aliquot Sequences (Amicable Pairs, and Sociable Numbers)
- Additional Examples of Calculating Aliquot Sequences

The Chinese Remainder Theorem (and Systems of Linear Congruences)
- Additional Examples of Solving Systems of Linear Congruences

* Examples of Finding Remainders using Wilson's Theorem

Jacobi Symbols
Examples of Computing Jacobi Symbols

Binary Quadratic Forms

Binary Quadratic Forms
The Discriminant of a Binary Quadratic Form
Indefinite, Semidefinite, and Definite Binary Quadratic Forms
IFF Criterion for a Binary Quadratic Form to Have a Discriminant d

Sums of Two Squares

A Product of a Sum of Two Squares is a Sum of Two Squares
Expressing Integers as a Sum of Two Squares
Examples of Expressing Integers as a Sum of Two Squares

Equivalence and Reduction of Binary Quadratic Forms

Proper Representation Criterion for Binary Quadratic Forms
Equivalent Binary Quadratic Forms
Example Problems Regarding Equivalent Binary Quadratic Forms
The Class Number H(d) of a Discriminant d
Reduced Binary Quadratic Forms
Reducing Binary Quadratic Forms
Examples of Reducing Binary Quadratic Forms 1
Examples of Reducing Binary Quadratic Forms 2
Computing the Class Number H(-3)
Computing the Class Number H(-11)
Computing the Class Number H(-39)
Expressing Integers Properly as a Sum of Two Squares
The Functions R(n), r(n), P(n), and N(n)
A Formula for P(n) = N(n)

Arithmetic Functions

Arithmetic Functions (Additive and Multiplicative)
The Dirichlet Convolution of Two Arithmetic Functions
Examples of Dirichlet Convolutions of Two Arithmetic Functions
The Möbius Function
The Dirichlet Convolution μ * 1 = ꙇ
The Möbius Inversion Formula

Dirichlet's Approximation of Real Numbers by Rational Numbers

Farey Sequences
Theorems Regarding Farey Sequences
Dirichlet's Approximation Theorem
Dirichlet's Approximation Theorem by Farey Sequences

Irrational Number Approximation

Irrational Number Approximation by Rational Numbers
Hurwitz's Theorem
An Example of a Series Converging to an Irrational Numbers

Algebraic Number Approximation

Algebraic and Transcendental Numbers
Algebraic Number Approximation
An Example of a Series Converging to a Transcendental Number

Irrational Numbers

The Rational Roots Theorem
Rational and Irrational Values of cosθ, sinθ, and tanθ
Proof that e is Irrational
Proof that Pi is Irrational

Minkowski's Convex Body Theorem

Blichfeldt's Principle
Lattices in Rn
Minkowski's Convex Body Theorem
Proof that if p ≡ 1 (mod 4) then p is the Sum of 2 Squares by Minkowski's Convex Body Theorem
Lagrange's Four Square Theorem

Continued Fractions

Continued Fractions
Finite Continued Fractions and Rational Numbers
The Sequences (hn) and (kn)
The nth Convergent of an Infinite Continued Fraction
Convergence of Infinite Continued Fractions
Infinite Continued Fractions and Irrational Numbers
Examples of Computing Infinite Continued Fractions
Irrational Number Approximation by Infinite Continued Fractions
Criterion for a/b to be a Convergent of an Infinite Continued Fraction
Periodic and Purely Periodic Continued Fractions
IFF Criterion for an Irrational Number to be Periodic
Periodic Continued Fractions are Quadratic Irrationals
Quadratic Irrationals Have Periodic Continued Fractions
IFF Criterion for an Irrational Number to be Purely Periodic
Pell's Equation
Solutions to x^2 - dy^2 = 1 and x^2 - dy^2 = -1
Solutions to x^2 - dy^2 = N

The Prime Counting Function
The von-Mangoldt Function
The Chebyshev Functions
Dirichlet Series
The Riemann Zeta Function
The Euler Product of a Dirichlet Series
The Dirichlet Series for the von-Mangoldt Function

References

1. Underwood Dudley, "Elementary Number Theory Second Edition".