# When a prime number p divides $ab$ then we have either p divides a or p divides b.Prove that $\sqrt {p}$ is not rational for any prime number p.

When a prime number $p$ divides $ab$ then we have either $p$ divides $a$ or $p$ divides $b$. Prove that $\sqrt p$ is not rational for any prime number $p$.

-
I think OP meant to use Euclide's Lemma, not prove it. –  Ittay Weiss Mar 4 '13 at 7:52
@gnometorule only if my interpretation is correct ;) –  Ittay Weiss Mar 4 '13 at 7:55

Assume that $\sqrt p=\frac{s}{t}$, with $gcd(s,t)=1$. Then $pt^2=s^2$ and thus $p$ divides the right hand side (since it clearly divides the left hand side), so $p$ divides $s^2$. Using Euclid's lemma it follows that $p$ divides $s$. Write $s=pk$, and thus $pt^2=p^2k^2$. Divide by $p$ to obtain $t^2=pk^2$. Now $p$ divides the right hand side, so it also divides $t^2$. Euclid's lemma again shows that $p$ divides $t$, but this is a contradiction since we assumed $gcd(s,t)=1$. QED.

-

By induction, the given Prime Divisor Property (PDP):  prime $\rm\,p\,$ divides $\rm\,ab\,\Rightarrow\, p\,$ divides $\rm\,a\,$ or $\rm\,b\,$ generalizes to $\,\rm\color{blue}{PDP^*}$:  if a prime divides a product then it divides some factor.

If $\rm\, \sqrt{p}\, =\, r\,$ is rational then the polynomial $\rm\:x^2\! - p\:$ has a rational root $\rm\,x = r.\,$ Thus, by the Lemma below, the root is an integer $\rm\, x = n,\,$ hence $\rm\: p = x^2 = n^2,\:$ contra $\rm\,p\,$ is prime. $\ \$ QED

Lemma $\$ A rational root of $\rm\,f(x) = x^n\! + c_{n-1}x^{n-1}\!+\cdots+c_0\,$ is an integer, if all $\rm\,c_i$ are integers.

Proof $\$ Suppose $\rm\:f(a/b) = 0.\:$ Wlog $\rm\:b>0\:$ and $\rm\:a/b\:$ is in least terms, so $\rm\:gcd(a,b)=1.\,$ Then $$\rm\: 0\, =\, b^n f(a/b) =\, a^n + c_{n-1} a^{n-1}\color{#C00}b+c_{n-2} a^{n-2} \color{#C00}{b^2} +\cdots+c_1 a\, \color{#C00}{b^{n-1}}\! + c_0 \color{#C00}{b^n}\:$$ If $\rm\:b>1\:$ then it has a prime factor $\rm\:p.\:$ Above, $\rm\,p\,$ divides the LHS $= 0,$ so it also divides the RHS. Since $\rm\,p\,$ divides $\rm\,\color{#C00}b\,$ it divides $\rm\,\color{#C00}{b^2,b^3,\ldots}\,$ so $\rm\,p\,$ divides all $\rm\color{#C00}{terms}$ after the first on the RHS, therefore $\rm\,p\,$ must also divide the first term $\rm\:a^n.\,$ Therefore, by $\rm\color{blue}{PDP^*}$, $\rm\,p\,$ divides $\rm\,a,\,$ contra $\rm\:gcd(a,b)=1.\:$ Thus $\rm\,b>1\,$ is impossible, so, since $\rm\,b>0,\,$ we infer $\rm\,b = 1,\:$ hence $\rm\, a/b\,$ is an integer. $\ \$ QED

Remark $\$ The Lemma is a special case of the well-known Rational Root Test, namely, the case where the polynomial is monic, i.e. it has leading coefficient $= 1.$ The proof easily extends to the general result: the denominator $\rm\,b\,$ divides the leading coefficient $\rm\,c_n,\,$ if $\rm\,a/b\,$ is in least terms.

-

Assume that $\sqrt p$ is a rational number $r/s$. We may assume that $r$ and $s$ are relatively prime integers.

Then we have $p=r^2/s^2$. Since $p$ is an integer and $r$ and $s$ are relatively prime, $s=1$ or $s=-1$. Then $p=r^2$.

But this contradicts that $p$ is a prime number.

-
This proof is incorrect. –  Ittay Weiss Mar 4 '13 at 7:40
@IttayWeiss What is wrong with it? –  Ragib Zaman Mar 4 '13 at 7:45
@IttayWeiss Why?? Maybe I should have said that $s^2p=r^2$ and $p$ divides $r$. Then we see $p$ divides $s$. This contradicts the assumption that $r$ and $s$ are relatively prime. –  Primo Mar 4 '13 at 7:46
@Primo yes, since OP was looking for a solution using Euclid's lemma, I think these things need to be spelled out (or at least pointed out). And when I remarked the proof is wrong, I should have said 'incomplete', I'm sorry. –  Ittay Weiss Mar 4 '13 at 7:52
Your argument seems to implicity use: $\, r,s\,$ coprime $\,\Rightarrow\ r^2,s^2\,$ coprime. That should be explicitly mentioned, and, more importantly, justified. –  Math Gems Mar 4 '13 at 17:41