Number Theory Fundamentals

Divisibility

• A divisor of a number is an integer that divides it without leaving a remainder.
• Notation: a | b means "a divides b" or "a is a divisor of b".
• Properties:
  • If a | b and a | c, then a | (b + c).
  • If a | b and a | c, then a | (b - c).
  • If a | b and c | a, then c | b.

Prime Numbers

• A prime number is a positive integer greater than 1 that is divisible only by 1 and itself.
• Examples: 2, 3, 5, 7, 11, ...
• Properties:
  • There are infinitely many prime numbers.
  • Every positive integer can be expressed as a product of prime numbers in a unique way ( Fundamental Theorem of Arithmetic).

Greatest Common Divisor (GCD)

• The GCD of two or more integers is the largest integer that divides each of them without leaving a remainder.
• Notation: gcd(a, b) or (a, b).
• Properties:
  • gcd(a, b) = gcd(b, a).
  • gcd(a, b) = gcd(a, b + a).
  • gcd(a, b) = gcd(a, b - a).

Euclidean Algorithm

• A method for computing the GCD of two integers.
• Steps:
  1. Divide the larger number by the smaller number.
  2. Take the remainder as the new smaller number.
  3. Repeat steps 1 and 2 until the remainder is 0.
  4. The last non-zero remainder is the GCD.

Congruences

• A congruence is an equation of the form a ≡ b (mod n), where a, b, and n are integers.
• Meaning: a and b have the same remainder when divided by n.
• Properties:
  • a ≡ a (mod n).
  • If a ≡ b (mod n), then b ≡ a (mod n).
  • If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

Diophantine Equations

• A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers.
• Solution: x = x0 + (b/d)t, y = y0 - (a/d)t, where d = gcd(a, b) and x0, y0 are particular solutions.

Fermat's Little Theorem

• If p is a prime number, then a^p ≡ a (mod p) for any integer a.
• Corollary: If p is a prime number, then a^(p-1) ≡ 1 (mod p) for any integer a not divisible by p.

Divisibility

• A divisor is an integer that divides another integer without leaving a remainder.
• Notation: a | b means "a divides b" or "a is a divisor of b".
• Properties of divisibility:
  • If a divides b and a divides c, then a divides b + c.
  • If a divides b and a divides c, then a divides b - c.
  • If a divides b and c divides a, then c divides b.

Prime Numbers

• A prime number is a positive integer greater than 1 that is divisible only by 1 and itself.
• Examples: 2, 3, 5, 7, 11, ...
• Properties of prime numbers:
  • There are infinitely many prime numbers.
  • Every positive integer can be expressed as a product of prime numbers in a unique way (Fundamental Theorem of Arithmetic).

Greatest Common Divisor (GCD)

• The GCD of two or more integers is the largest integer that divides each of them without leaving a remainder.
• Notation: gcd(a, b) or (a, b).
• Properties of GCD:
  • gcd(a, b) = gcd(b, a).
  • gcd(a, b) = gcd(a, b + a).
  • gcd(a, b) = gcd(a, b - a).

Euclidean Algorithm

• A method for computing the GCD of two integers using repeated divisions.
• Steps:
  • Divide the larger number by the smaller number.
  • Take the remainder as the new smaller number.
  • Repeat steps until the remainder is 0.
  • The last non-zero remainder is the GCD.

Congruences

• A congruence is an equation of the form a ≡ b (mod n), where a, b, and n are integers.
• Meaning: a and b have the same remainder when divided by n.
• Properties of congruences:
  • a ≡ a (mod n).
  • If a ≡ b (mod n), then b ≡ a (mod n).
  • If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

Diophantine Equations

• A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers.
• Solution: x = x0 + (b/d)t, y = y0 - (a/d)t, where d = gcd(a, b) and x0, y0 are particular solutions.

Fermat's Little Theorem

• If p is a prime number, then a^p ≡ a (mod p) for any integer a.
• Corollary: If p is a prime number, then a^(p-1) ≡ 1 (mod p) for any integer a not divisible by p.