Number Theory

Number theory is a branch of pure mathematics devoted primarily to the study of integers and integer-valued functions.

Basic Concepts

Number theory involves several fundamental concepts:

  1. Divisibility: One integer a is divisible by another integer b if there exists an integer c such that a = b*c.

  2. Prime Numbers: A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

  3. Greatest Common Divisor (GCD): The GCD of two or more integers is the largest positive integer that divides each of the integers without a remainder.

  4. Least Common Multiple (LCM): The LCM of two integers a and b is the smallest positive integer that is divisible by both a and b.

Fundamental Theorems

Number theory includes several fundamental theorems:

  1. Fundamental Theorem of Arithmetic: Every integer greater than 1 either is a prime number itself or can be represented as a product of prime numbers and that, moreover, this representation is unique, up to the order of the factors.

  2. Chinese Remainder Theorem: If one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under certain conditions.

  3. Fermat's Little Theorem: If p is a prime number, then for any integer a, the number a^p – a is an integer multiple of p.

  4. Euler's Totient Theorem: If n and a are coprime positive integers, then a to the power of φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.

Number theory has numerous applications in computer science, particularly in cryptography and algorithm design. It also has many connections with other branches of mathematics, particularly geometry and complex analysis.