what is the highest common factor of 455 and 338?
You asked:
MathBot Answer:
Method 1:
\(13\) is the greatest common divisor of \(455\) and \(338\).
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 \(455\) and \(338\):
\(\operatorname{gcd}(455, 338) = \operatorname{gcd}(338, 117)\), since \(117\) is the remainder when \(455\) is divided by \(338\).
\(\operatorname{gcd}(338, 117) = \operatorname{gcd}(117, 104)\), since \(104\) is the remainder when \(338\) is divided by \(117\).
\(\operatorname{gcd}(117, 104) = \operatorname{gcd}(104, 13)\), since \(13\) is the remainder when \(117\) is divided by \(104\).
\(\operatorname{gcd}(104, 13) = 13\), since \(13\) divides \(104\).
Method 2:
The greatest common divisor of two integers is the largest positive integer that divides both integers.
The prime factorization of $455$ is $5 \times 7 \times 13$.
The prime factorization of $338$ is $2 \times 13^{2}$.
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}(455, 338) = 13 = 13.$