Hello, I'm working out of Hungerford's Abstract Algebra text and this proof has been bothering me because I think I know why it works and it's so simple but I can't figure out how you would show a rigorous proof of it...(adsbygoogle = window.adsbygoogle || []).push({});

If [tex]a=p_1^{r_1}p_2^{r_2}p_3^{r_3} \cdots p_k^{r_k}[/tex] and [tex]b=p_1^{s_1}p_2^{s_2}p_3^{s_3} \cdots p_k^{s_k}[/tex]

where [tex]p_1,p_2, \ldots ,p_k[/tex] are distinct positive primes and each [tex]r_i,s_i \geq 0[/tex] ,

then prove that [tex]GCD(a,b)=p_1^{n_1}p_2^{n_2}p_3^{n_3} \cdots p_k^{n_k}[/tex], where for each [tex]i \text{, } n_i=\min(r_i,s_i)[/tex].

I had thought I might be able to show it through using the definition of GCD as a linear combination--where the GCD, d, is the smallest positive element in the set

[tex]S=\big\{ d=am+bn \text{ } \vert \text{ } m,n \in \mathbb{Z} \big\}[/tex]

and therefore I could use that to show that the GCD(a,b) must be the minimum of each [tex]r_i,s_i[/tex]. But that just isn't working out and seems like it's making the proof too complicated anyway. I apologize that I don't have more of a solution worked out--any hint or help would be greatly appreciated. Thank you.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Simple prime/GCD proof question

**Physics Forums | Science Articles, Homework Help, Discussion**