Divisor Proof with Contrapositive

Date: 09/16/2002 at 13:59:01
From: Eric
Subject: Proof of m^2 | n^2 => m | n

I have been trying to prove that if n^2 divides m^2, then n divides m.

   m^2 = k*n^2  m,n,k all in Z.

     k = (m/n)^2

Is there a proof that says if a rational number squared is an integer, 
then it too is an integer? Since we know k is an integer, this would 
be sufficent to prove this, correct?  Thank you for any help.

Eric

Date: 09/16/2002 at 18:08:37
From: Doctor Paul
Subject: Re: Proof of m^2 | n^2 => m | n

I think this proof is most easily accomplished by contraposition.  

Can you prove: 

   n does not divide m => n^2 does not divide m^2

Proving this statement is equivalent to proving your statement, since 
a statement and its contrapositive are logically equivalent.

To prove the statement, suppose that n does not divide m. Then there 
exists some prime p in the prime factorization of n that does not 
occur in the prime factorization of m. If p does not occur in the 
prime factorization of m, it won't occur in the prime factorization of 
m^2 either. Similarly, if p occurs in the prime factorization of n, it 
also occurs in the prime factorization of n^2.

Thus there exists a prime (namely p) in the prime factorization of n^2 
that does not occur in the prime factorization of m^2. Hence, n^2 does 
not divide m^2.  This was to be shown...

I hope this helps. Please write back if you'd like to talk about this 
some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/16/2002 at 20:16:47
From: Eric
Subject: Thank you (proof of m^2 | n^2 => m | n)

AH! That makes sense. I wish I had thought of that. Once I read your 
response it became very clear. Thank you very much!

Eric