Modular Arithmetic/Modular Arithmetic

Modular Arithmetic
 ← What is a Modulus? Modular Arithmetic The Pigeonhole Principle → 


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 a 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 equals 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, MultiplicationEdit

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.


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

The   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 divisors. 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.