GCD

Jul 17, 2023

A divisor of n, also called a factor of n, is an integer m that can be multiplied by some integer to produce n.
and n is a multiple of m.
$n = km$ then $m | n$

Greatest common divisor. It is also termed as the highest common factor (HCF) or the greatest common factor (GCF).
Euclidean algorithm - Wikipedia

• $gcd(a, b) = ar + bs$ Bezout’s Identity
• If $gcd(a, n) = 1$ and $gcd(a, m) = 1$ then $gcd(a, mn) = 1$
• Lamé’s Theorem:
  • If Euclid’s Algorithm requires k steps to compute the gcd of some pair, then the smaller number in the pair must be greater than or equal to the kth Fibonacci number.
  • $n \geq Fib(k) ≈ \frac{\phi^k}{\sqrt{5}}$, order of growth is $\Theta(\log n)$
    • n is the smaller of the two inputs to the procedure
    • k is the number of steps taken by the process

to compute $gcd(48, 180)$, we find the prime factorizations $48 = 2^4 \cdot 3^1$ and $180 = 2^2 \cdot 3^2 \cdot 5^1$; the GCD is then $2^{min(4,2)} · 3^{min(1,2)} · 5^{min(0,1)} = 2^2 · 3^1 · 5^0 = 12$
I Do Maths · Prime Numbers and Prime Factorization

The Euclidean Algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u.
2. gcd(2u, 2v) = 2 · gcd(u, v)
3. gcd(2u, v) = gcd(u, v), if v is odd (2 is not a common divisor). Similarly, gcd(u, 2v) = gcd(u, v) if u is odd.
4. gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd.

• Bezout’s Identity