Abstract Algebra Proof question

  • Thread starter Gamble93
  • Start date
  • #1
6
0

Homework Statement



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]

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

Answers and Replies

  • #2
16
0
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.
 
  • #3
15
0
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}.

I'm having trouble understanding this statement. Can someone provide an example?
 
  • #4
158
0
I'm having trouble understanding this statement. Can someone provide an example?

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.
 
  • #5
16
0
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}))...
 
  • #6
Deveno
Science Advisor
908
6
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:

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

Related Threads on Abstract Algebra Proof question

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
6
Views
893
Top