Prove $\,p \equiv q \pmod a \iff p \bmod a = q \bmod a$

Question

I'm trying to understand the notation $p \equiv q \pmod a$. Does does it implies that $p \bmod a = q \bmod a$? for example:

$$ \begin{align} 5 \bmod 7 &= 5 \\ 12 \bmod 7 &= 5 \end{align} $$

Therefor $5 \equiv 12 \pmod 7$.

The last makes more seance to me and looks true so far but I'm not sure if it's always true.

Answer 1

Yes, you're entirely correct. The implication is bidirectional: $$p \equiv q \pmod a \iff p \bmod a = q \bmod a.$$

Answer 2

This involves two different meanings to "mod".

The first is the traditional use, where $p \equiv q \pmod a$ means that $a$ divides $p-q$.

The second is the more recent usage, where "mod" is a binary operator such that "$p \bmod a$" is the remainder when $p$ is divided by $a$.

Looked at in this way, yes, your two expressions are equivalent. This can be readily proved, but I will leave that to you.

A hint: If $r = p \bmod a$, then there is an integer $u$ such that $p = a\cdot u + r$ and $0 \le r < a$.

Answer 3

Yes recall $\, \bar p:=p\ {\rm mod}\ n =$ least natural $\,\bar p\,$ with $\, \color{#0a0}{\bar p\equiv p}\pmod{\! n},\,$ i.e. remainder of $\,p\div n.\,$ Ditto for: $\,\color{#0a0}{\bar q := q}\bmod n.\,$ So $\!\bmod n\!:\ \color{#c00}{p\equiv q}\Rightarrow \color{#0a0}{\bar p\equiv} \color{#c00}{p\equiv q}\,\color{#0a0}{\equiv \bar q}\Rightarrow\bar p\equiv \bar q,\,$ by $\,\equiv\,$ is an equivalence relation so is transitive. The proof reverses, yielding the first equivalence below

$\qquad \bmod n\!:\,\ p\equiv q\iff \bar p\equiv \bar q \iff \bar p = \bar q,\,$ since $\,0 \le \bar p,\,\bar q < n$

---

More conceptually: $\:p\equiv q\!\iff\!$ they have equal equivalence classes $\,p+n\Bbb Z = q+n\Bbb Z\!\iff $ their equivalence classes have equal least natural element, i.e. equal remainders $\!\bmod n,\,$ thus

$$ \bbox[9px,border:1px solid #c00]{p\equiv q\!\!\!\pmod{\!n}\iff p\bmod n\:\! =\:\! q\bmod n}\qquad$$

It may prove instructive to add further details to the sketched proofs to ensure comprehension (compare to direct proofs, e.g. here and here).

Remark $ $ The operational use of mod is often more convenient in computational contexts, whereas the relational use often yields more flexibility in theoretical contexts. The difference amounts to whether it is more convenient to work with canonical normal forms vs. arbitrary equivalence classes (here $\,\bar a = a\bmod n\,$ vs. $\,[a]_n = a+n\Bbb Z).\,$ For example, imagine how inconvenient it would be to state the laws of fraction arithmetic if one required all fractions to be in normal (reduced) form, i.e. in lowest terms. Instead, it proves far more convenient to work with arbitrary equivalent fractions, e.g. to choose both with a common denominator before adding fractions. See here for further discussion of these matters.