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

1,260

## Solution 1

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.

## Solution 2

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.

Share:
1,260

Author by

### Man

Updated on March 05, 2020

• Man over 3 years

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

• Ittay Weiss over 10 years
I think OP meant to use Euclide's Lemma, not prove it.
• Ittay Weiss over 10 years
@gnometorule only if my interpretation is correct ;)
• Ittay Weiss over 10 years
This proof is incorrect.
• Ragib Zaman over 10 years
@IttayWeiss What is wrong with it?
• thebooort over 10 years
@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.
• Ittay Weiss over 10 years
@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.
• Math Gems over 10 years
Your argument seems to implicity use: $\, r,s\,$ coprime $\,\Rightarrow\ r^2,s^2\,$ coprime. That should be explicitly mentioned, and, more importantly, justified.
• thebooort over 10 years
@MathGems Yes. I didn't give him every detail.
• Math Gems over 10 years
@Primo But that detail is essential in a proof like this, since many students mistakenly believe it to be true for incorrect reasons (or, worse, don't even realize that it needs proof). It and related aspects of unique factorization are the biggest source of errors in elementary number theory.
• thebooort over 10 years
@MathGems You are right. But I didn't think that it is a good idea to give him a full detailed answer. It's just my opinion.