Chittesh14
Badges: 19
Rep:
?
#1
Report Thread starter 5 months ago
#1
Name:  Screen Shot 2019-04-16 at 20.03.50.png
Views: 18
Size:  74.3 KB

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 l_i > m_i, m_i > l_i, l_i = m_i for all 1 \leq i \leq k.

Ideas for l_i > m_i for all 1 \leq i \leq k, if m_i > l_i, it would be a similar argument.

I can then rewrite a as: a = (p_1^{m_1} * .... * p_k^{m_k}) * (p_1^{l_1-m_1} * .... * p_k^{l_m-m_k}) = b * (p_1^{l_1-m_1} * .... * p_k^{l_m-m_k}).

Hence, b | a and therefore gcd(a, b) = b = (p_1^{m_1} * .... * p_k^{m_k}) = (p_1^{min(l_1,m_1)} * .... * p_k^{min(l_k,m_k)}).

The reverse argument applies for if a | b i.e. if m_i > l_i for all 1 \leq i \leq k. If l_i = m_i, 1 \leq i \leq k 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, l_i > m_i and some other j, l_i < m_i for  1 \leq i,j \leq k, then neither: b | a nor a | b, so I am stuck !
Last edited by Chittesh14; 5 months ago
0
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 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
reply
Chittesh14
Badges: 19
Rep:
?
#3
Report Thread starter 5 months ago
#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 l_i &gt; m_i, m_i &gt; l_i, l_i = m_i for all 1 \leq i \leq k 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
DFranklin
Badges: 18
Rep:
?
#4
Report 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
reply
Chittesh14
Badges: 19
Rep:
?
#5
Report Thread starter 5 months ago
#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
reply
Chittesh14
Badges: 19
Rep:
?
#6
Report Thread starter 5 months ago
#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 = (p_1^{r_1} * .... * p_k^{r_k}) where r_i &gt; min(l_i, m_i), then you can rewrite this as:  d = (p_1^{l_1} * .... * p_k^{l_k}) * (p_1^{r_1-l_1} * .... * p_k^{r_k-l_k}) = a * (p_1^{r_1-l_1} * .... * p_k^{r_k-l_k}). 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 = (p_1^{r_1} * .... * p_k^{r_k}) where r_i &lt; min(l_i, m_i). Assume that it is the greatest common divisor of a. Then you can write a as:  a = (p_1^{l_1} * .... * p_k^{l_k}) = (p_1^{r_1} * .... * p_k^{r_k}) * (p_1^{l_1-r_1} * .... * p_k^{l_k-r_k}) = e * (p_1^{l_1-r_1} * .... * p_k^{l_k-r_k}). Hence, a is divisible by e, so e | a. We can do a similar argument for b, replacing the l_i with m_i for 1 \leq i \leq k. So, r | a and r | b. But, since r_i &lt; min(l_i, m_i) for 1 \leq i \leq k, then since all r, l and m are integers: r_i &lt; l_i and r_i &lt; m_i. So, r_i+1 \leq l_i and r_i+1 \leq m_i for all 1 \leq i \leq k. So, if you take r_i+1, 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 p_i^{r+1} for i \leq i \leq k 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
DFranklin
Badges: 18
Rep:
?
#7
Report 5 months ago
#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.
0
reply
Chittesh14
Badges: 19
Rep:
?
#8
Report Thread starter 5 months ago
#8
(Original post by 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.
OK, I think I found the error for (a). Thanks
0
reply
B_9710
Badges: 17
Rep:
?
#9
Report 5 months ago
#9
I'd show that if  r_i &gt; \text{min} \{\ell _i, m_i \} then x= \prod p_i ^{r_i } doesn't divide one of a or b so we need  r_i \leq \text{min} \{\ell _i, m_i \} . Clearly largest integer that satisfies this is the one where  r_i = \text{min} \{\ell _i , m_i \} .
0
reply
Chittesh14
Badges: 19
Rep:
?
#10
Report Thread starter 5 months ago
#10
(Original post by B_9710)
I'd show that if  r_i &gt; \text{min} \{\ell _i, m_i \} then x= \prod p_i ^{r_i } doesn't divide one of a or b so we need  r_i \leq \text{min} \{\ell _i, m_i \} . Clearly largest integer that satisfies this is the one where  r_i = \text{min} \{\ell _i , m_i \} .
Yes, I think that's what I realised my mistake was:  r_i &gt; \text{min} \{\ell _i, m_i \} , 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:  r_i &lt; \text{min} \{\ell _i, m_i \} , 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
B_9710
Badges: 17
Rep:
?
#11
Report 5 months ago
#11
(Original post by Chittesh14)
Yes, I think that's what I realised my mistake was:  r_i &gt; \text{min} \{\ell _i, m_i \} , 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:  r_i &lt; \text{min} \{\ell _i, m_i \} , 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
reply
Chittesh14
Badges: 19
Rep:
?
#12
Report Thread starter 5 months ago
#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 x = \prod p_i ^{r_i+1 } 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 x = \prod p_i ^{r_i+1 } > \prod p_i ^{r_i} since r_i+1 &gt; r_i.

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

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

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

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%

Watched Threads

View All