Question

# Determine the greatest common divisor of 164 and 258.

Polynomial factorization
Determine the greatest common divisor of 164 and 258.

2021-05-12
Step 1
To find the gcd of two numbers m and n, take the prime factorization of both numbers.
Let the prime factorization of m and n be
$$\displaystyle{m}={{p}_{{{1}}}^{{{s}_{{{1}}}}}}{{p}_{{{2}}}^{{{s}_{{{2}}}}}}\ldots.{{p}_{{{r}}}^{{{s}_{{{r}}}}}}$$
$$\displaystyle{n}={{p}_{{{1}}}^{{{t}_{{{1}}}}}}{{p}_{{{2}}}^{{{t}_{{{2}}}}}}\ldots.{{p}_{{{r}}}^{{{t}_{{{r}}}}}}$$
Then
$$\displaystyle{\gcd{{\left({m},{n}\right)}}}={{p}_{{{1}}}^{{\min{\left({s}_{{{1}}},{t}_{{{1}}}\right)}}}}{{p}_{{{2}}}^{{\min{\left({s}_{{{2}}},{t}_{{{2}}}\right)}}}}\ldots..{{p}_{{{r}}}^{{\min{\left({s}_{{{r}}},{t}_{{{r}}}\right)}}}}$$
Step 2
Find gcd(164, 258).
The prime factorization of 164 and 258 is:
$$\displaystyle{164}={2}^{{{2}}}\times{41}={2}^{{{2}}}\times{3}^{{{0}}}\times{41}^{{{1}}}\times{43}^{{{0}}}$$
$$\displaystyle{258}={2}\times{3}\times{43}={2}^{{{1}}}\times{3}^{{{1}}}\times{41}^{{{0}}}\times{43}^{{{1}}}$$
Step 3
Therefore,
$$\displaystyle{\gcd{{\left({m},{n}\right)}}}={2}^{{\min{\left({2},{1}\right)}}}\times{3}^{{\min{\left({0},{1}\right)}}}\times{41}^{{\min{\left({1},{0}\right)}}}\times{43}^{{\min{\left({0},{1}\right)}}}$$
$$\displaystyle={2}^{{{1}}}\times{3}^{{{0}}}\times{41}^{{{0}}}\times{43}^{{{0}}}={2}$$