Question

Determine the greatest common divisor of 164 and 258.

Polynomial factorization
ANSWERED
asked 2021-05-10
Determine the greatest common divisor of 164 and 258.

Answers (1)

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}\)
0
 
Best answer

expert advice

Need a better answer?
...