# Prime Factorizations Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

Hello, I was stuck on this question. I had split the question into possible cases. Since, a and b have the same prime factors in their prime factorizations, I assumed the cases: if for all .

Ideas for for all , if , it would be a similar argument.

I can then rewrite a as: a = .

Hence, b | a and therefore gcd(a, b) = b = = .

The reverse argument applies for if a | b i.e. if for all . If then a = b and so gcd(a,b) = a = b, and it is again the minimum of the the powers, which is either of them as they are equal.

But, I am stuck now since: How do I show it if for i, and some other j, for , then neither: b | a nor a | b, so I am stuck !

Last edited by Chittesh14; 5 months ago

0

reply

Report

#2

For arbitrary i, show that if r_i > Min(a_i, b_i) then r doesn't divide one of a, b (so r isn't the gcd) and if it's <min (a_i, b_i) then p_i r divides both a, b and so r isn't the gcd.

0

reply

(Original post by

For arbitrary i, show that if r_i > Min(a_i, b_i) then r doesn't divide one of a, b (so r isn't the gcd) and if it's <min (a_i, b_i) then p_i r divides both a, b and so r isn't the gcd.

**DFranklin**)For arbitrary i, show that if r_i > Min(a_i, b_i) then r doesn't divide one of a, b (so r isn't the gcd) and if it's <min (a_i, b_i) then p_i r divides both a, b and so r isn't the gcd.

By the way, is this for the general argument proving the whole question, or is it just in addition to my method? i.e. do I have to show my ideas for if for all and what you said, or would doing what you said be enough for the entire proof?

I think showing what you said is enough for the entire proof right, as it rules out the other two cases implying r_i must be = min(m_i, l_i)?

0

reply

Report

#4

It's almost sufficient and you certainly don't need the argument you posted.

To be comolete, you also need to show that there can't be any other primes (i.e. a prime P that's not any of p1,p2...) in the decomposition of r.

To be comolete, you also need to show that there can't be any other primes (i.e. a prime P that's not any of p1,p2...) in the decomposition of r.

0

reply

(Original post by

It's almost sufficient and you certainly don't need the argument you posted.

To be comolete, you also need to show that there can't be any other primes (i.e. a prime P that's not any of p1,p2...) in the decomposition of r.

**DFranklin**)It's almost sufficient and you certainly don't need the argument you posted.

To be comolete, you also need to show that there can't be any other primes (i.e. a prime P that's not any of p1,p2...) in the decomposition of r.

Do you mean in the decomposition of the gcd of a and b, rather than r?

0

reply

**DFranklin**)

For arbitrary i, show that if r_i > Min(a_i, b_i) then r doesn't divide one of a, b (so r isn't the gcd) and if it's <min (a_i, b_i) then p_i r divides both a, b and so r isn't the gcd.

1. Consider the number d = where , then you can rewrite this as: . Hence, d > a and so d cannot divide a. You can also argue d cannot divide b by the same reasoning, but you only need to show d doesn't divide a or b to show it's not a common divisor, so I assume it's valid? Continuing, therefore, d doesn't divide a, hence it cannot be a common divisor of a and b, so it isn't the gcd of a and b.

2. Consider the number e = where . Assume that it is the greatest common divisor of a. Then you can write a as: . Hence, a is divisible by e, so e | a. We can do a similar argument for b, replacing the with for . So, r | a and r | b. But, since for , then since all r, l and m are integers: and . So, and for all . So, if you take , it will still divide both a and b (by similar argument as first part, finding it difficult to repeat the latex...), but now the powers are greater than if r_i is used, so that e.g. f = product of all for is a greater common divisor of a and b, hence a contradiction.

3. The gcd(a,b) cannot have any other distinct primes in its decomposition other than the ones in the decomposition of a and b. Because, primes are only divisible by 1 and themselves, any prime in the decomposition of a and b is only divisible by itself and 1. So, any other prime in the decomposition of the gcd(a,b) that is not in the decomposition of a or b, will not divide any prime factors in a or b, hence it won't be a factor, let alone prime factor of a and b, which will imply that the gcd cannot divide a or b, and lead to a contradiction. So, any prime factor in gcd(a,b) would have to be in the prime factorization of both a and b.

Last edited by Chittesh14; 5 months ago

0

reply

Report

#7

(1)+(2) have serious errors making them invalid. (3) looks ok.

To follow ghostwalker's example: I'm not going to reply further here.

To follow ghostwalker's example: I'm not going to reply further here.

0

reply

