2
$\begingroup$

I am working on proving that $\sqrt{5}$ is irrational. I think I have the proof down, there is just one part I am stuck on.

How do I prove that $x^2$ is divisible by 5 then $x$ is also divisible by $5$?

Right now I have $5y^2 = x^2$

I am doing a proof by contradiction, where I show that both x and y are divisible by 5. where $\sqrt{5} = x/y$

$\endgroup$
  • 2
    $\begingroup$ We can quote Euclid's Lemma. Or else we can show by $4$ separate computations that if $x$ has remainder $1,2,3,4$ on division by $5$, then $x^2$ is not divisible by $5$. $\endgroup$ – André Nicolas Oct 17 '14 at 18:35
  • $\begingroup$ What is the most important property of primes? $\endgroup$ – Jacob Bond Oct 17 '14 at 18:36
  • $\begingroup$ Try imitating one of these many proofs for the irrationality of $\sqrt2$. :-$)$ $\endgroup$ – Lucian Oct 18 '14 at 1:46
5
$\begingroup$

We can quote Euclid's Lemma. If the prime $p$ divides the product $ab$, then $p$ divides $a$ or $p$ divides $b$ (or $p$ divides both).

At a more elementary level, we can show by $4$ separate computations that if $x$ has remainder $1,2,3,4$ on division by $5$, then $x^2$ is not divisible by $5$.

For example, if $x$ has remainder $2$ on division by $5$, then $x=5k+2$ for some integer $k$. Then $x^2=25k^2+10k+4=5(5k^2+2k)+4$, so $x^2$ has remainder $4$ on division by $5$, and in particular is not divisible by $5$.

$\endgroup$
  • $\begingroup$ Interesting. Since I haven't proved Euclid's Lemma, I am gonna try the methods you suggested at the end. Thank you very Much. $\endgroup$ – user181506 Oct 17 '14 at 18:44
  • $\begingroup$ Could you do this by induction to generalize it? Like if wanted to do this for $sqrt[23]$ where I show that it doesnt work for n = 1 and then create a generic equation that only works when n = the number you are considering in this 5? or is it not kosher to do induction in side of contradiction? $\endgroup$ – user181506 Oct 17 '14 at 18:52
  • $\begingroup$ Verifying $4$ cases is enough for the prime $5$, and verifying $12$ cases would be enough for the prime $13$. I do not see offhand a simple proof by induction that really avoids proving Euclid's Lemma. $\endgroup$ – André Nicolas Oct 17 '14 at 18:56
  • $\begingroup$ kk, thank you very much! $\endgroup$ – user181506 Oct 17 '14 at 18:58
  • $\begingroup$ You are welcome. The standard proof for $\sqrt{2}$ is similar, we do not have to use euclid's Lemma to prove that if $2$ divides $x^2$ then $2$ divides $x$, all we have to do is to observe that if $x$ is odd (remainder $1$ on division by $2$) then $x^2$ is odd. The calculation for $\sqrt{5}$ is the same, except there are more cases. For the general $\sqrt{p}$, we would need Euclid's Lemma, or a close relative. $\endgroup$ – André Nicolas Oct 17 '14 at 19:04
3
$\begingroup$

Another proof for $\sqrt{n}$: Suppose that $\sqrt{n}$ is rational but not an integer. Let q be the smallest integer such that $q\sqrt{n}$ is an integer. Consider the non-zero integer $$q'=q(\sqrt{n}-[\sqrt{n}])$$ where [ ] denotes the integer part. Then q' is less than q and $q'\sqrt{n}=qn-q\sqrt{n}[\sqrt{n}]$ is an integer, contradicting the assumption of rationality.

$\endgroup$
2
$\begingroup$

Use the fact that $5$ is prime.

If $5$ is not a divisor of $x$, then $5$ does not apper in its factorisation. Then, it doesn't appear in the factorisation of $x^2$.

$\endgroup$
2
$\begingroup$

$5$ appears with odd exponent in the prime factorisation of $5y^2$.

$5$ appears with even exponent in the prime factorisation of $x^2$.

Thus, $5y^2 \ne x^2$.

$\endgroup$
  • $\begingroup$ The same argument works for any $n$ that is not square: just take a prime divisor of $n$ that has odd exponent. $\endgroup$ – lhf Oct 17 '14 at 20:55
1
$\begingroup$

Say we are looking on $\sqrt{n}$ where $n$ is a prime number and we want to show that it is irrational.

Assume that $\sqrt{n}$ is rational, thus we can write $\sqrt{n}=\frac{m}{p}$ where $\gcd(m,p)=1$ and we get $p^2\cdot{n}=m^2$.

We can say that $m^2$ is divisible by $n$ and we want to show that $m$ has to be divisible by $n$.

Let's assume that $m$ has a remainder of $t$ when divided by $n$ (i.e, $m$ is not divisible by $n$), thus $m=n\cdot{k}+t$ where $k\in{\mathbb{N}}$ and $t$ is an integer such that $t\in[1,n-1]$.

If $m=n\cdot{k}+t$ then $m^2=(n\cdot{k}+t)^2=n^2k^2+2nkt+t^2=nk(nk+2t)+t^2$, thus $m^2$ has a remainder of $t^2$ when divided by $n$, hence we got a contradiction.

