Question

Difference between modular and polynomial arithmetic

Answer 1

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.