# Problem

Let $$n$$ be a positive integer and not a perfect square. Prove $$\sqrt{n}$$ is irrational.

# Proof

Consider proving by contradiction. If $$\sqrt{n}$$ is rational, then there exist two coprime integers $$p,q$$ such that $$\sqrt{n}=\frac{p}{q},$$ which implies $$p^2=nq^2.$$ Moreover, since $$p, q$$ are coprime, by Bézout's theorem, there exist two integers $$a,b$$ such that $$ap+bq=1.$$ Thus $$p=ap^2+bpq=anq^2+bpq=(anq+bp)q,$$ which implies $$\sqrt{n}=\frac{p}{q}=anq+bp \in \mathbb{N^+},$$ which contradicts.

• The conclusion needs some work. You don't specify why this is a contradiction and you don't mention the case where it isn't a contradiction which is when $n$ is a perfect square. – Winther Apr 19 at 14:04
• Why not simply count prime factors? If $n$ isn't perfect square there must be a prime factor $r$ of $n$ which occurs in an odd power. Hence -- using the above notation -- $p^2=n\cdot q^2$. Occurrence on the lhs of $r$ is even whereas on the rhs it's odd. – Michael Hoppe Apr 19 at 14:22
• Please see my "Problem"... – mengdie1982 Apr 19 at 14:36
• @mengdie1982 The point is that you don't mention it in the actual proof so it's not explicit that you are considering the case that $n$ is not a perfect square. This is a detail, but it's always a good idea to be very clear about what you are assuming. – Winther Apr 19 at 17:07

It is fine.

I would perhaps just note that the equality $$p=(anq+bp)q$$ goes against the hypothesis that $$p$$ and $$q$$ are coprime, unless $$q=1$$, in which case $$\sqrt n=p\in\mathbb Z$$. But that is just a matter of taste.

• I don't agree it's a matter of taste. If one is to give a proof of such a basic statement, for which an important lesson is to for the student to learn how to present a rigorous proof, then it should be done properly. IMO what you mention here should be included in the proof otherwise it's incomplete. As written OPs proof seem to indicate that it would be a contradiction even when $n$ is a perfect square as this special case is not mentioned at all. – Winther Apr 19 at 14:09
• @Winther In my opinion, the OP just forgot to add the words “the hypothesis that $n$ is not a perfect square” at the end of the proof. – José Carlos Santos Apr 19 at 14:12
• Please see my "Problem"... – mengdie1982 Apr 19 at 14:36

At this level, one should be more explicit about how the contradiction is obtained, i.e. the final equation contradicts the hypothesis that $$n$$ is a perfect square. That done the proof is correct.

The proof essentially repeats inline the following Bezout-based proof of Euclid's Lemma (for $$\,k = p)$$. Generally it is better to invoke the Lemma by name (Euclid's Lemma) rather than repeat its proof inline, i.e. in your proof you could write $$\,\gcd(p,q)=1,\ q\mid p^2\,\Rightarrow\, q\mid p\,$$ by Euclid's Lemma.

Euclid's Lemma $$\ \gcd(p,q) = 1,\,\ q\mid p k\,\Rightarrow\, q\mid k$$

Proof $$\,\ q\mid pk,qk\, \Rightarrow\, q\mid (ap\!+\!bq)k = k,\,$$ where $$\,ap\!+\!bq = 1\,$$ by Bezout.

Remark  See here for a simple Bezout based proof that generalizes to higher-degree roots and arbitrary algebraic integers {i.e. monic case [lead coeff $$=1]$$ of Rational Root Test). It uses Bezout to reduce the degree of the monic polynomial of which the number is a root, so we eventually reach a linear monic $$\,x - n,\,$$ so $$\,x = n\,$$ is an integer.

Proof by contradiction is not needed. It suffices to "take the contrapositive". This is when you switch the antecedent and the conclusion of an implication and negate them. Formally, it looks like this:

$$P \implies Q \text{ has the contrapositive } \neg Q \implies \neg P$$

It applies to the proof in the following way. Your argument shows that if $$\sqrt{n}$$ is rational, then it must be an integer. But if $$\sqrt{n}$$ is an integer, then $$n$$ must be a perfect square.

This means that if $$n$$ is not a perfect square, then $$\sqrt{n}$$ is not an integer, so $$\sqrt{n}$$ is not rational. Q.E.D.