314 – On √n

Let’s prove that if n\in\mathbb N, then either \sqrt n is an integer, or else it is irrational. (Cf. Abbott, Understanding analysis, Exercise 1.2.1.) There are many proofs of this fact. I present three.

1.

The standard proof of this fact uses the prime factorization of n: There is a unique way of writing n as \prod_{i=1}^k p_i^{\alpha_i}, where the p_i are distinct primes numbers, and the \alpha_i are positive integers (the number n=1 corresponds to the empty product, but since 1 is a square, we may as well assume in what follows that n>1).

We show that if \sqrt{n} is rational, then in fact each \alpha_i is even, so \sqrt n is actually an integer. Write \sqrt n=a/b where a,b are integers that we may assume relatively prime. This gives us that b^2n=a.

Consider any of the primes p=p_i in the factorization of n. Let p^\beta and p^\gamma be the largest powers of p that divide a and b, respectively, say a=p^\beta c and b=p^\gamma d where p does not divide either of c and d. Similarly, write n=p^{\alpha}m, where p does not divide m (\alpha is what we called \alpha_i above). We have

p^{2\gamma} p^{\alpha}d^2m=p^{2\beta}c^2.

The point is that since p is prime, it does not divide c^2 or d^2m: If q is a prime and q divides a  product hj (where h,j are integers), then q divides h or it divides j.

This means that either \alpha is even (as we wanted to show), so that 2\gamma+\alpha=2\beta, or else (upon dividing both sides of the displayed equation by the smaller of p^{2\gamma+\alpha} and p^{2\beta}), p divides one of the two sides of the resulting equation, but not the other, a contradiction.

2.

The above is the standard proof, but there are other arguments that do not rely on prime factorizations. One I particularly like uses Bézout theorem: If c is the greatest common divisor of the positive integers a and b, then there are integers x,y such that ax+by=c.

Suppose \sqrt n=a/b. We may assume that a,b are relatively prime, and therefore there are integers x,y such that ax+by=1. The key observation is that \sqrt n=n/\sqrt n=nb/a. This, coupled with elementary algebra, verifies that

\displaystyle \sqrt n= \frac ab=\frac{nb}a=\frac {ay+nbx}{by+ax},

but the latter is an integer, and we are done.

3.

Another nice way of arguing, again by contradiction, is as follows: Suppose that \sqrt n is not an integer, but it is rational. There is a unique integer m with m<\sqrt n<m+1, so 0<\sqrt n -m<1. Let a be the least positive integer such that (\sqrt n-m)a is an integer, call it b. Note that 0<b<a, which gives us a contradiction if ({\sqrt n}-m)b is again an integer. But this can be verified by a direct computation:

(\sqrt n-m)b=(\sqrt n-m)^2a=(n+m^2)a-2m\sqrt n a =(n-m^2)a-2m(\sqrt n-m)a.

4.

As a closing remark, the three arguments above generalize to show that \root k\of n is either an integer or irrational, for all positive integers n,k. Similarly, if \displaystyle\root k\of {\frac ab} is rational for some positive integers a,b, then both a,b are kth powers. (It is a useful exercise to see precisely how these generalizations go.)

Pdf source.

About these ads

One Response to 314 – On √n

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 45 other followers

%d bloggers like this: