Let q be a positive integer such that $q \geq 2$ and such that for any integers a and b, if $q|ab$, then $q|a$ or $q|b$. Show that $\sqrt{q}$ is irrational.


Let assume $\sqrt{q}$ is a rational number, where $n \neq 0$ and $\gcd (m,n)=1$, meaning $\sqrt{q} = \frac{m}{n} \Rightarrow q=\frac{m^2}{n^2} $

Since $n^2 \nmid m^2$, $q|m^2 \Rightarrow q|m$, so $m=qt$ where $t\in \mathbb{Z}$

By substitute $m=qt$ in the equation $qn^2 = m^2$, we get $n^2=qt^2$.

Since tells us that $q|n^2$ and $t^2|n^2$, it contradicts with the assumption $\gcd (m,n)=1$; therefore, $\sqrt{q}$ is irrational.

I get this proof with the assistant of the course, but is there any flaw or mistake? What are the other methods for proving this statement, can you at least give one different method? And how can I improve this proof?

  • $\begingroup$ What would it mean to "improve" the proof? $\endgroup$ – AJY Oct 26 '16 at 16:18
  • $\begingroup$ @AJY In the way that I wrote the proof. $\endgroup$ – onurcanbektas Oct 26 '16 at 16:20
  • $\begingroup$ What about $q=a=4$, $b=2$? $\endgroup$ – jacer21 Oct 26 '16 at 16:20
  • $\begingroup$ @jacer21, $q$ is explicitly assumed to be prime. $\endgroup$ – Ennar Oct 26 '16 at 16:21
  • 1
    $\begingroup$ @Leth, this is completely irrelevant, the statement is true. I was just addressing jacer21 as he tried to make counterexample to the claim by using that $\sqrt 4$ is not irrational. This counterexample doesn't work since $q$ must be prime by explicit assumption, and $4$ is not prime. I've given you links since you asked me about it, but as I said, it is completely irrelevant for the proof you gave, which looks ok. $\endgroup$ – Ennar Oct 26 '16 at 16:38

Proof using Bézout's Identity

For $\sqrt{q}$ to be irrational, $q$ must not be a perfect square. Thus, we only concern us with non-perfect square $q$.

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

By Bézout's Identity, there exist integers $x$ and $y$ such that $mx + ny = 1$

Now $\sqrt{q} = \sqrt{q}(1) = \sqrt{q}(mx + ny) = (\sqrt{q}m)x + (\sqrt{q}n)y = qnx + my = \text{an integer}$

Which leads us to a contradiction, since we initially assumed that $q$ wasn't a perfect square. Hence, $\sqrt{q}$ is irrational.

  • $\begingroup$ I did not understand the part $(\sqrt{q}m)x + (\sqrt{q}n)y = qnx + my$ $\endgroup$ – onurcanbektas Oct 26 '16 at 16:41
  • 1
    $\begingroup$ Notice that from our initial assumption we get $m = \sqrt{q} n$ $\endgroup$ – jskmr Oct 26 '16 at 16:43
  • 1
    $\begingroup$ @Leth See also this answer, which explains how to view such Bezout-based proofs as descent on denominators. See also many other proofs in that thread. $\endgroup$ – Bill Dubuque Oct 26 '16 at 20:18

We just have to show that for any prime number $p$, $\sqrt{p}\not\in\mathbb{Q}$.
If we assume $\sqrt{p}=\frac{a}{b}$ with $a,b\in\mathbb{Z}^+$ we get the identity $pb^2=a^2$.
For any $n\in\mathbb{Z}^+$, let $\nu_p(n)=\max\{m\in\mathbb{N}: p^m\mid n\}$. The identity $pb^2=a^2$ implies $$ \nu_p(pb^2) = \nu_p(a^2) $$ but that is impossible, since $\nu_p(a^2)$ is an even number and $\nu_p(pb^2)=1+\nu_p(b^2)$ is an odd number. $\sqrt{p}\not\in\mathbb{Q}$ trivially follows.

  • $\begingroup$ why just the odd numbers ? $\endgroup$ – onurcanbektas Oct 27 '16 at 4:40
  • $\begingroup$ @Leth: I misread "for any $q\color{red}{>}2$ such that $\ldots$" in the main question, now fixed. It is not really relevant, indeed. $\endgroup$ – Jack D'Aurizio Oct 27 '16 at 5:10
  • $\begingroup$ but I still don't understand why the p is prime.Above Ennar gave some info about it, but it is about something that I haven't studied. $\endgroup$ – onurcanbektas Oct 27 '16 at 9:18
  • $\begingroup$ @Leth: $$q\mid(ab)\implies q\mid a\text{ xor } q\mid b$$ is the very definition of prime. As an alternative, it is easy to show that only prime numbers (by your current definition) may have such property. $\endgroup$ – Jack D'Aurizio Oct 27 '16 at 9:20
  • 1
    $\begingroup$ @Leth: en.wikipedia.org/wiki/Prime_element $\endgroup$ – Jack D'Aurizio Oct 27 '16 at 15:18

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.