(Original post by

(1)+(2) have serious errors making them invalid. (3) looks ok.

To follow ghostwalker's example: I'm not going to reply further here.

**DFranklin**)(1)+(2) have serious errors making them invalid. (3) looks ok.

To follow ghostwalker's example: I'm not going to reply further here.

0

reply

Report

#9

I'd show that if then doesn't divide one of a or b so we need . Clearly largest integer that satisfies this is the one where .

0

reply

(Original post by

I'd show that if then doesn't divide one of a or b so we need . Clearly largest integer that satisfies this is the one where .

**B_9710**)I'd show that if then doesn't divide one of a or b so we need . Clearly largest integer that satisfies this is the one where .

EDIT: Can I do the same with part 2 of my proof: , then it is definitely smaller than the minimum of m_i and l_i, whichever is the smaller. So, I can say it divides a and b, because it is smaller than both m_i and l_i. I feel the mistake in my proof starts where I say r_i + 1 <= l_i. Can you confirm that? Is it that I can't assume they have a difference of 1, it may be that r < m but r = 2, m = 5? etc... Then, I'm not sure how to continue from that point.

I can only think of: If you choose e_i = min(m_i, l_i), then the product of all primes raised to the power of e_i for 1 <= i <= k, it divides both a and b, and therefore it is greater than r, so it is not the greatest common divisor?

Last edited by Chittesh14; 5 months ago

0

reply

Report

#11

(Original post by

Yes, I think that's what I realised my mistake was: , then it is greater than the smaller out of the two, m_i and l_i. So, if it is greater than m_i, x can't divide b, if it is greater than l_i, x can't divide a. Oh, yeah, I get your approach now, thank you!

EDIT: Can I do the same with part 2 of my proof: , then it is definitely smaller than the minimum of m_i and l_i, whichever is the smaller. So, I can say it divides a and b, because it is smaller than both m_i and l_i. I feel the mistake in my proof starts where I say r_i + 1 <= l_i. Can you confirm that? Is it that I can't assume they have a difference of 1, it may be that r < m but r = 2, m = 5? etc... Then, I'm not sure how to continue from that point.

I can only think of: If you choose e_i = min(m_i, l_i), then the product of all primes raised to the power of e_i for 1 <= i <= k, it divides both a and b, and therefore it is greater than r, so it is not the greatest common divisor?

**Chittesh14**)Yes, I think that's what I realised my mistake was: , then it is greater than the smaller out of the two, m_i and l_i. So, if it is greater than m_i, x can't divide b, if it is greater than l_i, x can't divide a. Oh, yeah, I get your approach now, thank you!

EDIT: Can I do the same with part 2 of my proof: , then it is definitely smaller than the minimum of m_i and l_i, whichever is the smaller. So, I can say it divides a and b, because it is smaller than both m_i and l_i. I feel the mistake in my proof starts where I say r_i + 1 <= l_i. Can you confirm that? Is it that I can't assume they have a difference of 1, it may be that r < m but r = 2, m = 5? etc... Then, I'm not sure how to continue from that point.

I can only think of: If you choose e_i = min(m_i, l_i), then the product of all primes raised to the power of e_i for 1 <= i <= k, it divides both a and b, and therefore it is greater than r, so it is not the greatest common divisor?

I think the key here that if r_i>min then it doesn't divide a or b, If r_i<min then there's another number greater that divides a and b. So greatest divisor must be where r_i=min.

Think about another question: what does it mean for a number to be a common divisor of a and b.

0

reply

(Original post by

If r_i<min(l_i, m_i) then certainly x divides both a and b. Also this means that r_i<l_i and r_i<m_i. So of course r_i+1<=l_i is true but I'm not sure what you're saying after that. Also what is r in the last paragraph?

I think the key here that if r_i>min then it doesn't divide a or b, If r_i<min then there's another number greater that divides a and b. So greatest divisor must be where r_i=min.

Think about another question: what does it mean for a number to be a common divisor of a and b.

**B_9710**)If r_i<min(l_i, m_i) then certainly x divides both a and b. Also this means that r_i<l_i and r_i<m_i. So of course r_i+1<=l_i is true but I'm not sure what you're saying after that. Also what is r in the last paragraph?

I think the key here that if r_i>min then it doesn't divide a or b, If r_i<min then there's another number greater that divides a and b. So greatest divisor must be where r_i=min.

Think about another question: what does it mean for a number to be a common divisor of a and b.

Cool, I will think about it and try to come up with something, thank you! .

Last edited by Chittesh14; 5 months ago

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top