In mod3, is 3 greater than, or less than 1?

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.

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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