(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

3. 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 Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Show that m and n relatively prime if and only if no prime divides both

**Physics Forums | Science Articles, Homework Help, Discussion**