greatest common divisor
Definition
Noun: The largest positive integer that is a divisor of two or more given integers without leaving a remainder. It is the greatest number that can exactly divide all numbers in a given set.
Usage
The term "greatest common divisor" is used in mathematics, specifically in number theory and arithmetic. It is a fundamental concept for simplifying fractions, solving Diophantine equations, and understanding the divisibility properties of integers. - It is often abbreviated as GCD. - For two integers a and b, their greatest common divisor is commonly denoted as gcd(a, b).
Examples
- The greatest common divisor of 8 and 12 is 4.
- To simplify the fraction 18/24, first find the greatest common divisor of 18 and 24, which is 6.
- If the greatest common divisor of two numbers is 1, those numbers are said to be relatively prime or coprime.
Advanced Usage
- Euclidean Algorithm: The most efficient and common method for computing the greatest common divisor of two numbers is the Euclidean algorithm.
- Example: To find gcd(48, 18), the algorithm proceeds through the steps: 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0. The last non-zero remainder is 6, so gcd(48, 18) = 6.
- Properties:
- gcd(a, b) = gcd(b, a) (commutative property).
- gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) (associative property).
- For any integer k, gcd(ka, kb) = |k| * gcd(a, b).
Variants and Related Words
- Common Divisor: Any integer that divides two or more given integers without a remainder. The "greatest common divisor" is the largest of these.
- Greatest Common Factor (GCF): A synonym for "greatest common divisor," more commonly used in elementary mathematics.
- Highest Common Factor (HCF): Another synonym, frequently used in British English.
Synonyms
- Greatest Common Factor (GCF)
- Highest Common Factor (HCF)
Related Phrases and Concepts
- Least Common Multiple (LCM): The smallest positive integer that is a multiple of two or more integers. The product of the GCD and LCM of two numbers equals the product of the numbers themselves (i.e., gcd(a, b) * lcm(a, b) = a * b for positive integers).
- Relatively Prime / Coprime: A term describing two integers whose greatest common divisor is 1.
- Euclid's Lemma: A fundamental proposition stating that if a prime number divides the product of two integers, then it must divide at least one of the integers. This lemma is used in proving the uniqueness of prime factorization, which is connected to the concept of the GCD.
Noun
- the largest integer that divides without remainder into a set of integers
Khám phá thêm
Các từ liên quan
Từ đồng nghĩa
