1
$\begingroup$

If $a=p_{1}^{k_{1}}p_{2}^{k_{2}} \cdots p_{s}^{k_{s}}$ and $b=p_{1}^{l_{1}}p_{2}^{l_{2}} \cdots p_{s}^{l_{s}}$ where $p_1,p_2,...,p_s$ are distinct primes, tell how to use this information to find $d=\gcd(a,b)$. Then argue that if $a$ and $b$ are both squares, so is $d$.

I'm not sure how to attack this problem. I started off by letting $a=2*3*5..$ and $b=2*3*5..$ but I obviously don't know what to do with the $k_s$ and the $l_s$. For example, what are they?

I think if I knew what $a$ and $b$ were I could easily prove $d$ is a square.

2 Answers 2

1

Let $e_i=\min(k_i,l_i)$. (This is the smaller of $k_i$ and $l_i$, where if $k_i=l_i$ we have $e_i=k_i=l_i$.) Then $d=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}.$

If $a$ and $b$ are squares, then the $k_i$ and $l_i$ are all even. So the $e_i$ are all even, and therefore $d$ is a perfect square.

What the symbols mean: The expression $a=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$ is the prime power factorization of $a$. The $p_i$ are distinct primes. It is an important basic theorem of number theory that every integer $\gt 1$ has a prime power factorization, and that, apart from the order of the terms, the factorization is unique.

Remark: There is a similar expression for the lcm of $a$ and $b$. Let $f_i=\max(k_i,l_i)$. Then the lcm is equal to
$p_1^{f_1}p_2^{f_2}\cdots p_s^{f_s}.$

0

Hint $\rm\,\ p\nmid a\:$ $\Rightarrow$ $\rm\:(ap^j,bp^{k+j})\,=\, (a,bp^k)\,p^j =\, (a,b)\,p^j\ $ by Euclid's Lemma. Recurse on $\rm\,(a,b).$

Alternatively, employ the universal definition: $\rm\,\ gcd(\color{#0A0}{a,b}) = \color{#C00}d \ \ $ iff $\rm\ \ c\mid \color{#0A0}{a,b}\!\iff\! c\mid \color{#C00}d$

Notice, by unique factorization, $\rm\ \prod P_i^{J_i}\mid \prod P_i^{K_i}\iff J_i \le K_i.\:$ Therefore

$\rm \prod P_i^{J_i}\,\big|\, \color{#0A0}{\prod P_i^{K_i},\: \prod P_i^{L_i}} \iff J_i \le K_i,L_i \iff J_i\le min(K_i,L_i)\iff \prod P_i^{J_i}\,\big|\,\color{#C00}{\prod P_i^{min(K_i,L_i)}}$

Therefore, by the stated universal definition: $\rm\ gcd\left(\color{#0A0}{\prod P_i^{K_i},\: \prod P_i^{L_i}}\right) =\, \color{#C00}{\prod P_i^{min(K_i,L_i)}}$


Finally note that $\rm\ \prod P_i^{J_i}\:$ square $\,\Rightarrow$ $\rm \prod P_i^{J_i} = \left(\prod P_i^{K_i}\right)^2 = \prod P_i^{2 K_i}\: $ $\Rightarrow$ $\rm\:J_i\:$ even $ $ (and conversely), by unique factorization. Therefore $\rm\:J_i,K_i\:$ even $\,\Rightarrow$ $\rm\:min(J_i,K_i)\:$ even $\,\Rightarrow$ $\rm\:\prod P_i^{min(K_i,L_i)}\:$ square.