Math Problem Solver

Method 1:

$4$ is the greatest common divisor of $56$ and $20$.

The greatest common divisor of two integers is the largest positive integer that divides both integers.

The greatest common divisor of integers $b$ and $a$ is written as $\operatorname{gcd}(b,a)$.

The greatest common divisor can be computed by Euclid's algorithm, which is based on repeated application of the following fact:$$\operatorname{gcd}(b, a) = \operatorname{gcd}(a, r)$$ where $r$ is the remainder of $b$ divided by $a$, and $0 < a \le b$.

Euclid's algorithm for computing the greatest common divisor of $56$ and $20$:

$\operatorname{gcd}(56, 20) = \operatorname{gcd}(20, 16)$, since $16$ is the remainder when $56$ is divided by $20$.

$\operatorname{gcd}(20, 16) = \operatorname{gcd}(16, 4)$, since $4$ is the remainder when $20$ is divided by $16$.

$\operatorname{gcd}(16, 4) = 4$, since $4$ divides $16$.

Method 2:

The greatest common divisor of two integers is the largest positive integer that divides both integers.

The prime factorization of $56$ is $2^{3} \times 7$.

The prime factorization of $20$ is $2^{2} \times 5$.

The GCD is the minimum of the prime powers of the two numbers. Find the greatest common divisor by multiplying the prime number powers together, including only the lowest prime number power of those prime factors which are common to both numbers.

$\text{gcd}(56, 20) = 2^{2} = 4.$