Proving sqrt(2) is irrational

[tomcant]

I was wondering if the following would suffice as a proof.

Prove that sqrt(2) is irrational.

Suppose that sqrt(2) is rational, and so sqrt(2) = p/q, for some p,q ε N.

Then 2*q^2 = p^2.

Now we can say that the integers on the left and right hand side have unique and identical prime factorisations. But, on the left there must be an odd number of factors of 2, since q^2 must have an even number. On the right side, there must be an even number of factors of 2, which is a contradiction, and thus sqrt(2) is irrational.

[ventsyv]

I'm not quite sure I understand your logic. Why does q^2 need to have even number of 2s in the prime factorization ? Why does it need to have any 2s ?? You assumed that p,q belong to N but nothing more. P could be 13 and q can be 17 for example.... or 8 and 9. Neither p nor q need to be even.
Here is my approach:

sqrt(2)=p/q such that p,q belong to N and gcd(p,q)=1 (clearly if gcd(p,q)!=1 p/q can be reduced to such that gcd(p1,q1)=1)

Then 2q^2 = p^2 => gcd(p^2,q^2)=gcd(2q^2,q^2)=2

I could be proven that gcd(p,q)=1=gcd(p^2,q^2) which is contradiction with above. Therefore sqrt(2) not rational.

I'll leave proving gcd(p,q)=1=gcd(p^2,q^2) to you. It involves factorization and is pretty straight forward.

Edit: Sorry I meant to say gcd not gcm

[Alvaro]

Your proof is correct, tomcant.

I'm not quite sure I understand your logic. Why does q^2 need to have even number of 2s in the prime factorization ? Why does it need to have any 2s ??

Zero 2s is an even number of 2s.

[...]
Then 2q^2 = p^2 => gcd(p^2,q^2)=gcd(2q^2,q^2)=2

Actually, gcd(2q^2,q^2)=q^2, not 2.

[Wizard]

x^2 must have an even number of factors for any integer x.
I forget the specific proof, but basically it's
[x] is the list of prime factors of x itself. So x*x will have factors [x] + [x], which will be even. Some numbers might be duplicates, but they're still prime factors, right?
Except when x is 1. or 0. Stupid base cases.

Anywho, q^2 must have an even number of factors, so 2*q^2 is therefore an odd number of factors, which (as noted by tomcant) contradicts the right side where p^2 must have an even number of factors.
Tomcant's proof by contradiction seems tight to me. Needs more words though.

[Alvaro]

The more traditional way of proving this is starting like ventsyv, picking p and q with gcd(p,q)=1.

If 2q^2=p^2, then 2 divides p^2. Because 2 is prime, 2 must divide p (a modern definition of prime goes something like this: "if a prime number divides a product of numbers, it must divide one of the two numbers"). Let's write p=2x. Now the identity is 2q^2=4x^2 => q^2=2x^2. Now it turns out that 2 divides q^2, and therefore (like before) 2 divides q. But now we have 2|p and 2|q, which contradicts gcd(p,q)=1.

The advantage of this proof is that it doesn't require the use of unique factorization integers into primes, which is a non-trivial theorem. Personally, I still think I like tomcant's proof better, though.

[tomcant]

Thanks a lot everyone, I just needed to clarify that I wasn't messing up anywhere. I knew about the more traditional proof, but I was looking for something a little more elegant.

Thanks again