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.
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_{n1}x^{n1}\!+\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_{n1} a^{n1}\color{#C00}b+c_{n2} a^{n2} \color{#C00}{b^2} +\cdots+c_1 a\, \color{#C00}{b^{n1}}\! + 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 wellknown 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.
Related videos on Youtube
Man
Updated on March 05, 2020Comments

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 yearsI 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 yearsThis 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 yearsYour 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.