1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Abstract Algebra Proof question

  1. Jan 24, 2012 #1
    1. The problem statement, all variables and given/known data

    Let [tex] a=p_{1}^{r_{1}}p_{2}^{r_{2}}...p_{k}^{r_{k}}, b=p_{1}^{s_{1}}p_{2}^{s_{2}}...p_{k}^{s_{k}} [/tex] where [tex] p_{1},p_{2},...,p_{k} [/tex] are distinct positive primes and each [tex] r_{i},s_{i} ≥ 0[/tex] Prove that [tex] (a,b)=p_{1}^{n_{1}}p_{2}^{n_{2}}...p_{k}^{n_{k}} \mbox{ where for each } i \mbox{, } n_{i}=\mbox{minimum of } r_{i},s_{i}. [/tex]

    2. Relevant equations

    This is a question from a homework assignment from a first course in abstract algebra. The class has only been going for a few weeks. We've covered the long division algorithm for integers, the fundamental theorem of algebra, Euclid's algorithm and a few other menial theorems.

    3. The attempt at a solution

    I've tried letting [tex] c=p_{1}^{h_{1}}p_{2}^{h_{2}}...p_{k}^{h_{k}}, h_{i}≥
    0[/tex] be a divisor of a and b and then I just get lost. I'm not used to rigorous proof at all and this course has been a struggle for me while I get acquainted with the many styles of proof. Any sort of help or even guidance in the right direction would be much appreciated.
  2. jcsd
  3. Jan 24, 2012 #2
    I take it (a,b) = gcd(a,b)? I'm not sure if it is just a difference in notation or not, but I think your prime factor representations should be infinite, without a index k where it stops. It's a product of all primes to different powers greater than or equal to 0, and there are an infinite amount of them (many of them will have a power of 0). For a proof like this, you have two things to show: the first is that your candidate for the gcd(a,b) divides both a and b. Here our candidate is the right side of the (a,b)= (p_1)^{n_1}(p_2)^{n_2}... equation. Each n_i is min{r_i,s_i}, so we can divide both a and b with our candidate, since for each prime p_i, the corresponding prime in a and b will either be cancelled out or have a power of max{r_i,s_i}-min{r_i,s_i}. With this in mind you can formally show that your candidate divides both a and b. After this, you need to show that it is in fact the largest number that divides both a and b. A good start is to assume there is a larger one and show it is impossible.
  4. Jan 30, 2012 #3
    I'm having trouble understanding this statement. Can someone provide an example?
  5. Jan 30, 2012 #4
    The gcd of [tex](a,b) = p_1^{\min\{r_1,s_1\}}\cdots p_n^{\min\{r_n,s_n\}}[/tex]

    You take the minimum of the powers from a and b.

    Suppose [tex]a = 2^2\times 3[/tex] and [tex]b = 2\times 3^4[/tex]

    [tex](a,b) = 2\times 3[/tex]

    a has a 2 with power 2 and b with power 1. I took the min. I do this for all primes.
  6. Jan 30, 2012 #5
    Sure: we can write 108 as 108=(2^2)(3^3)(5^0)(7^0)... and 405 as 405=(2^0)(3^4)(5^1)(7^0)(11^0)... . Using our formula for (108,405)=(2^min{2,0})(3^min{3,4})(5^min{0,1})(7^min{0,0})(11^min{0,0})... we see that
    (108,405)=(2^0)(3^3)(5^0)(7^0)(11^0)... = 9. This divides both:
    108/9 = (2^2)(3^(3-2))(5^0)(7^0)...=(2^(max{2,0}-min{2,0}))(3^(max{3,4}-min{3,4}))(5^(max{0,0}-min{0,0}))...
  7. Jan 30, 2012 #6


    User Avatar
    Science Advisor

    if a prime does not occur in the prime factorization of an integer, it can be safely ommitted (the only 0 powers we need are the primes that occur in the factorization of one of a or b, but not both). no one i've ever come across factors 7 as:

  8. Jan 30, 2012 #7
    Definitely Deveno, but it's good to understand that it is an infinite product, otherwise you lose the uniqueness of each factorization.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook