Show that m and n relatively prime if and only if no prime divides both

[tonit]

Homework Statement

Show that m and n are relatively prime if and only if no prime divides both.

The Attempt at a Solution

Now, if m and n are relatively prime, we have gcd(m,n) = 1. All the common divisors of m and n must divide gcd(m,n), but the only divisors of 1 are 1 and -1. Thus they have no common prime divisor.

The converse:

Suppose we have the integers m and n with the following prime factorization:

m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}
n = p_1^{b_1}p_2^{b_2}...p_r^{b_r}

where p_i are primes that divide at least one of m and n, and an exponent is zero if the prime in question doesn't occur in that number.

Now the gcd(m,n) = p_1^{k_1}p_2^{k_2}...p_r^{k_r} where k_i = min(a_i,b_i) for 1≤i≤r.

So, if m and n don't have any common primes, min(a_i,b_i) = 0 for 1≤i≤r thus having gcd(m,n) = 1. If not, then there would be at least one prime dividing both, thus leading m and n not be relatively prime.


I believe the first part is OK, but I'm not quite sure about the converse proof.

 

[Infinitum]

Hi tonit!

I think the second proof is correct...

 

[oli4]

Hi tonit,
that looks right, if a bit involved.
Couldn't you just say that if m and n have a common prime than their gcd will be a muliple of it and therefore be >1, thereby showing they are not coprime ?

Cheers...

 

[tonit]

thank you both for your replies.
@oli4, It is about the converse: If they have no common prime divisor, then they are relatively prime. I know there may be other ways to prove it, but I am trying to put all the things I learned to work. Thanks though :D

 

[oli4]

:D
Tonit, you are right ! I just restated your first part :)
Now, if m and n are not coprime, then by definition they have at least a common factor which is >1
From those factors, anyone that is not prime can be broken into products of primes, any of those being a factor too of course.

 

[tonit]

gcd(m,n) = 1 <=> m and n have no common prime divisor...

so after showing that gcd(m,n) = 1 => m and n have no common prime divisor.

it needs to be shown that: m and n have no common prime divisor => gcd(m,n) = 1

Now each integer has it's own unique prime factorization.

And here's where my second part starts from up there.

The converse:

Suppose we have the integers m and n with the following prime factorization:

m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}
n = p_1^{b_1}p_2^{b_2}...p_r^{b_r}

where p_i are primes that divide at least one of m and n, and an exponent is zero if the prime in question doesn't occur in that number.

Now the gcd(m,n) = p_1^{k_1}p_2^{k_2}...p_r^{k_r} where k_i = min(a_i,b_i) for 1≤i≤r.

So, if m and n don't have any common primes, min(a_i,b_i) = 0 for 1≤i≤r thus having gcd(m,n) = 1. If not, then there would be at least one prime dividing both, thus leading m and n not be relatively prime.

min(a_i,b_i) = 0 for 1≤i≤r means that gcd(m,n) = p_1^{0}p_2^{0}...p_r^{0} = 1 which yields that m and n are relatively prime.

 

[oli4]

Hi tonit,
sorry, I must be confusing things, or it might just be a matter of having different definitions in different courses for coprimes (since they are equivalent, this is not too surprising)
For what I remember, two integers are coprime if the only integer that can divide them is 1, which is equivalent to saying their gcd is 1, or to say that they have no common prime divisor
I guess you must be starting with gcd=1 as the initial definition and are sticking to it which is what you have to do.
(I just checked wikipedia and it starts with the same definition I have and mentions indeed that this is the same thing as saying gcd=1)

 

[tonit]

if and only if is <=>

so after proving that gcd(m,n) = 1 means that no prime divides both, you need to prove that no prime divides both => gcd(m,n)=1

so:

Show that m and n relatively prime if and only if no prime divides both can be translated into:

gcd(m,n) = 1 \Rightarrow no prime divides both
no prime divides both \Rightarrow gcd(m,n) = 1

 

[oli4]

Tonit, yes, this is what I just did.
In my first post I said the exact same thing you did in the first part (but you were after the second anyway)
"coprimes (gcd=1) => no common prime" (except by saying "common prime=> not coprimes")
Now I'm saying "not coprimes (gcd>1) => common prime", which is the same thing as
"no common prime => coprimes (gcd=1)"
I must be tired (I am, in fact) :)