The irrationality of $\sqrt{3}$ and the fundamental theorem of arithmetic How do you prove the square root of $3$ is irrational by using the Fundamental Theorem of Arithmetic?
We learned proof by contradiction last week but we need to use the Fundamental Theorem to show this instead of using the classical $p \cong q \mod (n)$.
The Fundamental Theorem of Arithmetic:
Every positive integer $n > 1$ can be represented in exactly one way as a product of prime powers:
I started out by using the proof by contradiction but I couldn't get very far.
Suppose $\sqrt3 \in \mathbb{Q}$. Then $\exists a, b \in \mathbb{Z}$ s.t. $\sqrt3 = a/b$.
I couldn't get far.
 A: Hint: if $\sqrt{3}=a/b$ for some $a, b \in \mathbb{Z}$, then $3b^{2} = a^{2}$. Using the fundamental theorem of arithmetic, count how many times $3$ can appear in the factorization of each side.
A: If $\sqrt{3}$ is rational, assume $\sqrt{3}=\dfrac{a}{b}$, where $a,b$ are coprime integers. Then after rearranging and squaring we have,
$3b^2=a^2\qquad\ldots (1)$
By FTA, this implies that $a^2$ is divisible by $3$ and subsequently $a$ is divisible by $3$. Then we have $a=3k$ for some $k\in\mathbb{Z}$. Then, using (1),
$3b^2=(3k)^2\implies 3b^2=9k^2\implies b^2=3k^2$
which implies (again by FTA) that $b^2$ is divisible by $3$, or $b$ is divisible by $3$.
Contradiction! We assumed that $a,b$ are coprime but this shows that they have a common prime factor of $3$.
Therefore, our assumption is wrong and hence $\sqrt{3}$ is irrational.
Note: It can also be seen that since $a,b$ are integers and $a^2,b^2$ must be perfect squares, then by (1) and FTA, $3$ divides $b^2$ an even number of times (because otherwise $b^2$ cannot be a perfect square) while it divides $a^2$ an odd number of times (because in LHS, an extra $3$ is multiplied to $b^2$). But then by equality in (1), it shows that $a^2$ is simultaneously divisible by $3$ odd and even number of times, which is impossible. So, our initial assumption that $\sqrt{3}$ is rational is wrong. As such, $\sqrt{3}$ is irrational.
