Divisibility and factorization

Concepts

• Greatest common divisor from Discrete mathematics 10 exercisesThe greatest common divisor gcd(a,b) of two integers a and b, not both zero, is the largest integer that divides both.
• Euclidean algorithm from Discrete mathematics 10 exercisesThe Euclidean algorithm computes the greatest common divisor of two integers a and b by dividing repeatedly, replacing each pair…
• Prime number from Discrete mathematics 10 exercisesA prime number p is an integer greater than 1 whose only positive divisors are 1 and itself.
• Bézout's identity 10 exercisesBézout's identity states that, for integers a and b not both zero, there exist integers x and y such that ax+by=gcd(a,b) .
• Extended Euclidean algorithm 10 exercisesThe extended Euclidean algorithm computes d=gcd(a,b) and integers x, y such that ax+by=d. It is the Euclidean algorithm that also…
• Euclid's lemma 10 exercisesIf a prime p divides the product ab, then p divides a or b. It is the key property that distinguishes primes from composite numbe…
• Fundamental theorem of arithmetic 10 exercisesEvery integer greater than 1 can be written uniquely as a product of primes, up to the order of the factors. It is the foundation…
• Least common multiple 10 exercisesThe least common multiple of two integers a and b is the smallest positive integer that is a multiple of both, denoted lcm(a,b) .
• Infinitude of primes 10 exercisesThe infinitude of primes is Euclid's theorem stating that the set of prime numbers is infinite: given any finite list of primes p…
• Linear Diophantine equation 10 exercisesA linear Diophantine equation is ax+by=c with integer coefficients, where we seek integer pairs x,y as solutions.