Prime Factorizations

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.

Reply 2

OP

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 > m_i, m_i > 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)?

Reply 3

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.

Reply 4

OP

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?

Reply 5

OP

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 > 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 < 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 < min(l_i, m_i)

for

1 \leq i \leq k

, then since all r, l and m are integers:

r_i < l_i

and

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

(edited 5 years ago)

Reply 6

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.

Reply 7

OP

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

Reply 8

B_9710

I'd show that if

r_i > \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 \}

.

Reply 9

OP

Original post by B_9710

I'd show that if

r_i > \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 > \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 < \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?

(edited 5 years ago)

Reply 10

B_9710

Original post by Chittesh14

Yes, I think that's what I realised my mistake was:

r_i > \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 < \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.

Reply 11

OP