2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Your question is unclear. What do you mean by "how do you prove the square root of 3 using the fundamental theorem of arithmetic?" $\endgroup$ – Mark Fantini Mar 15 '15 at 18:12
  • 3
    $\begingroup$ Are the words "is irrational" supposed to be in here somewhere? $\endgroup$ – Chappers Mar 15 '15 at 18:12
  • $\begingroup$ Yeah the question was: Show that square root of 3 is irrational using the Fundamental Theorem of Arithmatics. $\endgroup$ – Kagamine Len Mar 15 '15 at 18:14
  • $\begingroup$ Next step: Then $a^2 = 3b^2$, which means that $3 \mid a$... $\endgroup$ – Joffan Mar 15 '15 at 18:17
  • $\begingroup$ Square you equality, and suppose $a,b$ have no common factor, then use the Fundamental Theorem. $\endgroup$ – Bernard Mar 15 '15 at 18:17
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The OP is required to use FTA, so you should explicitly mention it when you use it above. $\endgroup$ – Bill Dubuque Mar 15 '15 at 18:58
  • $\begingroup$ @BillDubuque, I have edited my answer. It'd be great if you could verify it. Thanks in advance! $\endgroup$ – Prasun Biswas Mar 15 '15 at 19:41
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't get the hint. $\endgroup$ – Kagamine Len Mar 15 '15 at 18:26
  • $\begingroup$ @KagamineLen: by the FTA, suppose $3^{\alpha}\mid a$, and $3^{\beta}\mid b$. Then by the uniqueness of prime factorization guaranteed by the FTA, we have $2\alpha + 1 = 2\beta$. Do you see why? If so, why is this a problem? $\endgroup$ – Alex Wertheim Mar 15 '15 at 18:28
  • $\begingroup$ I see it now. Because p has a factorization of 3 times, but it should only factor once. $\endgroup$ – Kagamine Len Mar 15 '15 at 18:30
  • $\begingroup$ Hmmm? Are you sure you see? It's a parity argument. $3$ must divide $a$ an even number of times, but must divide $3b^{2}$ an odd number of times. This can't be so if they're equal. $\endgroup$ – Alex Wertheim Mar 15 '15 at 18:31
  • $\begingroup$ I don't see it. Like how did you get 2a = 2b+1 $\endgroup$ – Kagamine Len Mar 15 '15 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.