Number Theory Basics

Number Theory

• Divisibility:
  • Divisibility rules for 2, 3, 4, 5, 6, 8, 9, and 10
  • Greatest common divisor (GCD) and least common multiple (LCM)
• Prime Numbers:
  • Definition and properties (e.g., unique factorization)
  • Tests for primality (e.g., trial division, Miller-Rabin)
• Congruences:
  • Definition and properties (e.g., modular arithmetic)
  • Linear congruences and the Chinese Remainder Theorem
• Diophantine Equations:
  • Linear and quadratic equations in multiple variables
  • Pell's equation and its applications

Combinatorics

• Permutations:
  • Definitions and notation (e.g., nPr, nCr)
  • Formulae for permutations with and without repetition
• Combinations:
  • Definitions and notation (e.g., nCr)
  • Formulae for combinations with and without repetition
• Recurrence Relations:
  • Definition and examples (e.g., Fibonacci sequence)
  • Solving recurrence relations using generating functions
• Inclusion-Exclusion Principle:
  • Statement and examples of the principle
  • Applications to counting and probability

Graph Theory

• Basic Concepts:
  • Definitions: graph, vertex, edge, adjacency, and incidence
  • Types of graphs (e.g., simple, weighted, directed)
• Graph Representations:
  • Adjacency matrix and adjacency list
  • Incidence matrix and incidence list
• Graph Traversal:
  • Breadth-first search (BFS) and depth-first search (DFS)
  • Topological sorting and strongly connected components
• Graph Connectivity:
  • Definition and examples of connected and disconnected graphs
  • Connectivity measures (e.g., vertex connectivity, edge connectivity)

Probability

• Basic Concepts:
  • Event, sample space, and probability measure
  • Types of events (e.g., mutually exclusive, independent)
• Probability Rules:
  • Addition rule and inclusion-exclusion principle
  • Multiplication rule and conditional probability
• Random Variables:
  • Discrete and continuous random variables
  • Probability distributions (e.g., Bernoulli, binomial, normal)
• Conditional Probability and Independence:
  • Conditional probability and Bayes' theorem
  • Independence of events and random variables

Number Theory

• Divisibility
  • A number is divisible by 2 if its last digit is even
  • A number is divisible by 3 if the sum of its digits is divisible by 3
  • A number is divisible by 4 if its last two digits form a number divisible by 4
  • A number is divisible by 5 if its last digit is 0 or 5
  • A number is divisible by 6 if it is divisible by 2 and 3
  • A number is divisible by 8 if its last three digits form a number divisible by 8
  • A number is divisible by 9 if the sum of its digits is divisible by 9
  • A number is divisible by 10 if its last digit is 0
  • The greatest common divisor (GCD) of two numbers is the largest number that divides both numbers without a remainder
  • The least common multiple (LCM) of two numbers is the smallest number that is a multiple of both numbers
• Prime Numbers
  • A prime number is a positive integer greater than 1 that is divisible only by itself and 1
  • Every positive integer can be expressed as a product of prime numbers in a unique way
  • Trial division is a method to test if a number is prime by dividing it by all prime numbers up to its square root
  • Miller-Rabin is a probabilistic primality test
• Congruences
  • Congruence modulo n is an equivalence relation on the set of integers
  • Congruence classes modulo n are subsets of integers that leave the same remainder when divided by n
  • Modular arithmetic is a system of arithmetic where numbers "wrap around" after reaching a certain value (modulus)
  • Linear congruences are equations of the form ax ≡ b (mod n) and can be solved using the extended Euclidean algorithm
  • The Chinese Remainder Theorem states that a system of congruences has a unique solution modulo the least common multiple of the moduli
• Diophantine Equations
  • A Diophantine equation is a polynomial equation in two or more variables with integer coefficients
  • Linear Diophantine equations can be solved using the extended Euclidean algorithm
  • Pell's equation is a Diophantine equation of the form x² - ny² = 1, where n is a positive integer
  • Pell's equation has an infinite number of solutions and can be solved using continued fractions