Conclusion: if $n$ is a prime number and $m^2$ is divisible by $n$, then $m$ is divisible by $n$.

We got that $m$ has to be divisible by $n$, thus $m=n\cdot{k} \rightarrow p^2\cdot{n}=(nk)^2=n^2k^2 \rightarrow p^2=nk^2$.

By the same reasoning we get that $p$ has to be divisible by $n$ $\Rightarrow$ $m$ and $p$ are both divisible by $m$ in contradiction to that $\gcd(m,p)=1$ $\Rightarrow$ $\sqrt{n}$ is irrational.


Now we will prove generally that $\sqrt{n}$ is irrational if $n\ne x^2 \ s.t \ x\in\mathbb{Z}$.

The proof takes $n$ to be an integer bigger than 1. If n is not an integer we can find some q such that $q\cdot{n}$ is an integer and then apply the same proof.

We proved the case that $n$ is a prime, so we assume that $n$ is not a prime.

Assume that $\displaystyle n=\prod_{i}^{k}e_i^{a_i}$ where $e_i$ are prime numbers and $a_i$ are integers. For example $24=2^3\cdot{3}$, so $e_1=2\ , \ e_2=3\ , \ a_1=3\ , \ a_2=1$.

Assume that $\sqrt{n}$ is rational, so $\displaystyle \sqrt{n}=\frac{m}{p}$ where $\gcd(m,p)=1$.

If so, we get $p^2\cdot{n}=m^2$, so $n|m^2$.

We have proved the claim: if $m^2$ is divisible by some prime, then $m$ is also divisible by that prime.

Now, because $n|m^2$ all of the factors of $n$ are factors of $m^2$, $e_i$ are factors of $m^2$ and they are all primes, so they are also factors of $m$.

We can write $e_i|m$ where $i$ is an integer such that $i\in{[1,k]}$.

Now, we may define $\displaystyle m=t\cdot{\prod_{i=1}^{k}e_i}$. Our equation turns out to: $$p^2\cdot{n}=\left(t\prod_{i=1}^{k}e_i \right)^2 \rightarrow p^2\cdot{\prod_{i=1}^{k}e_i^{a_i}}=t^2\cdot{\prod_{i=1}^{k}e_i^2} \Rightarrow p^2 \prod_{i=1}^{k}e_i^{a_i-2}=t^2$$

Now we will take three cases:

  • There are i's such that $a_i=1$ and i's such that $a_i\ge 2$. WLOG we can assume that $a_1=1$ and $a_i \ge 2 \ for \ i\in{[2,k]}$. Now we will get $\displaystyle p^2\prod_{i=2}^{k}e_i^{a_i}=t^2\cdot{e_1}$. We can conclude that $e_1|p^2 \Rightarrow e_1|p$. If so, then $e_1|m$ and $e_1|p \Rightarrow$ contradiction!
  • $\forall i\in{[1,k]}: \ a_i=2$, so we get $p^2=t^2 \rightarrow p=t \rightarrow p|m$ which is true iff $p=1$. We will go back to this one.
  • $\forall i\in{[1,k]}: \ a_i>2$. In this case the equation is the same. We can write that $\forall i\in{[1,k]}: \ e_i|t^2 \rightarrow e_i|t$. We can iterate these steps and after $x$ iterations we will get the equation $\displaystyle p^2\prod_{i=1}^{k}e_i^{a_1-2x}=v^2$ which matches one of the two first cases.

We still didn't finish with the second case. We found that $p|m$ and because $\gcd(m,p)=1$ it can be true iff $p=1$. If $p=1$, then the equation becomes $n=m^2$, but $n \ne x^2 \ s.t \ x\in\mathbb{Z}$, thus we got a contradiction.

Conclusion: if $n$ is not a squared number, then $\sqrt{n}$ is irrational.

$\endgroup$
1
$\begingroup$

The following argument displaces the focus a bit away from $\sqrt5$ itself.

The discriminant of the quadratic polynomial $P=X^2-X-1$ is$~5$, so if $\sqrt5$ were rational, then so would the roots of$~P$ (as it has integer coefficients). Let $\phi$ be the positive root of$~P$ (it is the golden ratio $\frac{1+\sqrt5}2$); by definition it satisfies $\phi^2-\phi=1$ from which follows easily $\phi=\frac1{\phi-1}$. Now writing $\phi=\frac pq$ as a positive integer fraction in lowest terms (with clearly $p>q$), this equation gives $\phi=\frac1{\phi-1}=\frac 1{(p-q)/q}=\frac q{p-q}$ another positive integer fraction for$~\phi$ in ever lower terms, which is a contradiction.

The underlying idea here is to try to apply Euclid's algorithm to a ratio $a:b$ of positive real numbers to find a least common divisor of $a$ and $b$, and thereby express the ratio as a rational number. If along the way one encounters a fraction that was already seen before, this shows the process runs in a loop and therefore cannot terminate (of course it is also possible that the process fails to terminate without ever encountering a previous ratio). This periodicity happens ultimately for all quadratic irrationals, but most obviously so (with a period consisting of one step with a single subtraction) for the golden ration $\phi:1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.