Key Number Theory Concepts to Know for Discrete Mathematics

Number theory concepts are essential in discrete mathematics, focusing on integers and their properties. Key ideas include divisibility, prime factorization, and algorithms for finding greatest common divisors, which all play a crucial role in various applications like cryptography and problem-solving.

1. Divisibility and division algorithm

   • A number ( a ) is divisible by ( b ) if there exists an integer ( k ) such that ( a = b \cdot k ).
   • The division algorithm states that for any integers ( a ) and ( b ) (with ( b > 0 )), there exist unique integers ( q ) (quotient) and ( r ) (remainder) such that ( a = bq + r ) where ( 0 \leq r < b ).
   • Divisibility rules can simplify checking if one number divides another without performing full division.

2. Prime numbers and prime factorization

   • A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
   • Every integer greater than 1 can be expressed uniquely as a product of prime numbers, known as its prime factorization.
   • The Fundamental Theorem of Arithmetic states that the prime factorization of a number is unique, up to the order of the factors.

3. Greatest common divisor (GCD) and Euclidean algorithm

   • The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder.
   • The Euclidean algorithm is an efficient method for computing the GCD by repeatedly applying the division algorithm.
   • The GCD can be used to simplify fractions and solve problems involving divisibility.

4. Least common multiple (LCM)

   • The LCM of two integers is the smallest positive integer that is divisible by both numbers.
   • The relationship between GCD and LCM is given by the formula: ( \text{LCM}(a, b) = \frac{|a \cdot b|}{\text{GCD}(a, b)} ).
   • LCM is useful in problems involving synchronization of cycles, such as finding common time intervals.

5. Modular arithmetic

   • Modular arithmetic deals with integers and their remainders when divided by a fixed integer, called the modulus.
   • The notation ( a \equiv b \mod m ) means that ( a ) and ( b ) have the same remainder when divided by ( m ).
   • It is widely used in computer science, cryptography, and number theory for simplifying calculations.

6. Congruences and their properties

   • Congruences are equations that express the equivalence of two numbers modulo a third number.
   • Key properties include reflexivity, symmetry, and transitivity, which allow manipulation of congruences similar to equations.
   • If ( a \equiv b \mod m ), then ( a + c \equiv b + c \mod m ) and ( a \cdot c \equiv b \cdot c \mod m ) for any integer ( c ).

7. Chinese Remainder Theorem

   • The Chinese Remainder Theorem provides a way to solve systems of simultaneous congruences with coprime moduli.
   • It guarantees a unique solution modulo the product of the moduli.
   • This theorem is useful in number theory and computer algorithms for simplifying complex modular equations.

8. Fermat's Little Theorem

   • Fermat's Little Theorem states that if ( p ) is a prime and ( a ) is an integer not divisible by ( p ), then ( a^{p-1} \equiv 1 \mod p ).
   • This theorem is foundational in number theory and has applications in cryptography, particularly in primality testing.
   • It helps in reducing large exponentiations in modular arithmetic.

9. Euler's Theorem and Euler's totient function

   • Euler's Theorem generalizes Fermat's Little Theorem: if ( a ) and ( n ) are coprime, then ( a^{\phi(n)} \equiv 1 \mod n ), where ( \phi(n) ) is Euler's totient function.
   • The totient function counts the number of integers up to ( n ) that are coprime to ( n ).
   • Euler's Theorem is crucial in public key cryptography and modular exponentiation.

10. Linear Diophantine equations

    • A linear Diophantine equation is an equation of the form ( ax + by = c ) where ( a, b, c ) are integers and ( x, y ) are unknowns.
    • A solution exists if and only if the GCD of ( a ) and ( b ) divides ( c ).
    • The general solution can be expressed in terms of a particular solution and the GCD, allowing for infinite solutions based on integer parameters.