Dean Hanafy

Posted on Sunday, 23 November, 2003 - 09:59 pm:

Can someone tell me if i have proved the following validly or not? If not, the say so, but please don't tell me how to do the problem

Show that if p is prime, then p^1/2 must be irrational

p|ab => pn = ab => pc= a and pd = b

for n,c,d elements of Z and a,b elements of N

so (p^2)cd = ab

(p^2)cd = pn

p = n/cd

Now for a number to be rational, it must be able to be expressed in form s/t where s,t are elements of Z, without common factors.

so assume p^1/2 is rational

p^1/2 = s/t

p^1/2 = (n/cd)^1/2

where n = ab/p and cd= ab/p^2

and so n and cd have a common factor of ab which is a contradiction. Therefore the square root of any prime must be irrational

Thanks
Dean

James

Posted on Sunday, 23 November, 2003 - 10:12 pm:

Deleted

Tristan Marshall

Posted on Sunday, 23 November, 2003 - 10:47 pm:

Unfortunately, there is a problem on line 1, since:

LaTeX Image

but

James

Posted on Sunday, 23 November, 2003 - 10:50 pm:

I dont get the last statement, can you expand. Is what your saying that since a rational number can be expressed as s/t where s and t are coprime, therefore its a contradiction since n and cd arent coprime?
If you sub back in you get
p = n/cd = ab/p / ab/p²
= ab/p * p² /ab
= p

I dont really understand.
By the way, the fact that p is prime is not used in the proof and therefore if your proof is correct, it can prove that same result for any number, even if its not prime.

James

Posted on Sunday, 23 November, 2003 - 10:56 pm:

Heh, i just saw ur message Tristan, thats what i said before i deleted it.
The reason i deleted it is because if
p|ab, then either;
p|a or,
p|b, or
p|a and p|b

So he assumes the latter in his proof, i dont think thats a problem. However it is something to note Dean if you didnt know that already

Colin Hughes

Posted on Sunday, 23 November, 2003 - 11:28 pm:

It's a brave attempt, Dean, but you've used circular reasoning.

The first line is where your problems start. You can certainly say that if p|ab, then pn=ab. But you cannot maintain that pc=a and pd=b, where c and d are integer. For example, 5|6x10, 5x12=6x10, but 5x1.2=6 and 5x2=10.

If you start with the opposite (or assume that a and b are chosen such that), pc=a and pd=b, hence p|ab, then you have made p² |ab, as ab=p² cd.

I don't see where the problem with the final line comes from too. Just because s and t have no common factors, doesn't mean that the equality, s/t=n/cd, requires n and cd to have no common factors: 2/1=12/6=2. Why should cd and n have no common factors? In fact your fourth line: (p^2)cd = pn, shows that n|cd.

May I suggest you start by assuming that p^1/2 =a/b, where HCF(a,b)=1.

Dean Hanafy

Posted on Monday, 24 November, 2003 - 11:41 am:

Right ok, so my main problem is the fact that p|ab doesn't imply p|a AND p|b? Where will i find a contradiction then in order to prove what i want? I want basically to arrive at a contradiction in a similar way as in a proof that square root of 2 is irrational, but more generally for a prime. Any hints on how to do this?

Colin: is it implicit in your assumption that p is prime?

Thanks
Dean

Andre Rzym

Posted on Monday, 24 November, 2003 - 12:24 pm:

Dean,

Start with p^1/2 =a/b and a,b have no common factors, and assume that p is prime. Try to argue that a must have a factor of p, and thence that b must have a factor of p, which contradicts the 'no common factor' assumption.

Andre

Dean Hanafy

Posted on Monday, 24 November, 2003 - 06:51 pm:

Ok, i refined the proof to the following

Let P^1/2 = a/b where a and b have no common factor and p is prime then we have

p = (a/b)^2

pb^2 = a^2

which implies p|a^2

i.e. p|a x a, which implies p|a or p|a

Now since p|a then a= pc for some c

so pb^2 = a^2

pb^2=p^2.c^2

b^2 =pc^2

which implies p|b^2 which implies p|b

which shows that both b and a have a common factor which is a contradiction. Therefore p^1/2 must be irrational

Does this seem more valid?

Dean

Andre Rzym

Posted on Monday, 24 November, 2003 - 07:07 pm:

It looks good to me. You might also have a look here

Andre

Michael Doré

Posted on Monday, 24 November, 2003 - 07:24 pm:

There's another nice proof, involving some analysis. We show that if x is an integer then x is a perfect square or sqrt(x) is irrational.

Suppose x is not a perfect square, so sqrt(x) is not an integer. Then there exists an integer k such that:

0 < sqrt(x) - k < 1

Consider raising both sides to the power n. By the binomial theorem (sqrt(x) - k)ⁿ = a_n sqrt(x) + b_n for some integers a_n ,b_n . Now if sqrt(x) is irrational then sqrt(x) = p/q with p,q integers and q > 0.

