Modular arithmetic is very similar to the Arithmetic we are so much
used to. In line with the Sylvester's pronouncement, let's write down for the
record the differences and similarities found between Euclidean (regular) and Gaussian (modulo) arithmetic.
Differences
Numbers
Euclidean arithmetic operates on infinite set of all integers; Gaussian only works with finite
sets {0,1,...,N-1} (or with sets of residue classes.)
ab = 0
In usual arithmetic, ab = 0 is only possible when either a or b is zero. In Gaussian case we have, e.g., 2×3 = 0 (mod 6),
whereas neither 2 = 0 (mod 6) nor 3 = 0 (mod 6). 2 and 3
are zero divisors in the arithmetic modulo 6. Euclidean arithmetic has no zero divisors.
Arithmetic modulo a prime, too, has no zero divisors.
Polynomial roots
Fundamental Theorem of Algebra implies that
every polynomial of order n over the field C of complex numbers has exactly n roots. In
the Gaussian arithmetic all depends on a polynomial. For example, in modulo arithmetic even linear
equations may behave unexpectedly:
3x + 1 = 0 (mod 5) has a unique (mod 5) solution 3,
3x + 1 = 0 (mod 6) has no solution (mod 6)
3x - 6 = 0 (mod 9) has three solution (mod 6): 2,5, and 8
Simultaneous linear equations
As is demonstrated by the Chinese Remainder Theorem, in the Gaussian arithmetic
linear simultaneous equations may have a number of solutions. Analogous situation in the usual arithmetic
the only alternatives are a single solution (when all the equations are multiples of each other) or no solutions at all.
Multiplicative inverse
In Euclidean arithmetic no integer (except 1) has an inverse. In arithmetic modulo a prime number p,
every non-zero number has an inverse.
Similarities
But of course there is a good deal of similarity between the two arithmetic. Most important,
for both addition and multiplication all the basic properties are preserved:
Commutativity
a + b = b + a, a × b = b × a
Associativity
a + (b + c) = (a + b) + c, a × (b × c) = (a × b) × c
