1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Im reasonably sure this is true. I thought that this was the definition of equivalence in mod systems $\endgroup$ – Asimov May 27 '14 at 17:24
  • $\begingroup$ 5 is however a representative element of the class $5\bmod7$, so you should be carefull writing $5\bmod7=5$, since 5 is a number and $5\bmod7$ is an entire class of numbers. That is why we write $5\bmod7\equiv5$. $\endgroup$ – gebruiker May 27 '14 at 17:36
  • 2
    $\begingroup$ @gebruiker: No, I don't agree. For $n \in \mathbb Z$, $n$ mod $7$ is defined to be an integer between $0$ and $6$. So $5$ mod $7 = 5$. $\endgroup$ – TonyK May 27 '14 at 20:07
1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

Yes, $\, p\ {\rm mod}\ n\,$ is the least natural $\,\bar p\,$ such that $\, \bar p\equiv p\pmod n.\,$ Similarly for $\,\bar q \equiv q\pmod n.\,$ Therefore $\ {\rm mod}\ n\!:\ \bar p\equiv p\equiv q\,\equiv \bar q\,\Rightarrow\,\bar p\equiv \bar q\,$ by transitivity of $\,\equiv\,$ (being an equivalence relation)

Said 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 nonnegative element, i.e. equal remainders mod $\,n.$

You may find it instructive to carefully prove these equivalences.

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, or arbitrary equivalence classes. 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 very flexible to work with arbitrary equivalent fractions, e.g. to choose both with a common denominator before adding fractions.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy