Greatest common divisor
Builds on Divisibility
Definition
Let and be integers that are not both . A common divisor of and is an integer such that and . The greatest common divisor is the largest common divisor of and . By convention, .
Remarks
The number is positive when and are not both , because is a common divisor. An equivalent definition: is the unique nonnegative common divisor of and that each common divisor divides. This form also gives . For all integers , . The Euclidean algorithm computes .
Reading path
To understand this page from the ground up, read these 2 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Divisibility definition
- Greatest common divisor definition
Where this leads
51 pages build on this one.
- Pythagorean triple
- Diffie–Hellman key exchange
- Generalized Euclid's lemma
- Chinese remainder theorem for non-coprime moduli
- Multiplicativity of the divisor function
- Existence of primitive roots modulo a prime
- Fermat numbers are pairwise coprime
- Number of invertible residues modulo n
- Lcm of coprime integers
- Fermat's right triangle theorem
- Discrete logarithm
- Sum of the totient over the divisors
- Cancellation in congruences
- Multiplicative function
- Totient of a prime power
- Consecutive Fibonacci numbers are coprime
- Bézout's identity
- Primitive root theorem
- Fermat's Last Theorem for n = 4
- Chinese remainder theorem
- Multiplicativity of the totient function
- Coprime integers
- Dirichlet's theorem on arithmetic progressions
- Completely multiplicative function
- RSA cryptosystem
- Totient of a prime
- Reduced residue system
- Classification of Pythagorean triples
- Primitive root modulo n
- Existence of inverses modulo n
- Farey sequence
- Dirichlet convolution of multiplicative functions is multiplicative
- Integers modulo a prime form a field
- Multiplicative order
- Carmichael number
- Product of the gcd and the lcm
- Frobenius coin problem
- Multiplicativity of the Möbius function
- Euler's theorem
- Euler's totient function
- The order modulo p divides p − 1
- Lambert series
- Primitive polynomial over a finite field
- Prime-factor FFT algorithm
- Euler product for multiplicative functions
- Congruent number problem
- Hasse–Minkowski theorem
- Fast Fourier transform
- Pseudo-spectral method
- Chebotarev's density theorem
- Integer factorization
Further reading
About this page
| Tag | 02WF878BH1 |
|---|---|
| URI | m2://02WF878BH1 |
| Aliases | gcd, greatest-common-factor, highest-common-factor |
| Kind | definition |
| Writing | W1 stated |
| MSC | 11A05 |
| Defines | Greatest common divisor |
| Uses | Divisibility |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.