# Dividing Squares Fails to Invoke Contradiction: Two Elementary Divisibility Proofs

$x^2 \text{ is even } \iff x \text{ is even } \tag{Thm 3.12, P76}$ $\text{ Let } x, y \in \mathbb{Z}. \text{ Then } x \;\& \; y \text{ are of the same parity } \iff x + y \text{ is even.} \tag{Thm 3.16, P80}$ $\text{ Let } x, y \in \mathbb{Z}. \text{ Then } xy \text{ is even } \iff x \text{ is even or } y \text{ is even.}\tag{Thm 3.17, P81}$

Result 5.14: For every integer $m$ such that $2 \mid m$ and $4 \require{enclose} \enclose{updiagonalstrike}{\mid} m$, $\require{enclose} \enclose{updiagonalstrike}{\exists} x$ and $y \; \ni \;$ $x^2 + 3y^2 = m.$

Solution's Proof by Contradiction: Since $m$ is even, thus by Theorem 3.16, $x^2$ and $3y^2$ are of the same parity. Thus, there are 2 cases. Case 1 is when $x^2$ and $3y^2$ are even; Case 2 when $x^2$ and $3y^2$ are odd. [The issue in both cases seem analogous; I present only Case 2]

$\bbox[5px,border:2px solid grey]{\text{Case 2 of 2:$x^2$and$3y^2$are odd}}$ By the contrapositive of Thm 3.17,
$3y^2$ odd $\iff 3$ odd $\color{green}{AND} \; y^2$ odd. $\color{purple}{\bigstar}$
By the negation of Thm 3.12, $j^2$ odd $\iff j$ odd for both $j = x, y$.
Thus, $\exists \;c, d \in \mathbb{Z} \ni m = (2c + 1)^2 + 3(2d + 1)^2 = 4\underbrace{(a^2 + a + 3b^2 + 3b + 1)}_{\in \mathbb{Z}} \Longrightarrow 4|m. \Rightarrow\Leftarrow$

My Attempt for Case 2 I sheer away after $\color{purple}{\bigstar}$. Since $x^2, y^2$ odd,
thus $\exists \;k, p \in \mathbb{Z} \; \ni \; x^2 = 2k + 1 \; \& \; y^2 = 2p + 1$. Then, $m = 2(k + 3p + 2).$
Since $(k + 3p + 2) \in \mathbb{Z}$ thus $2 \mid m$. NOT a contradiction.

Problem 5.41: Prove that there do not exist positive integers $a$ and $n$ such that $a^2 + 3 = 3^n$.

Solution's Proof by Contradiction: $\bbox[5px,border:2px solid grey]{\text{Case 1:$n = 1$}}$ Then $a^2 = 0$ contradicts the hypothesis that $a \in \mathbb{N}$.

