Properties Of GCD function

Revision en1, by utkarsh.agarwal.min19, 2021-10-06 13:48:34

• GCD of a set of numbers can be thought as a blue-print of those numbers. If u keep adding the GCD you can make all numbers that belong in that set.

• Every common divisor of a and b is a divisor of gcd(a,b).

• Gcd(a,b) where both a and b are non-zero, can also be defined as the smallest positive integer d which can be a solution/which can be expressed as a linear combination of a and b in the form d=a*p + b*q, where both p and q are integers.

• Gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.

• If 'a' divides b*c and gcd(a,b)=d , then a/d divides c.

• If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).

• If m is any integer gcd(a,b)=gcd(a+m*b,b).

• The GCD: gcd(a, b) = gcd(b, a%b).

• If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.

• GCD is a multiplicative function. That is if a1 and a2 are coprime gcd(a1*a2,b)=gcd(a1,b)*gcd(a2,b).

• The GCD is a commutative function: gcd(a, b) = gcd(b, a).

• The GCD is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). Thus gcd(a, b, c, ...) can be used to denote the GCD of multiple arguments.

• gcd(a, b) is closely related to the least common multiple lcm(a, b): we have gcd(a, b)⋅lcm(a, b) = |a⋅b|.

• The following versions of distributivity hold true: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).

• If we have the unique prime factorizations of a = p1e1 p2e2 ⋅⋅⋅ pmem and b = p1f1 p2f2 ⋅⋅⋅ pmfm where ei ≥ 0 and fi ≥ 0, then the GCD of a and b is gcd(a,b) = p1min(e1,f1) p2min(e2,f2) ⋅⋅⋅ pmmin(em,fm).

• In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (a, b).

• For non-negative integers a and b, where a and b are not both zero, provable by considering the Euclidean algorithm in base n: gcd(na − 1, nb − 1) = ngcd(a,b) − 1.

• An identity involving Euler's totient function: Gcd(a,b)=∑φ(k) where k are all common divisors of 'a' and 'b'

Tags gcd, number theory, euler

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English utkarsh.agarwal.min19 2021-12-07 02:19:24 273
en3 English utkarsh.agarwal.min19 2021-10-06 15:20:11 117
en2 English utkarsh.agarwal.min19 2021-10-06 14:50:00 388
en1 English utkarsh.agarwal.min19 2021-10-06 13:48:34 2183 Initial revision (published)