Then (sqrt(x) - k)ⁿ = (a_n p + b_n q)/q. But the left hand side is positive. Therefore a_n p + b_n q must be positive. But it is an integer, therefore it is > = 1.

Hence: (sqrt(x) - k)ⁿ > = 1/q for all n.

However since 0 < sqrt(x) - k < 1, (sqrt(x) - k)ⁿ -> 0 as n -> infinity which is a contradiction.

The same method can easily be extended to show that if P is a monic polynomial with integer coefficients, and P(x) = 0 then x is either an integer or irrational.

Michael

Arun Iyer

Posted on Monday, 24 November, 2003 - 07:31 pm:

Quote :
"Now if sqrt(x) is irrational then sqrt(x) = p/q with p,q integers and q > 0."

hmm it should be sqrt(x) is rational or sqrt(x) is not irrational.
( excuse my nitpicking, just trying to be overly smart)

love arun

James

Posted on Monday, 24 November, 2003 - 08:01 pm:

If a polynominal is monic, does it mean that the roots are all integers or all irrational, ie. theres not a mix? I presume this is what you mean but i just want to make it clear.

Andre Rzym

Posted on Monday, 24 November, 2003 - 08:07 pm:

Well firstly, monic just means that the coefficient of the highest power of

x

is 1.

If the other coefficients are also integers, then the roots are either integers or irrationals, or a mixture of both.

As an example of the latter, consider expanding out:

$(x - 1) (x - \sqrt{2}) (x + \sqrt{2}) = 0$

Andre

James

Posted on Monday, 24 November, 2003 - 08:26 pm:

Oh i see now. I was being a bit stupid...I forgot about the existance of non-integer rational numbers.

Thanks

Marcos

Posted on Tuesday, 25 November, 2003 - 06:19 am:

You can also do it using the fundamental theorem of arithmetic. We aim to show

\sqrt{x}

is either an integer or irrational. If

x

is a perfect square then its square root is (by definition) and integer.

So, suppose $x$ isn't a perfect square. Thus it must contain at least one prime factor an odd number of times, call it $p$ .

Now, assume $\sqrt{x} = a / b$ where $a$ and $b$ are integers. Therefore $a^{2} = x b^{2}$ . But, $p$ will appear in both $a^{2}$ and $b^{2}$ an even number of times, and hence will appear an odd number of times in $x b^{2}$ . By the FTA, this is a contradiction.
(I hope I haven't assumed anything I wasn't meant to in that proof)

Marcos

Marcos

Posted on Tuesday, 25 November, 2003 - 06:21 am:

I've just noticed that this is practically the same as Andre's and mine can be extended in the same way for monic polynomials... Oh well...

Andre Rzym

Posted on Tuesday, 25 November, 2003 - 07:33 pm:

Apart from Michael's proof, and the one based on the Fundamental Theorem of Arithmetic, the irrationality of

\sqrt{n}

(if not an integer) can also be derived through continued fractions:

(i) Show that the continued fraction of a positive real is unique

(ii) Show that the continued fraction expansion for $a / b$ (where $a$ , $b$ are positive integers) terminates

(iii) Show that the continued fraction for $\sqrt{n}$ does not terminate (in fact it is periodic).

Thus $\sqrt{n}$ cannot be equal to $a / b$ .

Of the three proofs, this one is probably the most trouble, however there are additional prizes to be hard. For example, we can write $e$ as a simple continued fraction (where the constants follow the pattern [1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ..]). This immediately shows $e$ to be irrational.

Andre

Michael Doré

Posted on Wednesday, 26 November, 2003 - 02:00 pm:

Thanks for the correction Arun. Also: I said "consider raising both sides to the power n" when I really meant just "consider raising sqrt(x)-k to the power n".

Arun Iyer

Posted on Wednesday, 26 November, 2003 - 06:30 pm:

Andre,
how does one start with (iii)?

Michael,
i understand. it pretty much happens with me always. In some earlier post i typed in "thinks" instead of "things".(dunno what i was "think"ing then)

love arun

Andre Rzym

Posted on Thursday, 27 November, 2003 - 11:53 am:

Arun,

According to Davenport (The Higher Arithmetic), the theorem that "any quadratic irrational number has a continued fraction which is periodic after a certain stage" was first proved by Lagrange in 1700. You can find a proof in either Davenport or Hardy (Introduction to the theory of numbers). I can write it out if you wish but it's a bit long ...

Andre

Arun Iyer

Posted on Thursday, 27 November, 2003 - 12:02 pm:

Andre,
if its long then i will ask this problem after i am through with my exams. I don't think i am in any mood to understand big long proofs during my EPL(exam preparation leave).

Anyways, Thanks!

love arun