Podcast Beta
Questions and Answers
The property of prime numbers that states every positive integer can be expressed as a product of prime numbers in a unique way is known as _______________ factorization.
unique
The _______________ theorem is a result in number theory that describes the solution of linear congruences modulo n, where n is a product of pairwise coprime integers.
Chinese Remainder
In combinatorics, the formula for the number of permutations of n items taken r at a time is given by _______________.
nPr
The _______________ principle is a method used in combinatorics to count the number of elements in a union of sets by subtracting the number of elements in the intersection of the sets.
Signup and view all the answers
In graph theory, a graph is said to be _______________ if it is possible to traverse the graph from any vertex to any other vertex.
Signup and view all the answers
The _______________ search algorithm is a graph traversal algorithm that visits all the vertices reachable from a given vertex in a breadthward motion.
Signup and view all the answers
In probability, the _______________ rule is used to find the probability of two or more events occurring.
Signup and view all the answers
A random variable that can take on only a countable number of distinct values is called a _______________ random variable.
Signup and view all the answers
The probability of an event occurring given that another event has occurred is known as the _______________ probability.
Signup and view all the answers
The _______________ theorem is a result in probability that describes the probability of an event given new information.
Signup and view all the answers
Study Notes
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, MillerRabin)

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

InclusionExclusion 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:
 Breadthfirst search (BFS) and depthfirst 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 inclusionexclusion 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
 MillerRabin 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! / (nr)!
 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!(nr)!)
 The number of combinations of n objects, taken r at a time, with repetition, is (n+r1)! / (r!(n1)!)

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

InclusionExclusion Principle
 The InclusionExclusion 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
 Breadthfirst search (BFS) is a traversal method that explores all vertices at a given depth before moving to the next level
 Depthfirst 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 inclusionexclusion 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
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
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.