Simple prime/GCD proof question

  • Thread starter jeffreydk
  • Start date
  • #1
135
0
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...

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.
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
it's the greatest!

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].
Hi jeffreydk! :smile:

Well, it obviously is a divisor of both … and if you multiply it by anything else, it won't be, and therefore …

:cool: it's the greatest! :cool:
 
  • #3
135
0
ohh hah yes of course, thanks.
 

Related Threads on Simple prime/GCD proof question

  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
5
Views
3K
Top