# Prove an equivalence of modular-arithmetic

Studying elementary number-theory I found this equivalence for an odd prime $p$:

$(p\equiv1 \,\,\, \text{ (mod 4) and } p\equiv\pm3 \,\,\, \text{ (mod 8)) or } (p\equiv3 \,\,\, \text{ (mod 4) and } p\equiv \pm1 \,\,\, \text{ (mod 8))} \Longleftrightarrow (p\equiv5 \,\,\, \text{ (mod 8) or } p\equiv7 \,\,\, \text{ (mod 8))}$

I there an easy way to see why this equivalence holds? I started prooving $"\Rightarrow":$

If $(p\equiv1 \,\,\, \text{ (mod 4) and } p\equiv\pm3 \,\,\, \text{ (mod 8))}$, then $8\mid2(p-1)$ and $8 \mid (p\pm3)$, so we get $8\mid(2(p-1)-(p\pm3)) \Rightarrow 8\mid p-5$ and $8\mid p+1 \Rightarrow (p\equiv5 \,\,\, \text{ (mod 8) and } p\equiv7 \,\,\, \text{ (mod 8))}\,\,...$

It seems to take long to show an equivalence like that. Is there an easier way to see why this equivalence holds?

• "$p\equiv5\pmod8$ and $p\equiv7\pmod8$" is always false since $5\not\equiv7\pmod8$; do you mean "or" here? – stewbasic Jan 28 '18 at 22:23
• Hint: contradictions. One of the crucial things to learn as a beginning mathematician is vacuous truth, so we take every chance we can get to drill it in. – Chessanator Jan 28 '18 at 22:24
• This problem seems to have a lot more to do with logic than modular arithmetic. If $p\equiv3\pmod8$, can $p\equiv1\pmod4$? – Mike Jan 28 '18 at 22:24
• Yes, you're right. It must be an "or" here. – mathcourse Jan 28 '18 at 22:25

If I understand your question, if you want $p \equiv 1 \pmod 4$ and $p \equiv \pm 3 \pmod 8$ simultaneously then we must have $p \equiv -3 \equiv 5 \pmod 8$, since if instead $p \equiv 3 \pmod 8$ then $p=8k+3$ for some $k$ and we just take this modulo $4$ to see $p \equiv 3 \pmod 4$ which contradicts our original assumption. You can use the same reasoning for the other direction