1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple prime/GCD proof question

  1. Jul 11, 2008 #1
    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.
  2. jcsd
  3. Jul 12, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    it's the greatest!

    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:
  4. Jul 12, 2008 #3
    ohh hah yes of course, thanks.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Simple prime/GCD proof question
  1. Gcd proof (Replies: 11)

  2. GCD in PROOF? (Replies: 3)

  3. GCD question (Replies: 6)