Modular Arithmetic

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

6. Additive inverse

   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.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2009 Alexander Bogomolny