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

  • Thread starter tonit
  • Start date
  • Tags
    Prime
In summary: Hi tonit!In summary, if m and n are relatively prime, then their gcd is 1. If not, there would be at least one prime dividing both, thus leading m and n not be relatively prime.
  • #1
tonit
55
1

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 [itex]m[/itex] and [itex]n[/itex] are relatively prime, we have [itex]gcd(m,n) = 1[/itex]. All the common divisors of [itex]m[/itex] and [itex]n[/itex] must divide [itex]gcd(m,n)[/itex], but the only divisors of [itex]1[/itex] are [itex]1[/itex] and [itex]-1[/itex]. Thus they have no common prime divisor.

The converse:

Suppose we have the integers [itex]m[/itex] and [itex]n[/itex] with the following prime factorization:

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

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

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

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


I believe the first part is OK, but I'm not quite sure about the converse proof.
 
Physics news on Phys.org
  • #2
Hi tonit!

I think the second proof is correct... :smile:
 
  • #3
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...
 
  • #4
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
 
  • #5
: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.
 
  • #6
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.
tonit said:
The converse:

Suppose we have the integers [itex]m[/itex] and [itex]n[/itex] with the following prime factorization:

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

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

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

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

[itex]min(a_i,b_i) = 0[/itex] for [itex]1≤i≤r[/itex] means that [itex]gcd(m,n) = p_1^{0}p_2^{0}...p_r^{0} = 1[/itex] which yields that [itex]m[/itex] and [itex]n[/itex] are relatively prime.
 
  • #7
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)
 
  • #8
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:

[itex]gcd(m,n) = 1 \Rightarrow[/itex] no prime divides both
no prime divides both [itex]\Rightarrow gcd(m,n) = 1[/itex]
 
  • #9
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) :)
 

What does it mean for two numbers to be relatively prime?

Two numbers are relatively prime if they do not have any common factors other than 1. This means that their greatest common divisor (GCD) is 1.

Why is it important to show that m and n are relatively prime?

Showing that m and n are relatively prime is important because it helps us understand the relationship between two numbers and allows us to simplify certain mathematical problems. It also has applications in cryptography and number theory.

What is the significance of no prime dividing both m and n?

If no prime number divides both m and n, it means that they do not share any common factors. This is one of the criteria for two numbers to be relatively prime.

How do you prove that m and n are relatively prime if no prime divides both?

To prove that m and n are relatively prime if no prime divides both, we can use proof by contradiction. Assume that m and n are not relatively prime, which means that they have a common prime factor. We can then show that this assumption leads to a contradiction, thus proving that m and n are indeed relatively prime.

Can two numbers be relatively prime if they are both even?

No, two even numbers cannot be relatively prime because they both have 2 as a common factor. For two numbers to be relatively prime, they must not share any common factors, including 2.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
918
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
Back
Top