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?

  • $\begingroup$ "$p\equiv5\pmod8$ and $p\equiv7\pmod8$" is always false since $5\not\equiv7\pmod8$; do you mean "or" here? $\endgroup$ – stewbasic Jan 28 '18 at 22:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Chessanator Jan 28 '18 at 22:24
  • $\begingroup$ This problem seems to have a lot more to do with logic than modular arithmetic. If $p\equiv3\pmod8$, can $p\equiv1\pmod4$? $\endgroup$ – Mike Jan 28 '18 at 22:24
  • $\begingroup$ Yes, you're right. It must be an "or" here. $\endgroup$ – 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


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.