Combinatorics

• Permutations
  • A permutation is an arrangement of objects in a specific order
  • The number of permutations of n objects is n!
  • The number of permutations of n objects, taken r at a time, is nPr = n! / (n-r)!
  • The number of permutations of n objects, taken r at a time, with repetition, is nr
• Combinations
  • A combination is a selection of objects without regard to order
  • The number of combinations of n objects, taken r at a time, is nCr = n! / (r!(n-r)!)
  • The number of combinations of n objects, taken r at a time, with repetition, is (n+r-1)! / (r!(n-1)!)
• Recurrence Relations
  • A recurrence relation is an equation that defines a sequence recursively
  • The Fibonacci sequence is a classic example of a recurrence relation
  • Generating functions can be used to solve recurrence relations
• Inclusion-Exclusion Principle
  • The Inclusion-Exclusion Principle is a formula for counting the number of elements in a union of sets
  • The principle states that the number of elements in a union of sets is the sum of the sizes of each set minus the sum of the sizes of the intersections of each pair of sets

Graph Theory

• Basic Concepts
  • A graph is a collection of vertices connected by edges
  • A simple graph has no multiple edges between any two vertices
  • A weighted graph has edges with weights or labels
  • A directed graph has edges with direction
• Graph Representations
  • An adjacency matrix is a matrix where entry [i,j] represents the number of edges between vertices i and j
  • An adjacency list is a list of edges, where each edge is represented by a pair of vertices
  • An incidence matrix is a matrix where entry [i,j] represents the number of edges incident on vertex i
  • An incidence list is a list of edges, where each edge is represented by a pair of vertices and the vertices it is incident on
• Graph Traversal
  • Breadth-first search (BFS) is a traversal method that explores all vertices at a given depth before moving to the next level
  • Depth-first search (DFS) is a traversal method that explores as far as possible along each branch before backtracking
  • Topological sorting is a linear ordering of vertices in a directed acyclic graph
  • Strongly connected components are subgraphs that have a path from every vertex to every other vertex
• Graph Connectivity
  • A connected graph is a graph where there is a path between every pair of vertices
  • A disconnected graph is a graph where there is no path between every pair of vertices
  • The vertex connectivity of a graph is the minimum number of vertices that must be removed to disconnect the graph
  • The edge connectivity of a graph is the minimum number of edges that must be removed to disconnect the graph

Probability

• Basic Concepts
  • An event is a set of outcomes of an experiment
  • A sample space is the set of all possible outcomes of an experiment
  • A probability measure is a function that assigns a number between 0 and 1 to each event
  • Independent events are events where the occurrence of one does not affect the probability of the other
• Probability Rules
  • The addition rule states that the probability of the union of two events is the sum of their probabilities
  • The inclusion-exclusion principle is a formula for counting the number of elements in a union of sets
  • The multiplication rule states that the probability of the intersection of two independent events is the product of their probabilities
• Random Variables
  • A discrete random variable is a random variable that takes on a countable number of distinct values
  • A continuous random variable is a random variable that takes on a continuous range of values
  • A Bernoulli distribution is a discrete distribution that models the probability of success in a single trial
  • A binomial distribution is a discrete distribution that models the probability of k successes in n trials
  • A normal distribution is a continuous distribution that models the probability of a continuous variable
• Conditional Probability and Independence
  • Conditional probability is the probability of an event given that another event has occurred
  • Bayes' theorem states that the conditional probability of an event given another event is the probability of the two events multiplied by the probability of the given event
  • Independent events are events where the occurrence of one does not affect the probability of the other

Test your knowledge of number theory fundamentals, including divisibility, prime numbers, congruences, and Diophantine equations. Topics covered include rules for divisibility, properties of prime numbers, modular arithmetic, and more.