Number Theory Basics

Number Theory

Divisibility

• A positive integer a is said to divide another integer b (written as a | b) if there exists an integer k such that b = ka
• Properties of divisibility:
  • If a | b and a | c, then a | (b + c)
  • If a | b and b | c, then a | c

Prime Numbers

• A prime number is a positive integer that is divisible only by itself and 1
• Properties of prime numbers:
  • There are an infinite number of prime numbers
  • Every positive integer can be expressed as a product of prime numbers in a unique way (Fundamental Theorem of Arithmetic)
  • Prime numbers are greater than 1

Greatest Common Divisor (GCD)

• The GCD of two or more integers is the largest integer that divides each of them without leaving a remainder
• Methods for finding GCD:
  • Prime factorization
  • Euclidean algorithm

Congruences

• Two integers a and b are said to be congruent modulo n (written as a ≡ b (mod n)) if they leave the same remainder when divided by n
• Properties of congruences:
  • If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n)
  • If a ≡ b (mod n), then a ≡ b + kn (mod n) for any integer k

Diophantine Equations

• A Diophantine equation is a polynomial equation in two or more variables with integer coefficients, for which only integer solutions are sought
• Linear Diophantine equations:
  • ax + by = c, where a, b, and c are integers and x and y are variables
  • Solutions exist if and only if c is a multiple of the GCD of a and b

Fermat's Little Theorem

• If p is a prime number, then a^p ≡ a (mod p) for any integer a
• Applications:
  • Testing for primality
  • Cryptography

Divisibility

• A positive integer a divides another integer b if there exists an integer k such that b = ka.
• Key properties include:
  • If a divides both b and c, then it also divides their sum: a | (b + c).
  • If a divides b and b divides c, then a divides c: a | c.

Prime Numbers

• A prime number is defined as a positive integer greater than 1 that is only divisible by itself and 1.
• Notable properties of primes:
  • There are infinitely many prime numbers.
  • Every positive integer greater than 1 can be expressed uniquely as a product of prime numbers, known as the Fundamental Theorem of Arithmetic.

Greatest Common Divisor (GCD)

• The GCD of two or more integers is the largest integer that can divide each without leaving a remainder.
• Common methods to determine the GCD include:
  • Prime factorization, which involves expressing each number as a product of primes.
  • The Euclidean algorithm, based on repeated division.

Congruences

• Two integers a and b are congruent modulo n if they yield the same remainder when divided by n, denoted as a ≡ b (mod n).
• Congruences follow certain properties:
  • If a ≡ b (mod n) and c ≡ d (mod n), then their sums are also congruent: a + c ≡ b + d (mod n).
  • If a ≡ b (mod n), then for any integer k, a remains congruent to b + kn (mod n).

Diophantine Equations

• A Diophantine equation consists of polynomial equations with integer coefficients, specifically seeking integer solutions.
• For linear Diophantine equations of the form ax + by = c, solutions exist if and only if c is a multiple of the GCD of a and b.

Fermat's Little Theorem

• When p is a prime number, for any integer a, the relationship a^p ≡ a (mod p) holds.
• This theorem has practical applications in:
  • Primality testing, offering a way to determine if a number is prime.
  • Cryptography, particularly in algorithms that rely on number theory.