Follow-up Question: Proof of Irrationality of $\sqrt{3}$ As a follow-up to this question, I noticed that the proof used the fact that $p$ and $q$ were "even". Clearly, when replacing factors of $2$ with factors of $3$ everything does not simply come down to being "even" or "odd", so how could I go about proving that $\sqrt{3}$ is irrational?
 A: It's very simple, actually.
Assume that $\sqrt{3}$ = $\frac{p}{q}$, with $p,q$ coprime integers.
Then, $p = \sqrt{3}q$ and $p^2 = 3q^2$. If $3\mid p^2$, then $3\mid p$. So actually, $9\mid p^2$. Then, by similar logic, $3\mid q^2$, meaning $3\mid q$. Since $3$ divides both $p$ and $q$, the two numbers are not coprime. This is a contradiction, since we assumed that they $\textbf{were}$ coprime. Therefore, $\sqrt{3}$ cannot be written as a ratio of coprime integers and must be irrational.

$\textbf{NOTE:}$ The word "even" in the original proof was just a substitution for "divisible by $2$". This same idea of divisibility was used in this proof to show that $p$ and $q$ were divisible by $3$. It really is the same idea. There just isn't a nice concise word like "even" that was used to describe a multiple of $3$ in this proof.
A: Alternatively, a contradiction can be derived as follows: $$\begin{align} \sqrt3 &=\frac ab \\ a^2&=3b^2 \\ a^2+b^2 &= 4b^2=(2b)^2 \\ \end{align}$$The contradiction is due to the fact that the integer length of the hypothenuse of a primitive right triangle is odd.
A: Here is a proof that
if $n$ is a positive integer that is
not a square of an integer,
then $\sqrt{n}$ is irrational.
This proof does not use
any divisibility properties.
Let $k$ be such that
$k^2 < n < (k+1)^2$.
Suppose $\sqrt{n}$ is rational.
Then there is a smallest positive integer $q$ such that
$\sqrt{n} = p/q$.
Then $\sqrt{n} = \sqrt{n}\frac{\sqrt{n}-k}{\sqrt{n}-k}
= \frac{n-k\sqrt{n}}{\sqrt{n}-k}
= \frac{n-kp/q}{p/q-k}
= \frac{nq-kp}{p-kq}
$.
Since $k < \sqrt{n} < k+1$,
$k < p/q < k+1$,
or $kq < p < (k+1)q$,
so $0 < p-kq < q$.
We have thus found a representation of
$\sqrt{n}$ with a smaller denominator,
which contradicts the specification of $q$.
Note: This is certainly not original - 
but I had fun working it out
based on the proof I know
that $\sqrt{2}$ is irrational.
A: Here's another way: suppose $\sqrt3 = \frac pq$ for some coprime $p,q$, so
$$3q^2=p^2.$$ Now reduce this modulo $4$, noting that the quadratic residues modulo $4$ are $0$ and $1$. The only solution is $p^2 \equiv q^2 \equiv 0 \pmod 4$, but then $p$ and $q$ are both even, a contradiction.
A: Proof by contradiction
Assume that $\sqrt{3}$ is rational . Then this means that $\sqrt{3} = \frac{p}{q}$ where $p$ and $q \neq 0$ are integers in their lowest terms. That is to say that $\gcd(p,q) =1$
Now square both sides to get $3 = \frac{p^2}{q^2} \implies 3q^2 = p^2$
Now clearly, $3 \mid p^2$ but since $3$ is prime then $3 \mid p$.
This is because of euclid's lemma that states that if $p$ is prime and $p$ divides $ab$ then $p$ divides $a$ or $p$ divides $b$. And so here we have $3 \mid pp = p^2$ and so $3 \mid p$ 
Now $3k = p$ for some integer $k$ right and so $3q^2 = (3k)^2$ and so $3q^2 = 3(3k^2)$ and so $q^2 = 3k^2$ and so $3 \mid q^2$, however $3$ is prime so $3 \mid q$ and so now we have $3 \mid q$ and $3 \mid p$ which contradicts the fact that $\gcd(p,q)=1$ and so our assumption that $\sqrt{3}$ is rational is false and hence it must be irrational 
A: The general case : If $a,b,c,d$ are positive integers with  $GCD(a.b)=1=GCD(c,d)$ then $(a/b)^{c/d}$ is irrational unless $a$ and $b$ are $d$-th powers of positive integers.PROOF: Suppose $(a/b)^{c/d}=e/f$ where $f,g$ are positive integers and $GCD(f,g)=1$. Then $a^cf^d=b^ce^d$. We now apply a result (which one book called the "fundamental theorem of arithmetic"), that if $x,y,z$ are non-zero integers where $x$ divides $yz$ and $GCD(x.y)=1$ then $x$ divides $z$. Firstly, this implies that $GCD(a^c,b^c)=1=GCD(f^d,e^d)$. Secondly, applying the theorem with $x=a^c,y=b^c,z=e^d$, we have: $a^c$ divides $e^d$,but applying it with $x=e^d,y=f^d,z=a^c$, we have: $e^d$ divides $a^c$. So $a^c=e^d$.Now since $a^c.f^d=b^c.e^d$ and $a^c=e^d$, we also have $f^d=b^c$.Finally another consequence of the above theorem is that if $x$ is both a $c$-th power and a $d$-th power with $.GCD(c.d)=1$, then $x$ is a $cd$-th power. Applying this with $x=a^c$,and also with $x=b^c$, we know there are positive integers $u,v$ where $a^c=u^{cd}$ and $.b^c=v^{cd}$. So $a=u^d$ and $b=v^d$. QED.
