# 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
- 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 \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
- The Number of Primitive Roots of a Natural Number
- Determining the Primitive Roots of a Natural Number

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

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

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

- Quadratic Congruences $x^2 \equiv a \pmod p$
- Euler's Criterion If p is an odd prime and $p \nmid a$, then $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ or $a^{\frac{p-1}{2}} \equiv -1 \pmod p$.
- Legendre Symbols $(a/p) = \pm 1$
- Gauss's Lemma $(a/p) = (-1)^g$
- 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 \equiv q \equiv 3 \pmod 4$, otherwise $(p/q) = (q/p)$
- Pythagorean Triangles $x^2 + y^2 = z^2$ for $x, y, z \in \mathbb{Z}$.

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 \equiv b \pmod m$.
- Divisibility Tests
- Last Digits of Large Numbers
- Linear Congruences $ax \equiv b \pmod m$.

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

- The Number of Positive Divisors of an Integer n, d(n) $d(n) = \sum_{d \mid n} 1$
- The Sum of Positive Divisors of an Integer n, σ(n) $\sigma(n) = \sum_{d \mid n} d$
- Additional Examples of Calculating σ(n) for Large Integers $\sigma (p^n) = \frac{p^{n + 1} - 1}{p - 1}$.

- Euler's Theorem and Euler's Totient Function (Euler's Φ-Function) If (a, m) = 1, then $a^{\phi (m)} \equiv 1 \pmod m$.
- Calculating Φ for Large Positive Integers $\phi (p^n) = p^{n-1}(p - 1)$.

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

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

* Examples of Finding Remainders using Wilson's Theorem

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

### References

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