Featured Image
Guide to master the concepts of Number Theory
#cp #programming #numbertheory

Master Number Theory

A Powerful tool for competitive programmers


Number Theory is a branch of Mathematics which deals with the properties and relationships of Positive Numbers and arithmetic operations based on them. Used for counting, numbers have captivated mathematicians throught the history. By mastering key concepts in the number theory, you will gain a significant edge in tackling the problems involving divisibility, primality, modular arithmetic and more.

Fundamental concepts of Number Theory

The Peano Axioms

  1. 0 ∈ N ; 0 is a natural number
  2. If x ∈ N ⇒ S(x) ∈ N - Every natural number has a successor, which is also a natural number.
  3. If n ∈ N ; S(n) ≠ 0 - If n ∈ N, then the successor of n cannot be 0.
  4. ∀ a, b ∈ N; if S(a) = S(b) ⇒ a = b - Different Natural numbers have different successors.
  5. If 0 belongs to set V and V contains the successor of every number in S then, S contains every natural number. This axiom is popularlu known as ‘Principle of Induction

GCD and LCM

Greatest Common Divisor (GCD)

GCD of two or more numbers is defined as the largest positive integer that divides them, exactly.

ways to find gcd of two numbers
  • Prime Factorization
  • Divisions By prime
  • Euclidean Algorithm

    • Least Common Factor (LCM)

    LCM of two or more numbers is defined as the smallest positive integer that is divisible by each of the numbers.

    ways to find gcd of two numbers
  • Prime Factorization
  • Divisions By prime
  • Using the relation between GCD and LCM
    • GCD and LCM are related by a very simple equation: LCM(a,b) GCD(a,b) = ab. This gives a very fast way to calculate LCM of two numbers

    Prime Numbers

    A prime number is definde as a natural number greater than one that has no positive divisors other than 1 and itself. Prime Numbers are central to number theory because of the funcamental theorem of Arithmetic which states that 1 is either prime itself or can be factorized as product of primes. Some of the prime numbers include 2,3,5,7,11,13,…..etc.

    Prime Factors

    A Prime Factor of a number is a factor of the number that is only divisible by 1 and itself. Example : The Prime factors of 15 and 3 are 5 ( because 3*5 =15 and 2 and 5 are prime numbers)

    Modular Arithmetic

    Modular Arithmetic deals with remainders after division. We write a ≡ b (mod n) to signify that a and b leave the same remainder when divided by n (the modulus).

    Modular Addition

    (a + b) mod m = ((a mod m) + (b mod m)) mod m

    Modular Multiplication

    (a x b) mod m = ((a mod m) x (b mod m)) mod m

    Modular Division

    (a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.

    Modular Exponentiation (Fast Exponentiation)

    Efficiently compute large powers under modulo
    abmod m

    Modular Inverse

    The modular inverse of a mod m exists only if a and m are relatively prime i.e. gcd(a, m) = 1.

    Integer Factorization

    Integer Factorization, also known as prime factorization, is the process of breaking down a positive integer into a product of integers. The most commonly used algorithm for the integer factorization is Sieve of Eratosthenes. It is the efficient way of to calculate the prime factorization of a number 'n'. For every integer x between 1 and n, we can maintain a single prime that divides k and ist highest power.

    Euclidean Algorithm

    The Euclidean algorithm can be used to find the greatest common divisor of two positive integers. GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common prime factors.

    Basic Euclidean Algorithm to find GCD
    • GCD of two numbers doesn't change even if we subtract smaller number from the larger number. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
    • Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find the remainder 0.

    Chinese Remainder Theorem

    The Chinese remainder Theorem (CRT) is used to solve a set of different congruent equations with one variable but different moduli which are relatively prime as shown below.
    x = a1 mod m1
    x = a2 mod m2
    ...
    x = an mod mn
    Where all pairs of m1, m2, ..., mn are coprimes.
    CRT states that the above equations have a unique solution of the moduli are relatively prime.
    x = (a1M1M1-1 + a2M2M2-1 + ... + anMnMn-1)mod M

    Practice Makes Perfect

    The key to master number theory lies in consistent practice. Here are some resourses to help you hone your skills.

    By investing time and effort into learning number theory, you will equip yourself with a powerful arsenal of techniques to tackle wide range of problems in competitive programming.

    Recommended

    Comments

    Load Comments