# Category:Greatest Common Divisor

Jump to navigation
Jump to search

This category contains results about **Greatest Common Divisor**.

Definitions specific to this category can be found in Definitions/Greatest Common Divisor.

Let $a, b \in \Z: a \ne 0 \lor b \ne 0$.

### Definition 1

The **greatest common divisor of $a$ and $b$** is defined as:

- the largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$

### Definition 2

The **greatest common divisor of $a$ and $b$** is defined as the (strictly) positive integer $d \in \Z_{>0}$ such that:

- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$

This is denoted $\gcd \set {a, b}$.

When $a = b = 0$, $\gcd \set {a, b}$ is undefined.

## Subcategories

This category has the following 14 subcategories, out of 14 total.

### B

- Bézout's Identity (12 P)

### C

### E

- Examples of Common Divisors (2 P)

### G

- GCD from Prime Decomposition (9 P)

### I

### L

### P

- Product of GCD and LCM (6 P)

## Pages in category "Greatest Common Divisor"

The following 49 pages are in this category, out of 49 total.

### B

### E

### G

- GCD and LCM Distribute Over Each Other
- GCD and LCM from Prime Decomposition
- GCD equals GCD with Product of Coprime Factor
- GCD for Negative Integers
- GCD from Congruence Modulo m
- GCD from Generator of Ideal
- GCD from Prime Decomposition
- GCD from Prime Decomposition/General Result
- GCD of Consecutive Integers of General Fibonacci Sequence
- GCD of Fibonacci Numbers
- GCD of Generators of General Fibonacci Sequence is Divisor of All Terms
- GCD of Integer and Divisor
- GCD of Integer and its Negative
- GCD of Integer with Integer + n
- GCD of Integers with Common Divisor
- GCD of Polynomials does not depend on Base Field
- GCD of Sum and Difference of Coprime Integers
- GCD of Sum and Difference of Integers
- GCD with One Fixed Argument is Multiplicative Function
- GCD with Prime
- GCD with Remainder
- GCD with Self
- GCD with Zero
- Greatest Common Divisor divides Lowest Common Multiple
- Greatest Common Divisor is Associative
- Greatest Common Divisor is at least 1
- Greatest Common Divisors in Principal Ideal Domain are Associates

### L

### S

- Set of Integer Combinations equals Set of Multiples of GCD
- Set of Integer Multiples of GCD
- Set of Integers with GCD of 1 are not necessarily Pairwise Coprime
- Smallest Positive Integer Combination is Greatest Common Divisor
- Solution of Linear Diophantine Equation
- Sum of Integer Ideals is Greatest Common Divisor