# Modular Arithmetic

## Differences and Similarities

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

1. 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.)

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

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

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

5. 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:

1. Commutativity

a + b = b + a, a × b = b × a

2. Associativity

a + (b + c) = (a + b) + c, a × (b × c) = (a × b) × c

3. Distributivity

(a + b) × c = a×c + b×c

4. Zero element

0 + a = a

5. Unit element

1 × a = a

a + (-a) = 0

7. Euclid's common notions

a = b implies a + c = b + c (and a × c = b × c)

8. Factoring

If a polynomial equation f(x) = 0 has a root a then f(x) = (x-a)g(x) for some other polynomial g.