Modular Arithmetic/Modular Arithmetic

From Wikibooks, open books for an open world
Jump to navigation Jump to search
Modular Arithmetic
 ← What is a Modulus? Modular Arithmetic The Pigeonhole Principle → 

Introduction[edit | edit source]

Previously we gave examples of some modular congruences using the analogy of clock arithmetic – 27 hours from now will be the same time as 3 hours from now. In English we would say 27 is congruent to 3 modulo 24. Expressed mathematically, we would write:


Note the congruent sign has three horizontal lines and not two like an equals sign.

In general, for any integers and any integer , the congruence is equivalent to the following:

  1. is an integer
  2. ( divides minus )
  3. there exists some integer such that

Using our previous example , we see that:

Now that we have a definition of modular congruence, we can go on to state some basic properties of the congruence relation () itself. The congruence relation is an equivalence relation, which means that the congruence relation is reflexive, symmetric, and transitive. Since the equality relation () is also an equivalence relation we can demonstrate these three properties easily; for any integers  :

  1. Reflexive:
  2. Symmetric: if then
  3. Transitive: if and then

Analogously, for the congruence relation () satisfies these three properties; for any integers and any integer  :

  1. Reflexive:
  2. Symmetric: if then
  3. Transitive: if and then
Exercises: Equivalence Relations

Prove that the congruence relation () is reflexive, symmetric, and transitive.

Which of the following relations are congruence relations:

  • Less than ()
  • Greater than ()
  • Less than or equal to ()
  • Greater than or equal to ()
  • Not equal to ()

Addition, Subtraction, Multiplication[edit | edit source]

We took what appears to be a detour through equivalence relations, because those three properties allow us to define addition, subtraction, and multiplication for congruences. Addition, subtraction, and multiplication work exactly the same way as they do with integers with the only constraint being that addition, subtraction, and multiplication is only allowed when the congruences have the same moduli. Mathematically, suppose we have some and then:

  1. (Addition and Subtraction)
  2. (Multiplication)

For example, since 23 ≡ 3 (mod 4) and 6 ≡ 2 (mod 4) the following are true:

  1. (23 + 6) ≡ (2 + 3) (mod 4) = 29 ≡ 5 (mod 4) = 29 ≡ 1 (mod 4) (Addition)
  2. (23 - 6) ≡ (2 - 3) (mod 4) = 17 ≡ -1 (mod 4) = 17 ≡ 3 (mod 4) (Subtraction)
  3. (23 * 6) ≡ (2 * 3) (mod 4) = 138 ≡ 6 (mod 4) = 138 ≡ 2 (mod 4) (Multiplication)

Again, as long as we have the same moduli between two congruences, we can add, subtract, and multiply them together.

Exercises: Equivalence Relations

Using the definition of congruences and the fact that it is an equivalence relationship, prove that addition, subtraction, and multiplication are valid for congruences with the same moduli.

Division[edit | edit source]

Just as we cannot divide by zero in normal arithmetic, division for modular congruences is only allowed under certain circumstances. For example, just because we cannot divide both sides by two because . Mathematically, if and if then .

means the greatest common divisor for – the greatest number that divides both and . When the greatest common divisor of two numbers is 1, that means there are no other common divisors (i.e. they are relatively prime). Our example of fails to divide by 2, because both 2 and 10 are divisible by 2. Again, we can only divide provided that there are no common divisors between the number we are trying to divide by and the modulus. Note that if the modulus is a prime number, then division is defined for all divisors.