When performing the division , the remainder is . What is the remainder in the division ? What is the remainder in the division of by ? If you have special software, you can determine quickly that the remainder for the first question is the number . Note that the number in the second question is the current largest known prime number at the writing of this post. The special software you use might have to struggle a little to come up with the answer of . Without special software, you can use congruence arithmetic to perform the above calculations.
Congruence notation was invented by the great mathematician Carl Friedrich Gauss (1777 – 1855). It is hard to overstate the importance of the role of congruence in number theory. The notion not only eases calculation but also makes statements of theorems much easier to state and simplifies the proofs of theorems. This post is a basic discussion of congruence.
For more information about congruence or modular arithmetic, see the number theory introductory text  or the Wikepedia entry on modular arithmetic.
Given integers , and with , the statement that is congruent to modulo means that the difference is divisible by . In symbol, we write . The number is the modulus of the congruence. We also use the notation to refers to the statement that is divisible by . We repeat the definition below.
The following two properties of congruence that can be easily verified from definition .
Another meaning of congruence modulo comes from the division algorithm. For example, the division gives the remainder , i.e., . So for the division where both and are both positive, we have for some integer with (call the remainder) and some integer . From this we can conclude that every integer is congruent modulo to exactly one integer from the set . The integer is called the least residue of modulo . We summarize as follows: for every integer ,
For a proof of property (3), see this post. Another characteristic of congruence modulo is the following property.
All the above conditions point to the cyclical nature of congruence, which can be visualized in a diagram. The figure is below describes congruence modulo .
You can start at any point in the above diagram. Every time you add or subtract the modulus , you go around the circle and come back to the same point you start from (conditions 2 and 4). Two integers are related congruence modulo if they can be reduced by the division algorithm to the same time in the clock (condition 3).
Some Properties for Congruence
Congruence arithmetic is similar to conventional arithmetic. However, there are important differences. For example, comparing congruence with the equality sign = will help us see some of the differences. To set up the comparison, the following are some operations on real numbers we would like to focus on:
Operations on real numbers:
All the above arithmetic operations on real numbers have analog in congruence except for R5. The following are the equivalence in congruence operations.
C5 has the additional requirement that and the modulus are coprime.
The properties C3 and C4 indicate that congruences may be validly added, subtracted and multiplied.
Note that the direct analog of R5 is not true in general. For example, . However, . In this case we cannot cancel out the common factor of on both sides of the congruence. When the additional requirement that the common factor and the modulus are coprime (i.e. the greatest common divisor is ), we can cancel out the common factor (as indicated by C5).
The derivation of the properties C1 through C4 is straightforward. The proof of C5 relies on Euclid’s lemma.
The properties in the above section are not meant to be memorized. The best approach is to work examples.
One typical congruence calculation is to find the least residue of a number modulo . The number could be a sum or a product. Or it could be some number raised to an exponent. For the case of sum or product, we can start by reducing the components in the sum or product. For the case of an exponential, we can sometimes break it up into product of smaller numbers or use a “divide and conquer” approach. Let’s look at some examples.
To find congruence modulo , we do not need to first multiply. We can start by reducing each of the factors as follows:
In the above calculation we use property C4. We have and . Thus . We really do not need to be too conscious of which property to use. Just work enough examples and the process will flow quite naturally.
To find , we can start by breaking up the number . The following is one example of how to do so.
In the above calculation, we break up into multiple of with added. Then starting reducing each of the numbers. Then multiply and sum to get . We then break it up into and , which is reduced into and . Finally is reduced into modulo . The properties used are C3 and C4. Once again, this type of calculation will flow naturally after working a few examples.
To find , we can start by reducing the base .
It follows from property C4 that if , then . Based on this idea, we can reduce base to the smaller base of . We then reduce the exponent to the exponent of . Such a process is a “divide and conquer” process that repeatedly reduces the exponent by half down to a manageable size.
Another example. Find the . Note that and .
The key to a reduction of power in a congruence calculation is to find the right starting point. In the above example, exponent is reduced from to , Then subsequently, keep reducing the exponent by half in each step until reaching a size that is manageable or easy to do.
It also follows from Fermat’s little theorem that .
It is well known, even to some elementary school children, that an integer is divisible by nine if the sum of the digits is divisible by nine. The proof of this fact is very easy if done using congruence. The idea for the proof will be clear from the following example.
The number is divisible by nine since . Also note that the sum of its digits is . We can also look at the congruence angle. First, , and and so on. Furthermore, we have:
We can now reduce the digital representation of using congruence.
The above derivation shows that any positive integer is congruent modulo to the sum of its digits. Thus a positive integer is divisible by if and only if the sum of its digits is divisible by .
The same property is also true for divisibility by three. Using congruence, it can be shown that any positive integer is divisible by if and only if the sum of its digits is divisible by .
Congruence modulo is an interesting case. Note that , , and and so on. Thus where or depending on whether the power is even or odd. So in reducing the digital representation of a number, we need to add alternating plus and minus signs.
Thus is not divisible by .
Work the two congruence calculation mentioned at the beginning of the post. Show the following.
- Dudley U., Elementary Number Theory, 2nd ed., Dover Publications, Inc, New York, 2008