Re: Newbie question(s)...

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 09/17/03 

Date: Wed, 17 Sep 2003 14:28:26 +0200

On Tue, 16 Sep 2003 19:09:44 +0000, M.S.Bo wrote:

> On 16 Sep 2003 07:13:58 -0700, jonathanrbaker@yahoo.com (Jonathan
> Baker) wrote:
>
>>- I *think* that the square root of any prime number is irrational
>>(need to write some code...)
>
> No, you want a proof. I doubt you could write any computer program
> that can prove there the square root of every prime number is
> irrational.
>
> If I remember correctly, there is a proof that is proof by
> contradiction; assume that for a prime number, the square root is
> rational, find a contradiction.

It is a simple proof: when sqrt(p) is a positive rational number it
can be expressed as the ratio n/m, where n and m are both natural
numbers such that the greatest common divisor of n an m is 1.

We then have p = n^2/m^2 and consequently p * m^2 = n^2. It is
obvious that p divides n^2, but because p is a prime number it must
also be the case that p divides n (because the exponent for each prime
in the factorization of n^2 must be even). Now we also have that p^2
divides n^2, i.e. n^2 = p^2 * k, for some integer k. From this it
follows that p * m^2 = n^2 = p^2 * k and consequently m^2 = p *
k. Thus p is a divisor of m^2 and using the same reasoning as above
that also means that p is also a divisor of m.

Now we have reached the contradiction because we assumed that n and m
had no common factor.

greetings,

Ernst Lippe

Relevant Pages