GCD

The greatest common divisor of the arguments.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaGreatest common divisor↗MathWorldGreatestCommonDivisor↗WikidataQ131752↗Encyclopedia of MathematicsGreatest_common_divisor↗nLabgreatest common divisor↗Britannicatopic/greatest-common-divisor↗FungrimGCD✓↗Fungrim entryWolfram LanguageGCD✓↗SageMathgcd([$*,])✓↗Rosetta CodeGreatest common divisor↗

GCD(a, b, …)greatest common divisor of two or more integers.

Typed signatures

Type	Package	Applies
(any*) -> number	compute-engine	always
(any*) -> number	number-theoryreplaces compute-engine	always

Domain: Number theory

Details

• Also called the greatest common factor: the largest positive integer dividing every argument.
• Paired with LCM by $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab$.
• compute-engine discards signs before computing, so $\gcd(-a,b)=\gcd(a,b)$.
• $\gcd(0,n)=n$ since every integer divides 0; with no arguments at all compute-engine returns 0, GCD's identity element.
• Extends to rationals: $\gcd(p_1/q_1, \dots) = \gcd(p_1, \dots)/\operatorname{lcm}(q_1, \dots)$.

Examples

26 more kept as data, checked against the oracles

Basic #

live ↗

In$\gcd(12, 18)$Out$6$

live ↗

In$\gcd(24, 36)$Out$12$

GCD is variadic: it accepts any number of arguments

live ↗

In$\gcd(20, 30, 45)$Out$5$

live ↗

In$\gcd(2, 6, 10)$Out$2$

Scope #

Over the rationals: the gcd of the numerators over the lcm of the denominators

live ↗

In$\gcd(\frac{1}{3}, \frac{2}{5}, \frac{3}{7})$Out$\frac{1}{105}$

Gaussian integers: the associate in the first quadrant

live ↗

In$\gcd(3+i, 1+3i)$Out$1+i$

Gaussian integers: $-3+2i=i(2+3i)$ and $10+15i=5(2+3i)$

live ↗

In$\gcd(-3+2i, 10+15i)$Out$2+3i$

Gaussian rationals: $\gcd(15+10i,\,3+2i)/\operatorname{lcm}(3,2)$

live ↗

In$\gcd(5+\frac{10}{3}i, \frac{3}{2}+i)$Out$\frac{1}{2}+\frac{1}{3}i$

Big integers: $\gcd(20!,\,10^{100}+3)=7$, exact past where a double rounds

live ↗

In$\gcd(20!, 10^{100}+3)$Out$7$

Listable: a single list argument threads element-wise against the rest

live ↗

In$\gcd(12, \bigl\lbrack3, 7, 40\bigr\rbrack)$Out$\bigl\lbrack3, 1, 4\bigr\rbrack$

live ↗

In$\mathrm{ReduceConditions}(\gcd(a^2-1, 12)\lt\gcd(a, 12)∧-10\lt a\lt10, a, ℤ)$Out$\mathrm{ReduceConditions}(\gcd(12, a^2-1)\lt\gcd(12, a)∧-10\lt a\lt10, a, ℤ)$

Applications #

Reduce $12/18$ to lowest terms by dividing out the GCD

live ↗

In$\frac{12}{\gcd(12, 18)}$Out$2$

Greatest common divisor of two integers

live ↗

In$\gcd(14, 105)$Out$7$

When one divides the other, the gcd is the smaller

live ↗

In$\gcd(24, 12)$Out$12$

Shared factor 3

live ↗

In$\gcd(6, 21)$Out$3$

The gcd of 6 and 3 is itself divisible by 3

live ↗

In$\gcd(6, 3)\bmod3=0$Out$\mathrm{True}$

Properties #

Commutative: $\gcd(a,b)=\gcd(b,a)$

live ↗

In$\gcd(12, 18)=\gcd(18, 12)$Out$\mathrm{True}$

$\gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab$. See LCM

live ↗

In$\gcd(12, 18)\operatorname{lcm}(12, 18)=12×18$Out$\mathrm{True}$

$\gcd(F_m,F_n)=F_{\gcd(m,n)}$: here $F_6=8$. See Fibonacci

live ↗

In$\gcd(\mathrm{Fibonacci}(12), \mathrm{Fibonacci}(18))$Out$8$

Takes any number of arguments; distinct primes give 1

live ↗

In$\gcd(7, 11, 29)$Out$1$

Coprime integers have gcd 1

live ↗

In$\gcd(5, 6)=1$Out$\mathrm{True}$

Possible issues #

A single argument is returned unchanged

live ↗

In$\gcd(4)$Out$4$

With no arguments compute-engine returns 0, the identity element

live ↗

In$\gcd()$Out$0$

0 is absorbed: every integer divides it, so $\gcd(0,n)=n$

live ↗

In$\gcd(0, 5)$Out$5$

Signs are discarded before computing the GCD

live ↗

In$\gcd(-12, 9, 57)$Out$3$

Lists of one length thread element-wise, as in Wolfram: $\{\gcd(2,6),\gcd(4,8)\}$

live ↗

In$\gcd(\bigl\lbrack2, 4\bigr\rbrack, \bigl\lbrack6, 8\bigr\rbrack)$Out$\bigl\lbrack2, 4\bigr\rbrack$

$\gcd(0,0)=0$ by convention

live ↗

In$\gcd(0, 0)$Out$0$

Symbolic arguments stay unevaluated

live ↗

In$\gcd(x, y)$Out$\gcd(x, y)$

The result is never negative

live ↗

In$\gcd(-3, 9)$Out$3$

An infinite argument has no divisors to take: the call stays unevaluated, as in Wolfram

live ↗

In$\gcd(∞, 6)$Out$\gcd(6, ∞)$

About

Examples	56
Checked against	Wolfram Language 56 agreeSageMath 52 agree2 unevaluated1 errorSymPy 46 agree2 unevaluatedmathlib4 9 agree2 errorOscar 9 agree5 errorJulia 19 agree28 errorRust 17 agree2 error
Crosswalk	WikipediaMathWorldWikidataEncyclopedia of MathematicsnLabBritannicaFungrimFungrim entry ×35Wolfram LanguageSageMath ×2SymPyOscarJuliaRustRosetta Code

Implementation

mappedwolframpackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

mappedoscarpackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

mappedrustpackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

See also: LCM, ExtendedGCD