# 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

- Integer Division
- Greatest Common Divisor
- The Division Algorithm for Positive Integers
- The Euclidean Algorithm
- Primes Numbers
- Composite Numbers
- Unique Factorization
- Prime Power Decomposition
- Example Questions Regarding Primes and Composites
- Linear Diophantine Equations
- Solutions to Linear Diophantine Equations

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

- 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

- 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

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

- The Number of Positive Divisors of an Integer ( Examples 1 | Examples 2 )
- 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 )
- Euler's Totient Function ( Examples 1 | Examples 2 )
- Euler's Totient Function on Odd and Even Natural Numbers
- Euler's Totient Theorem

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

## 5. Order, Primitive Roots, and Quadratic Congruences

- 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

- The Order of a (mod m)
- Primitive Roots
- 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

### References

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