Best solutions to - "Determine the greatest common divisor of 164 and..."

Burhan Hopper

Answered question

2021-05-10

Determine the greatest common divisor of 164 and 258.

Elberte

Skilled2021-05-12Added 95 answers

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

m = p_{1}^{s_{1}} p_{2}^{s_{2}} \dots . p_{r}^{s_{r}}

n = p_{1}^{t_{1}} p_{2}^{t_{2}} \dots . p_{r}^{t_{r}}

Then

gcd (m, n) = p_{1}^{min (s_{1}, t_{1})} p_{2}^{min (s_{2}, t_{2})} \dots . . p_{r}^{min (s_{r}, t_{r})}

Step 2
Find gcd(164, 258).
The prime factorization of 164 and 258 is:

164 = 2^{2} \times 41 = 2^{2} \times 3^{0} \times 41^{1} \times 43^{0}

258 = 2 \times 3 \times 43 = 2^{1} \times 3^{1} \times 41^{0} \times 43^{1}

Step 3
Therefore,

gcd (m, n) = 2^{min (2, 1)} \times 3^{min (0, 1)} \times 41^{min (1, 0)} \times 43^{min (0, 1)}

= 2^{1} \times 3^{0} \times 41^{0} \times 43^{0} = 2

Do you have a similar question?

Recalculate according to your conditions!

Didn't find what you were looking for?