Greatest common divisor, no prime factor without power

156 Views Asked by At

If I try to get the GCD of 272 and 210 I end up with the following

  • $272 = 272/2=136/2=68/2=34/2=17$
  • $2^4 \times 17$
  • $210 = 210/2=105/5=21/3=7$
  • $2 \times 5 \times 3 \times 7$

Normally if there are 2 equal numbers with a different force, the one with the highest force is scrapped. But that would mean there are no equal numbers left. So am I to understand the scrapping rule is ignored in these situations and the GCD is 2 or did I make a mistake?

2

There are 2 best solutions below

0
On BEST ANSWER

Scrapping rule is not ignored. Rather, scrapping means taking away the extra force of the larger number. So 2^4 is scrapped down to 2, because it has 3 extra force.

Hope this helped.

(I assumed force means power/exponent. Also, the word "scrap" is not really used to describe what is being done here.)

3
On

The GCD of two numbers stands for the "greatest common divisor", or the "greatest common factor" shared by the two numbers.

$$272 = 2^4 \times 17 = \color{blue}{2^1}\times 2^3 \times 17$$ $$210 = \color{blue}{2^1}\times 3\times 5 \times 7.$$ In this case, as you've shown, the two numbers share only one factor of $2$, so the greatest common factor shared by each of $272$ and $210$ is precisely that one factor of $2$.

What we do ignore is the factor $2^3 = 8$ of $272$, since $210$ has only one factor of $2$, so we scrap the number of factors of any particular prime in one number that exceed the number of factors of that same prime in the second number.

Hence, $\;\gcd(272, 210) = 2.$

For a more general case,

For integers $\,m, n$, $\,a, b,\,$ with $\,a, b \geq 0,\;$ if $\,m = p_1^{a}\times p_2^b,\;$ and $\,n = p_1^c\times q,\,$ where $\,p_1, p_2, q\,$ are distinct primes, then if $\,a \lt c,\,$ $\,\gcd(m,n) = p_1^{a},\,$ and if $\,c\lt a,\,$ then $\,\gcd(m,n) = p_1^c.$