14
$\begingroup$

In modular arithmetic (say mod3), is the largest number (3) greater than or less than the smallest number?

Because, intuitively, it would be greater, but 3+1=1 in mod3 which would suggest that it is smaller.

$\endgroup$
5
  • 16
    $\begingroup$ There is no linear order in integers modulo $\;n\;$ $\endgroup$
    – user177692
    Mar 29, 2015 at 13:58
  • $\begingroup$ So, inequalities don't apply? $\endgroup$
    – davecw
    Mar 29, 2015 at 13:59
  • $\begingroup$ Yes @davecw, they do not apply. $\endgroup$
    – user177692
    Mar 29, 2015 at 14:05
  • 4
    $\begingroup$ @AntoineNemesioParras: There certainly is a linear order; in fact, there are $n!$ linear orders. But if $n \ge 2$, then none of them satisfies the criterion $a \le a + 1$ for all $a$. $\endgroup$
    – ruakh
    Mar 29, 2015 at 18:36
  • $\begingroup$ @ruakh Thank you, that is my meaning. $\endgroup$
    – user177692
    Mar 30, 2015 at 9:49

4 Answers 4

27
$\begingroup$

You can't have a notion of order (a set of relations of the form $a<b$) that agrees with $a+c<b+c$ on such a set, because there is a finite number $n$ of times you can add $1$ to itself to get $0$, and so $$ 0<1<1+1<\dotsb< \underbrace{1+\dots+1}_n=0, $$ which makes no sense.

You're welcome to define $0<1<2<\dotsb<n-1$, but it can't be compatible with addition.

$\endgroup$
3
  • 2
    $\begingroup$ Actually, you can have an asymmetric (and even trichotomous) relation $\prec$ on the integers modulo $n$ that satisfies $a+c \prec b+c \iff a \prec b$: one example, for odd $n$, would be $a \prec b$ $\iff$ $0 < (b-a) \bmod n < n/2$ (where $x \bmod n$ means the smallest non-negative integer congruent to $x$ modulo $n$). It's just that such a relation may not (and in fact, except for trivial cases when $n<3$, cannot) be transitive, so you cannot conclude $a<c$ from $a<b$ and $b<c$. $\endgroup$ Mar 29, 2015 at 15:19
  • $\begingroup$ @IlmariKaronen Oh, I see. The OP wasn't very clear about precisely what they wanted, so I wrote the simplest explanation I could think of. But that's another good way of making it fall apart. $\endgroup$
    – Chappers
    Mar 29, 2015 at 15:26
  • 5
    $\begingroup$ Regarding your last remark/paragraph, this is exactly the situation in most programming languages where "the integers" are actually "the integers mod $2^N$ for some $N$". And it's rather confusing to beginners who don't understand that. $\endgroup$ Mar 29, 2015 at 17:14
11
$\begingroup$

The integers modulo $n$ form a ring, but it's not an ordered ring, so it's generally not meaningful to speak of one element of such a ring being greater or less than another.

The reason why we can't just define an ordering on the integers modulo $n$ (for $n > 1$) is that the following properties, generally expected of an order relation, cannot all hold at the same time on a finite ring with more than one element:

  1. totality: for all $a$ and $b$, either $a \leq b$ or $b \leq a$.
  2. antisymmetry: if $a \neq b$ and $a \leq b$, then $b \nleq a$.
  3. transitivity: if $a \leq b$ and $b \leq c$, then $a \leq c$.
  4. translation invariance: if $a \leq b$, then $a + c \leq b + c$.

In particular, if we had such a relation on the integers modulo $n$, then, by totality and antisymmetry, either $0 \leq 1$ or $1 \leq 0$ would have to hold, but not both. Assuming, without loss of generality, that $0 \leq 1$, we could apply translation invariance $n-1$ times to show that $1 \leq 2$, $2 \leq 3$, $3 \leq 4$, and so on up to $n-1 \leq n$. By transitivity, we could then conclude that $1 \leq n$; but, since $n \equiv 0$ in the ring of integers modulo $n$, this would imply $1 \leq 0$, which, together with the earlier assumption that $0 \leq 1$, would lead to a contradiction unless $n = 1$.

That said, if we drop (or even just relax) any one of these four properties, it is possible to find "order" relations on the integers modulo $n$ that satisfy the remaining three. For example, it's perfectly reasonable to identify the elements of $\mathbb Z / n \mathbb Z$ with their smallest non-negative representatives, and to order these as one usually would (i.e. $0 < 1 < 2 < \dotsb < n-1$), but this order is not translation-invariant modulo $n$; in particular, by this order, $-1 \equiv n-1 > 0$ modulo $n$.

Conversely, by giving up transitivity, it's also possible to define a total, antisymmetric and translation-invariant "order" on the integers modulo $n$. For example, for odd $n$, we may define $a \preceq b$ $\iff$ $(b-a) \bmod n \le n/2$, where $x \bmod n$ means the smallest non-negative integer congruent to $x$ modulo $n$. (If we also relax either totality or antisymmetry a little, this can be made to work for even $n$, too.) Essentially, if we were to draw the integers modulo $n$ equally spaced in a circle, $a \preceq b$ would hold whenever $a$ lies on the half-circle "behind" $b$.

$\endgroup$
2
$\begingroup$

My interpretation of modular arithmetic was that you reduce everything to the group {0, 1, 2}, which would mean that 3 would be equivalent to 0. Therefore the question "is 3 greater than 1 (mod3)" doesn't make sense, since 3 isn't on your number line; the question would simply be "is 0 greater than 1", to which the answer is no.

EDIT: Sorry I didn't see; this is basically what iadvd said, but less thorough.

$\endgroup$
1
$\begingroup$

It is just due to the properties of the modular arithmetic, in your sample, the largest possible number you could obtain mod $3$ would be $2$, because the possible residuals of the division are only $\{0,1,2\}$.

$3 \bmod 3$ is congruent to $0$, because the residual of $3$ divided by $3$ is $0$. According to the properties of modular arithmetic:

$$(a+b) \bmod 3 = (a \bmod 3) + (b \bmod 3)$$

so

$$(3+1) \bmod 3 = (3 \bmod 3) + (1 \bmod 3) = 0 + 1 = 1$$

In other words, you can use order only applied to the results of the mod operation, which in the $\bmod 3$ case are $\{0,1,2\}$.

$\endgroup$
2
  • $\begingroup$ You do realize that when you hit $\geq 2000$ rep that you will be able to make edits that are applied immediately right? If you are going to make so many edits, please consider actually editing the text body instead of just changing/adding a tag. $\endgroup$ Apr 1, 2015 at 1:04
  • $\begingroup$ @crash, thank you for the information about the reputation, I use to read the open questions every day and try to help the ones I am interested by tagging them, it is a way of (1) getting familiar with the topics as well and (2) helping the site to refine the search feature. I am not good enough to edit the text body sometimes (in some occasions I have fixed the mathjax code) I will try to reduce my daily reviews. $\endgroup$
    – iadvd
    Apr 1, 2015 at 1:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .