Proving the irrationality of $\sqrt{5}$: if $5$ divides $x^2$, then $5$ divides $x$

Question

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$

Answer 1

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$.

Answer 2

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$.

Answer 3

$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$.

Answer 4

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.

Answer 5

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.

Answer 6

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$.