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