# 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

**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

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

**Zero element**0 + a = a

**Unit element**1 × a = a

**Additive inverse**a + (-a) = 0

**Euclid's common notions**a = b implies a + c = b + c (and a × c = b × c)

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

- Modular Arithmetic
- Differences and Similarities
- Solutions to some problems

- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71417238