A basic discussion of congruences

When performing the division 45 \div 7, the remainder is 3. What is the remainder in the division 9664^{79081} \div 55049? What is the remainder in the division of (2^{57885161} - 1) by 524287? If you have special software, you can determine quickly that the remainder for the first question is the number 1020. Note that the number 2^{57885161} - 1 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 255. 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 [1] or the Wikepedia entry on modular arithmetic.

___________________________________________________________________________________________________________________

Basic Discussion

Given integers a, b and m with m>0, the statement that a is congruent to b modulo m means that the difference a-b is divisible by m. In symbol, we write a \equiv b \ (\text{mod} \ m). The number m is the modulus of the congruence. We also use the notation m \lvert a-b to refers to the statement that a-b is divisible by m. We repeat the definition below.

    a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \  m \lvert a-b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The following two properties of congruence that can be easily verified from definition (1).

    a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ a=b+k \cdot m \text{ for some integer } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)

    b+k \cdot m \equiv b \ (\text{mod} \ m) \text{ for all integers } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2b)

Another meaning of congruence modulo m comes from the division algorithm. For example, the division 45 \div 7 gives the remainder 3, i.e., 45=6 \cdot 7 +3. So for the division a \div m where both a and m are both positive, we have a=q \cdot m+r for some integer r with 0 \le r <m (call the remainder) and some integer q. From this we can conclude that every integer a is congruent modulo m to exactly one integer from the set \left\{0,1,2,\cdots,m-1 \right\}. The integer r is called the least residue of a modulo m. We summarize as follows: for every integer a,

    a \equiv r \ (\text{mod} \ m) \text{ for a unique integer } r \text{ with } 0 \le r < m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

For a proof of property (3), see this post. Another characteristic of congruence modulo m is the following property.

    a \equiv b \ (\text{mod} \ m) \Longleftrightarrow \text{ each of } a \text{ and } b \text{ leaves the same remainder }

              \text{ when divided by } m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ (4)

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 12.

You can start at any point in the above diagram. Every time you add or subtract the modulus m=12, 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 12 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:

    a=b \ \ \Longrightarrow \ \ b=a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R1}

    a=b \text{ and } b=c \ \ \Longrightarrow \ \ a=c \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R2}

    a=b \text{ and } c=d \ \ \Longrightarrow \ \ a+c=b+d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R3}

    a=b \text{ and } c=d \ \ \Longrightarrow \ \ a \cdot c=b \cdot d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R4}

    ac=bc \text{ and } c \ne 0 \ \ \Longrightarrow \ \ a=b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R5}

All the above arithmetic operations on real numbers have analog in congruence except for R5. The following are the equivalence in congruence operations.

    a \equiv b \ (\text{mod} \ m) \ \ \Longrightarrow \ \ b \equiv a \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C1}

    a \equiv b \ (\text{mod} \ m) \text{ and } b \equiv c \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv c \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C2}

    a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a+c \equiv b+d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C3}

    a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \cdot c \equiv b \cdot d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C4}

    a \cdot c \equiv b \cdot c \ (\text{mod} \ m) \text{ and } c \not \equiv 0 \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv b \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C5}

      C5 has the additional requirement that c and the modulus m 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, 20 \equiv 2 \ (\text{mod} \ 6). However, 10 \not \equiv 1 (\text{mod} \ 6). In this case we cannot cancel out the common factor of 2 on both sides of the congruence. When the additional requirement that the common factor c and the modulus m are coprime (i.e. the greatest common divisor is 1), 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.

___________________________________________________________________________________________________________________

Some Examples

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 a modulo m. The number a 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 55 \cdot 67 congruence modulo 7, we do not need to first multiply. We can start by reducing each of the factors as follows:

    55 \cdot 67 \equiv 6 \cdot 4 \equiv 24 \equiv 3 \ (\text{mod} \ 7)

In the above calculation we use property C4. We have 55 \equiv 6 \ (\text{mod} \ 7) and 67 \equiv 4 \ (\text{mod} \ 7). Thus 55 \cdot 67 \equiv 6 \cdot 4 \ (\text{mod} \ 7). 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 1567 \equiv (\text{mod} \ 13), we can start by breaking up the number 1567. The following is one example of how to do so.

    \displaystyle \begin{aligned} 1567&=30 \cdot 50 + 67 \\&=31 \cdot 50 + 17 \\&\equiv 5 \cdot 11+4=59 \ (\text{mod} \ 13)\\&=50+9 \\&\equiv 11+9 \ (\text{mod} \ 13)=20 \\&\equiv 7 \ (\text{mod} \ 13) \end{aligned}

In the above calculation, we break up 1567 into multiple of 50 with 17 added. Then starting reducing each of the numbers. Then multiply and sum to get 59. We then break it up into 50 and 9, which is reduced into 11 and 9. Finally 20 is reduced into 7 modulo 13. The properties used are C3 and C4. Once again, this type of calculation will flow naturally after working a few examples.