$\bbox[5px,border:2px solid grey]{\text{Case 2:$n \geq 2$}}$ Then $a^2 = 3 - 3^n \Longrightarrow a^2 = 3(3^{n = 1} - 1) \Longrightarrow 3|a^2 \; \color{#0073CF}{\bigstar}$ $\Longrightarrow 3|a \Longrightarrow ... \text{ Steps omitted } ... \Longrightarrow 9|3.$ Contradiction.

My Attempt: I veer away from the solution after $\color{#0073CF}{\bigstar}$. $3|a^2$ means $a^2 = 3k$ for some integer $k$. Then $a^2 + 3^n = 3 \Longrightarrow 3k + 3^n = 3 \Longrightarrow 3(k + 3^{n - 1}) = 3 \Longrightarrow 3|3$. NOT a contradiction.

How and why did my attempts flop? It seems due to working with the squares in both questions?

Source: Result 5.14, P114 & Problem 5.41, P125 of Mathematical Proofs, 2nd ed. by Chartrand et al

-
Because what has to be used is something stronger than just what Thm. 3.12 gives you, namely that the square of an even integer is divisible by $4$, and that the square of an odd integer is $\equiv 1 \pmod{4}$. –  Daniel Fischer Sep 4 '13 at 12:12
@DanielFischer: Thank you for your comment. Nevertheless, I still don't savvy what in my attempts would progonosticate its failure? What in my attempts would prod me to wise up to divisibility by 4 instead of 2? –  LePressentiment Sep 6 '13 at 9:35

The problem with your proofs is that you remove the effect of being squared by treating the square as an ordinary natural number. The behavior of squares are different from the behavior of ordinary natural number. For instance, since $(2k + 1)^2 \equiv 1 \pmod 4$, thus for odd $x$, $x^2 \equiv 1 \pmod 4$ which is not true for any odd $x$.
Indeed, suppose you could prove that $x^2 + 3y^2 = m$ has no solution only using $x^2=2k+1$ and $y^2=2p+1$ and without using squares. Then by setting $u = x^2, v = y^2$, you could prove that $u+3v=m$ for $u,v$ odd does not admit any solution either. Being squared, is an essential part of assumptions. The same is true for your second solution. By assuming $a^2=3k$ you do not take into account that if $3|a^2$ then $9|a^2$ which is more powerful.
Thank you. I upvoted. $\Large{\text{1.}}$ Could you please elucidate on what do you mean by "simple odd $x$"? $\quad \Large{\text{2.}}$ What would be the overarching lesson(s) from these two examples? On the condition that $d \mid x^2 \implies d \mid x$, always proceed with $d \mid x \iff dk = x \Longrightarrow d(dk^2) = x^2$? Anything else more catholic? –  LePressentiment Sep 10 '13 at 1:11
If $d$ is not prime, you cannot deduce from $d \mid x^2$ that $d^2 \mid x^2$. We know that the exponent of primes in factorization of $x^2$ should be even. –  Arash Sep 10 '13 at 7:16
By "simple odd", I meant "odd". Nothing fancy!. Regarding the elucidation, for instance, if $x=2$ and $d=4$, then $d|x^2$ but $d^2=16$ cannot be a divisor of $x^2=4$. By prime factorization, I meant that each natural number $x$ can be written as $x=p_1^{\alpha_1}...p_k^{\alpha_k}$ where $p_i$ is a prime number. Hence $x^2=p_1^{2\alpha_1}...p_k^{2\alpha_k}$ which means that the power of primes in the factorization of $x^2$ should be even. So if $d$ is a prime and $d|x^2$ then we can say $d^2|x^2$. –  Arash Sep 11 '13 at 8:16
Even more if $d$ can be factorized as $p_1^{\beta_1}...p_k^{\beta_k}q_1^{\alpha_1}...q_k^{\alpha_k}$ where $\beta_i$'s are odd and $\alpha_i$'s are even and $d|x^2$, you can say $d'=p_1^{\beta_1+1}...p_k^{\beta_k+1}q_1^{\alpha_1}...q_k^{\alpha_k}$ is also a divisor of $x^2$. –  Arash Sep 11 '13 at 8:21
$\Large{\text{3.}}$ Thank you. My question remains though. From your comment on Sep 12: If $d$ prime and $d \mid \color{#B87333}{x^2}$, then $d^2 \mid \color{#B87333}{x^2}$. Now, $$d \mid {\color{#B87333}{x^2}} \text{ means } \exists \, k \in \mathbb{Z} \; \ni \; dk = \color{#B87333}{p_1^{2\alpha_1}...p_k^{2\alpha_k}}$$. $$\text{So } d^2 \mid {\color{#B87333}{x^2}} \text { means } \exists \, k \in \mathbb{Z} \; \ni \; d^2(k^2) = \color{#B87333}{p_1^{2\alpha_1}...p_k^{2\alpha_k}}$$ How and why do these equations divulge that a necessary condition (in your comment) is that $d$ is prime? –  LePressentiment Sep 14 '13 at 7:25