Consider the following statement:
For all $n\in\mathbb{Z}$, if $n^2$ is a multiple of 3, then $n$ is a multiple of $3$.
- Prove this statement by the contrapositive.
So my answer for question 1 would be:
For all $n\in\mathbb{Z}$, if $n^2$ is not a multiple of $3$, then $n$ is not a multiple of $3$.
Consider the following proof:
Proof:
(1) Let $n^2$ be a multiple of $3$.
(2) Then $n^2 = 3q$ for some integer $q$.
(3) By uniqueness of prime factorization, $3$ is in the prime factorization of $n^2$.
(4) Suppose $3$ is not in the prime factorization of $n$ and let $p_1,\ldots,p_s$ be the prime decomposition of $n$.
(5) Then $n^2=p_1p_1\ldots p_sp_s$ but $3\neq p_i$ for all $i\in\{1,\ldots,s\}$, contradiction. QED
2a. What is the contradiction that arises in the proof?
2b. Why the uniqueness of prime factorization allows us to claim in (3) that $3$ is in the prime factorization of $n^2$?
- Write a direct proof of the theorem.
Thanks for the help in advance.