To find 55^{23} \equiv (\text{mod} \ 7), we can start by reducing the base 55.

    \displaystyle \begin{aligned} 55^{23}&\equiv 6^{23} \ (\text{mod} \ 7) \\&=(6^2)^{11} \cdot 6 \\&\equiv (1)^{11} \cdot 6 \ (\text{mod} \ 7) \\&\equiv 6 \ (\text{mod} \ 7)  \end{aligned}

It follows from property C4 that if a \equiv b \ (\text{mod} \ m), then a^n \equiv b^n \ (\text{mod} \ m). Based on this idea, we can reduce base 55 to the smaller base of 6. We then reduce the exponent 23 to the exponent of 11. 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 2^{100} \equiv (\text{mod} \ 101). Note that 2^7=128 and 128 \equiv 27 \ (\text{mod} \ 101).

    \displaystyle \begin{aligned} 2^{100}&= (2^{7})^{14} \cdot 2^2  \\&\equiv (27)^{14} \cdot 4 \ (\text{mod} \ 101) \\&= (27^2)^{7} \cdot 4 \\&\equiv 22^7 \cdot 4 \ (\text{mod} \ 101) \\&=(22^2)^3 \cdot 22 \cdot 4 \\&\equiv 80^3 \cdot 88 \ (\text{mod} \ 101) \\&=80^2 \cdot 80 \cdot 88 \\&\equiv 37 \cdot 80 \cdot 88 \ (\text{mod} \ 101) \\&=2960 \cdot 88 \\&\equiv 31 \cdot 88 \ (\text{mod} \ 101) \\&\equiv 1 \ (\text{mod} \ 101) \end{aligned}

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 100 to 14, 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 2^{100} \equiv 1 \ (\text{mod} \ 101).

___________________________________________________________________________________________________________________

More Examples

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 55953 is divisible by nine since 55953 = 9 \cdot 6217. Also note that the sum of its digits is 27. We can also look at the congruence angle. First, 10 \equiv 1 \ (\text{mod} \ 9), 10^2 \equiv 1 \ (\text{mod} \ 9) and 10^3 \equiv 1 \ (\text{mod} \ 9) and so on. Furthermore, we have:

    55953=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3

We can now reduce the digital representation of 55953 using congruence.

    \displaystyle \begin{aligned} 55953&=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3 \\&\equiv 5 \cdot 1+5 \cdot 1+9 \cdot 1+5 \cdot 1+3 \\&=27 \\&\equiv 0 \ (\text{mod} \ 9)  \end{aligned}

The above derivation shows that any positive integer is congruent modulo 9 to the sum of its digits. Thus a positive integer is divisible by 9 if and only if the sum of its digits is divisible by 9.

The same property is also true for divisibility by three. Using congruence, it can be shown that any positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3.

Congruence modulo 11 is an interesting case. Note that 10 \equiv -1 \ (\text{mod} \ 11), 10^2 \equiv 1 \ (\text{mod} \ 11), and 10^3 \equiv -1 \ (\text{mod} \ 11) and so on. Thus 10^n \equiv k \ (\text{mod} \ 11) where k=1 or k=-1 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.

    \displaystyle \begin{aligned} 85647&=8 \cdot 10^4+5 \cdot 10^3+6 \cdot 10^2+4 \cdot 10+7 \\&\equiv 8 \cdot 1+5 \cdot (-1)+6 \cdot 1+4 \cdot (-1)+7 \\&=12 \\&\equiv 1 \ (\text{mod} \ 11)  \end{aligned}

Thus 85647 is not divisible by 11.

___________________________________________________________________________________________________________________

Exercises

Work the two congruence calculation mentioned at the beginning of the post. Show the following.

    9664^{79081} \equiv 1020 \ (\text{mod} \ 55049)

    2^{57885161}-1 \equiv 255 \ (\text{mod} \ 524287)

___________________________________________________________________________________________________________________

Reference

  1. Dudley U., Elementary Number Theory, 2nd ed., Dover Publications, Inc, New York, 2008

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

One thought on “A basic discussion of congruences

  1. 1. Superb blog! I have learned a lot.
    2. Solved your largest prime number problem (7-22-2013 post) easily with a FAST Powering Algorithm I built from instructions on one of your posts.
    3. Then I noticed that the problem was a special case with 2 Mersenne Numbers (MN) which can be solved in 1 or 2 steps. Simply take y (mod x) where x < y and represent exponents (which can be used to identify a MN). When x =19 and y = 57,885,161 the mod solution is 8 or the 8th MN. The 2nd step would be to either look up the 8th MN (255) or calculate the MN using 8 for the exponent (e) in the MN form 2^(e) – 1 or 2 raised to 8th power -1 = 255.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s