Abstract Algebra Proof question

[Gamble93]

Homework Statement

Let $$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}}$$ where $$p_{1},p_{2},...,p_{k}$$ are distinct positive primes and each $$r_{i},s_{i} ≥ 0$$ Prove that $$(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}.$$

Homework 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.

The Attempt at a Solution

I've tried letting $$c=p_{1}^{h_{1}}p_{2}^{h_{2}}...p_{k}^{h_{k}}, h_{i}≥ 0$$ 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.

 

[aeroplane]

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 canceled 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.

 

[Rker]

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 canceled out or have a power of max{r_i,s_i}-min{r_i,s_i}.

I'm having trouble understanding this statement. Can someone provide an example?

 

[fauboca]

I'm having trouble understanding this statement. Can someone provide an example?

The gcd of $$(a,b) = p_1^{\min\{r_1,s_1\}}\cdots p_n^{\min\{r_n,s_n\}}$$

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

Suppose $$a = 2^2\times 3$$ and $$b = 2\times 3^4$$

$$(a,b) = 2\times 3$$

a has a 2 with power 2 and b with power 1. I took the min. I do this for all primes.

 

[aeroplane]

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}))...

 

[Deveno]

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}))...

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:

2⁰3⁰5⁰7¹11⁰13⁰...

 

[aeroplane]

Definitely Deveno, but it's good to understand that it is an infinite product, otherwise you lose the uniqueness of each factorization.