# Prime FactorizationsWatch

Announcements
#1

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
5 months ago
#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
#3
(Original post by 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.
Thank you, don't know why I didn't think of this.
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
5 months ago
#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.
0
#5
(Original post by 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.
Ok, thank you. I will work on it now.
Do you mean in the decomposition of the gcd of a and b, rather than r?
0
#6
(Original post by 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.
Ok, here are my current ideas:

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
5 months ago
#7
(1)+(2) have serious errors making them invalid. (3) looks ok.

0
#8
(Original post by DFranklin)
(1)+(2) have serious errors making them invalid. (3) looks ok.

OK, I think I found the error for (a). Thanks
0
5 months ago
#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
#10
(Original post by 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 .
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?
Last edited by Chittesh14; 5 months ago
0
5 months ago
#11
(Original post by 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?
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.
0
#12
(Original post by 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.
Yeah, I just meant: since r_i+1 <= l_i and r_i+1 <= m_i, then for 1 <= i <= k divides both a and b, leading to a contradiction that e was the greatest common divisor of a and b as > since .

Cool, I will think about it and try to come up with something, thank you! .
Last edited by Chittesh14; 5 months ago
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• The University of Law
The Bar Series: Applications and Interviews - London Bloomsbury campus Postgraduate
Thu, 17 Oct '19
• Cardiff Metropolitan University
Sat, 19 Oct '19
• Coventry University
Sat, 19 Oct '19

### Poll

Join the discussion

#### How has the start of this academic year been for you?

Loving it - gonna be a great year (141)
17.89%
It's just nice to be back! (213)
27.03%
Not great so far... (282)
35.79%
I want to drop out! (152)
19.29%