# Number Theory Topics

Important Notice: The Number Theory section is one of the first sections ever to be developed on Math Online and unfortunately is not up to par with the quality that the rest of the site provides. Regardless, most of the material posted is still readable but be on the look out for many mistakes. The pages in this hub will slowly be reviewed and edited for quality. |

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

## 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
- Example Problems Regarding 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 \pmod {n}$
- Examples of Decrypting with RSA $P \equiv C^d \pmod {n}$

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

## 3. The d, σ, and ϕ Functions

###### 3.1. The d Function

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

## 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
- Determining the Number of Primitive Roots a Prime Has
- Determining if r is a Primitive Root of n
- Finding Other Primitive Roots (mod p)

###### 4.2. Quadratic Congruences

###### 4.3. Legendre Symbols

- Legendre Symbols
- 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

###### 4.4. Jacobi Symbols

###### 4.5. Pythagorean Triangles

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

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

## 7. Approximation and Pell's Equation

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

###### 7.7. Pell's Equation

## 8. The Prime Number Theorem

###### 8.1. Dirichlet Series

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 possible errors that can be overlooked. |

###### References

- 1. Elementary Number Theory (2nd Edition) by Underwood Dudley.

- 2. An Introduction to the Theory of Numbers (5th Edition) by Ivan Niven.