Number Theory

Number theory, as the name suggests, is the study of the properties and relationships of integers and has a long history dating back to the very inception of mathematics. Gauss famously said about number theory:

“Mathematics is the queen of sciences, and number theory is the queen of mathematics.”

Elementary Number Theory

The term “elementary” in this context contrasts with analytic or algebraic number theory and does not imply simplicity at the level of elementary school. While understanding the propositions may be relatively straightforward, the field itself is not inherently simple. Many mathematically talented individuals are introduced to number theory from a young age.

Multiples and Divisors

• Greatest Common Divisor and Coprime $\gcd$
  • Definition of Even Numbers
• Quotient and Remainder
  • Euclidean Algorithm
• Extended Euclidean Theorem
• Divisibility Rules for 3 and 9
• Divisibility Rules for 7 and 13
• Divisibility Rule for 11

Primes

• Primes and Composite Numbers
  • List of Primes up to the 10,000th
  • Prime Factorization Principle
  • Fundamental Theorem of Arithmetic
  • Euclid’s Proof: There are Infinitely Many Primes
  • Euler’s Proof: There are Infinitely Many Primes
• Mersenne Primes
• Smooth Numbers
• Almost Primes

Modular Arithmetic

• Congruence in Number Theory
• Fundamental Theorem of Algebra for Modular Equations
• Fermat’s Little Theorem
  • Carmichael Numbers
  • Coset Enumeration
  • Miller-Rabin Primality Test
• Wilson’s Theorem
• Chinese Remainder Theorem
• Method of Successive Squaring
• Order in Number Theory
  • Primitive Root Theorem
  • $p$-adic Numbers
  • Lifting the Exponent Lemma

Perfect Numbers

• Euler’s Totient Function $\phi$
  • Multiplicative Property of Euler’s Totient Function
  • Euler’s Totient Theorem
  • Sum of Euler’s Totient Function
• Roots of Congruence Equations
• Sigma Function in Number Theory $\sigma$
• Euclid’s Perfect Number Formula
• Euler’s Perfect Number Theorem

Quadratic Reciprocity

• Quadratic Residues and Non-Residues QR, NR
• Multiplicative Property of the Legendre Symbol
• Euler’s Criterion
• Gauss’s Law of Quadratic Reciprocity
• Necessary and Sufficient Condition for a Prime to Leave a Remainder of 1 When Divided by 4
• Necessary and Sufficient Condition for a Prime to Leave a Remainder of 1 When Divided by 3

Elliptic Curves

• Pythagorean Triples
  • One of the Pythagorean Numbers Must be Even
  • One of the Pythagorean Numbers Must be a Multiple of 3
  • Primitive Pythagorean Triples Can Be Expressed by Two Odd Numbers
  • Primitive Pythagorean Numbers are Coprime
• Pell’s Equation

Cryptography

Initially, cryptography was a prominent application of number theory. For thousands of years, number theory, once purely a branch of pure mathematics, transformed into a practical field through applications in cryptography, and recently, abstract algebra has been applied.

• Encryption and Decryption

Discrete Logarithms

• Discrete Logarithms
• Diffie-Hellman Key Exchange Algorithm
• ElGamal Public Key Cryptosystem
• Shanks’ Algorithm
• Pohlig-Hellman Algorithm
• Conditions Under Which the Discrete Logarithm Problem Is Easily Solvable

Factorization

• Prime Factorization
• RSA Public Key Cryptosystem
• Goldwasser-Micali Probabilistic Key Cryptosystem
• Pollard’s $p-1$ Factorization Algorithm
• Conditions Under Which Factorization of Semiprimes Is Easily Solvable

Algebraic Number Theory

Extended Rings

• Gaussian Integers $\mathbb{Z} [i]$
• Norm of Gaussian Rings
• Gaussian Prime Theorem
• Eisenstein Integers $\mathbb{Z} [\omega]$
• Norm of Eisenstein Rings
• Eisenstein Prime Theorem

Analytic Number Theory

Arithmetic Functions

• Arithmetic Function $f$
  • Möbius Function $\mu$
  • Euler’s Totient Function $\varphi$
  • Norm $N$
  • Unit Function $u$
  • Mangoldt Function $\Lambda$
  • Liouville Function $\lambda$
  • Divisor Function $\sigma_{\alpha}$
• Multiplicative Property of Arithmetic Functions
• Dirichlet Convolution $\ast$
  • Identity $I$ for Dirichlet Convolution
  • Inverse $f^{-1}$ for Dirichlet Convolution
  • Multiplicative Property and Dirichlet Convolution
  • Abelian Group of Arithmetic Functions $\left( A, \ast \right)$
  • Abelian Group of Multiplicative Functions $\left( M, \ast \right)$
• Möbius Inversion Formula
• Bell Series $f_{p}(x)$
• Derivative of Arithmetic Functions $f ‘$
• Selberg Identity
• Generalized Dirichlet Convolution $\circ$
  • Generalized Dirichlet Convolution Representation for Partial Sums of Arithmetic Functions

References

• Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition)
• Apostol. (1976). Introduction to Analytic Number Theory
• Hoffstein. (2008). An Introduction to Mathematical Cryptography