# Show that $a \equiv \pm 3\pmod 8$ is $a^2 \equiv 9 \pmod {16}$.

Show that $a \equiv \pm 3 \pmod 8$ is $a^2 \equiv 9 \pmod {16}$.

My attempt is incomplete:
$a \equiv \pm 3 \pmod 8 \implies (a \equiv 3 \pmod 8) \cup (a \equiv - 3 \pmod 8)$
It is possible to take only one value, not both if the modulus is the same, for a given value $a$. The reason for the given example, considering both as possible would lead to :
$3 \pmod 8 \equiv -3 \pmod 8$
$\implies 3 + 8n = 5 +8m, \exists n,m \in \mathbb{Z}$
$\implies 2 = 8(n-m)$
$\implies 1 = 4 (n-m)$
$\implies (n-m) = 1/4$
which is impossible for both $n,m$ being integers.

The difficulty is in finding the logic behind using the two possible (but, mutually exclusive) solutions.

Based on answers below, have identified the given solution approach that concerns with finding the original equation that can have either of the two roots. This original equation should have both roots as possibility. Hence, the answers below emphasize multiplication of the two sub-equations of the original equation, & grouping together the terms with common factor as $16$ and residue $9$.

I am not fully sure of the below issue being clear to me, and am restating it:

But have a hitch in understanding given answer(s), as I compare the original equation's derivation, based on the two mutually exclusive solutions, to the derivation of a quadratic equation from two roots. But in this question, the two roots are mutually exclusive. Does it not make multiplication un-obvious.
Is it that the quadratic equation has roots, while here each residue class is its own equation. This is why for a given modulo $m$, there are stated to be $m$ in-congruent solutions, that form a complete set of residues modulo $m$.
Hence, no parallel can be drawn between the two: - quadratic equation and two different residue values for a modular equation.

• I would say brute force it, $a = 3,5,11,13$ – Doug M Jan 17 '18 at 0:19
• I thought some better approach - theoretic should be better. – jiten Jan 17 '18 at 0:19
• Not so bad to have down-voting. Panic is not needed here, unless repetitious. – jiten Jan 17 '18 at 0:26
• @hardmath I feel that my logical error has been removed, and with proof. Any further will make it no more a question. I feel I have found a good proof in the process. – jiten Jan 17 '18 at 19:10
• I appreciate your effort at improving the Question, but your "doubt" seems to hinge on confusing "and" and "or", something that is inevitable with informal language but which we try to avoid in mathematics. For example, when we say the solutions to $x^2 -3x + 2 = 0$ are $x = 1$ and $x = 2$, we cannot mean that $x = 1$ at the same time $x = 2$. We mean that the quadratic equation is satisfied if (and only if) $x =1$ or $x = 2$. I feel the Answer by @Mohammad Riazi-Kermani should suffice to clear up your confusion if you do a bit of reflection. – hardmath Jan 17 '18 at 22:51

## 2 Answers

Your statement $$a \equiv \pm 3 \pmod 8 \implies (a \equiv 3 \pmod 8) \wedge (a \equiv - 3 \pmod 8)$$ is not logically true. You may change it to $$a \equiv \pm 3 \pmod 8 \implies (a \equiv 3 \pmod 8) \lor (a \equiv - 3 \pmod 8)$$

Note that $$(a=8k\pm 3)\implies ( a^2 = 64 k^2 +9\pm 48k)=16M+9$$Thus the statement is true.

• Please elaborate, why it is "either-or" and not "both roots", as am still confused. Tried to search for a given value that satisfies the congruence, but seems wrong route. – jiten Jan 17 '18 at 0:45
• Please elaborate, as to me the only reason can be: if this is true, then - $3+8n = 5 +8n, \exists n \in \mathbb{Z} \implies 3 = 5.$ – jiten Jan 17 '18 at 0:51
• I hope my explanation is okay. – jiten Jan 17 '18 at 0:53
• Please look at my edited OP to help with my doubt. – jiten Jan 17 '18 at 20:52
• What you have proved in your edited solution is that we can't have both $3 \pmod 8$ and $\equiv -3 \pmod 8$. That is not what you intended to prove. – Mohammad Riazi-Kermani Jan 17 '18 at 21:35

If $a=8k\pm3$ then $a^2=64k^2\pm48k+9=16(4k^2\pm3k)+9$ how hard is this?

• Wonderful! Actually I feel have lost connect of modulo with simple arithmetic, and the grouping by factoring out common terms. Seems that feel modulo something abstract. – jiten Jan 17 '18 at 0:25
• Fixed a small error for you (missing '$k$'). – Deepak Jan 17 '18 at 0:25
• @Servaes Please reconsider the status of my OP, as edit has been made. – jiten Jan 17 '18 at 19:41
• Please look at my edited OP to help with my doubt. – jiten Jan 17 '18 at 20:52