2
$\begingroup$

Gauss introduced the $\equiv$ symbol because congruences modulo $n$ were very similar to equality.

But, by curiosity I would like to know if it was possible to write inequations such as:

$$3x + 2y \leq 5 [7]$$.

$\endgroup$
  • $\begingroup$ It doesn't make sense to have such inequalities. Equality modulo is not an equality in the usual sense. $a \equiv b \pmod n$ only means that $a - b$ is divisible by $n$. What would an inequality mean? $a-b$ is less than something that is divisible by $n$? It certainly is. Moreover, if you want to deal with congruences as if they are equations in the usual sense, then any number is less than any number and any number is greater than any number, etc. Modulo $5$, $10$ is "greater" than $100$ in the sense that $10 = 1000$, and $100$ is "greater" than $10$ in the usual sense. $\endgroup$ – user230734 Apr 24 '15 at 11:34
  • 1
    $\begingroup$ @BolzWeir: This is an answer. $\endgroup$ – Eric Stucky Apr 24 '15 at 11:55
  • $\begingroup$ @EricStucky: At first, I thought: "let me give a short statement and a simple example on why this doesn't make sense". Then I got carried on. Anyway, I posted it as an answer. $\endgroup$ – user230734 Apr 24 '15 at 12:01
3
$\begingroup$

It doesn't make sense to have such inequalities. Equality modulo is not an equality in the usual sense.

$a \equiv b \pmod n$ only means that $a - b$ is divisible by $n$. What would an inequality mean? $a-b$ is less than something that is divisible by $n$? It certainly is.

If you want to deal with congruences as if they are equations in the usual sense, then any number is less than any number and any number is greater than any number, etc. Modulo $5$, $10$ is "greater" than $100$ in the sense that $10 = 1000$, and $100$ is "greater" than $10$ in the usual sense.

$\endgroup$
1
$\begingroup$

When we write "$x \leq y$" with $x$ and $y$ numbers, the "expected" properties include:

  • Totality: For all $x$ and $y$, at least one of "$x \leq y$" and $y \leq x$" holds;

  • Antisymmetry: If $x \leq y$ and $y \leq x$, then $x = y$;

  • Transitivity: If $x \leq y$ and $y \leq z$, then $x \leq z$.

  • Translation invariance: If $x \leq y$, then $x + a \leq y + a$ for all $a$".

Let $n > 1$ be an integer. It's easy to see not all of these properties can be satisfied in the set $\mathbf{Z}/n\mathbf{Z}$ of residue classes modulo $n$. Take $x = [0]$ and $y = [1]$. Which inequality should hold, "$[0] \leq [1]$" or "$[1] \leq [0]$"? No matter which you try, you run into trouble because $$ \underbrace{[1] + \dots + [1]}_{\text{$(n-1)$ times}} = [n-1] = [-1]. \tag{1} $$ If $[0] \leq [1]$, then by (1) and transitivity, $[0] \leq [-1]$. Adding $[1]$ to both sides gives $[1] \leq [0]$. This violates antisymmetry because $[0] \neq [1]$.

Similarly, if $[1] \leq [0]$, then by (1) and transitivity, $[-1] \leq [0]$. Adding $[1]$ to both sides gives $[0] \leq [1]$, again violating antisymmetry.

$\endgroup$
  • $\begingroup$ How can you say that by transitivity [0]≤[−1] $\endgroup$ – lopata Apr 24 '15 at 12:58
  • $\begingroup$ @TheoZ: Briefly, "a sum of positive numbers is positive", and $[-1]$ is a sum of $[1]$'s. In more detail, adding "$[0] \leq [1]$" to itself $(n - 1)$ times gives $$[0] \leq [1] \leq [1] + [1] = [2] \leq \dots \leq [1] + \dots + [1] = [n - 1] = [-1],$$so $[0] \leq [-1]$ by transitivity. $\endgroup$ – Andrew D. Hwang Apr 24 '15 at 13:31
  • 1
    $\begingroup$ @TheoZ i.e. ordered $\Rightarrow$ torsion-free. Follow the link for a similar question. $\endgroup$ – Bill Dubuque Apr 24 '15 at 14:56

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.