Example 1: The time is now 21:00. Class will start in 11 hours. What will the time be then?

The answer to this question is not 21+11=32 but rather 21+11-24=8. When the time passes 23:59:59, we start over from zero again. The time on a watch is actually the remainder upon integer division by 24; we have that

When you are only interested in the remainders and not care about the quotients, we talk about congruences. When we calculate with the remainders from division by the integer n, we say that we calculate modulo n or that we calculate in Z_{n}. Two numbers with same remainder upon divison by the integer n are called congruent modulo n. We have for instance that

since

That the numbers 25, 11, -3 and 4 are congruent modulo n we can denote as that they belong to the equivalence class [4]_{7}, called residue class 4 modulo 7. The residue classes modulo 7 are the sets

We see that the residue classes constitutes a partition of the set of all integers Z, since the residue classes are mutually disjoint as well as their union are equal to Z.

Example 2: Add 34 and 51 modulo 7. We can either compute the sum directly

or stepwise

since 85=7*12+1, 34=7*4+6 and 51=7*7+2.

Example 3: Compute 34 multiplied by 51 modulo 7. We can either compute the product directly

or stepwise

since 1734=7*247+5, 34=7*4+6 and 51=7*7+2.

Example 4: Calculate the inverse to 3 modulo 7. The inverse to a number a is a number b=a^{-1} such that the product ab=1. Let us make a table over the products modulo 7 between the integers 0-6. We have

* |
0 |
1 |
2 |
3 |
4 |
5 |
6 |

0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |

1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |

2 |
0 |
2 |
4 |
6 |
1 |
3 |
5 |

3 |
0 |
3 |
6 |
2 |
5 |
1 |
4 |

4 |
0 |
4 |
1 |
5 |
2 |
6 |
3 |

5 |
0 |
5 |
3 |
1 |
6 |
4 |
2 |

6 |
0 |
6 |
5 |
4 |
3 |
2 |
1 |

We see from the table that 3^{-1} is 5, since

Example 5: Compute the inverse to 3 modulo 6. We construct a similar table as in the example above. We have

* |
0 |
1 |
2 |
3 |
4 |
5 |

0 |
0 |
0 |
0 |
0 |
0 |
0 |

1 |
0 |
1 |
2 |
3 |
4 |
5 |

2 |
0 |
2 |
4 |
0 |
2 |
4 |

3 |
0 |
3 |
0 |
3 |
0 |
3 |

4 |
0 |
4 |
2 |
0 |
4 |
2 |

5 |
0 |
5 |
4 |
3 |
2 |
1 |

In this case there is no inverse to 3 since there is no number that gives the product 1 (modulo 6) upon multiplication by 3.

Example 6: Solve the equation

This is the same as saying that

for some integer m. If we put m=-x we get the diophantine equation

that we solved in example 1 in part 4. The solution of the diophantine equation is y=-468-97k, k integer. This means that the wanted solution is y=17, since there is only one solution y in the interval 0-96 (for k=-4), that is

Example 7: Solve the equation

This is the same as saying that

for some integer m. If we put m=-x we get the diophantine equation

that had no solution in example 2 in part 4. This means that there is no solution to this equation.

Example 8: Solve the equation

This is the same as saying that

for some integer m. If we put m=-x we get the diophantine equation

that we solved in example 1 i part 4. The solution of this diophantine equation is y=6-14k, k integer. This means that we have 7 solutions (as many as gcd(98,35)) in the interval 0-97. They are obtained fork=0,-1,-2,…,-6 and are

We can easily check that they are solutions by insertion in the equation. We have for instance that