# What is the last digit of 6 811

## Chapter 3.1 Basics of congruences

Some problems that seem simple in principle have very large numbers that can easily give you a headache when trying to solve them. Here are three examples of such problems that we will solve in the course of this section:

• Divisibility: Is 222555+555222 divisible by 7?
• End digits: Which three digits does F end on73= ?
• Checksums: what is the checksum of the checksum of the checksum of 44444444?

To solve these and a large number of related problems, a set of tools will be developed below. The "trick" is not to look at all whole numbers, but to break them down into certain ones beforehand Classes and then continue to work with these (finitely many) classes. It is easy to explain what one has to imagine under such classes:

Every natural number m> 1 can be used to divide the whole numbers into groups of remainders, so-called Residual classes, to divide. If you choose m = 8, for example, the numbers 5, 13, 21, 29, but also -3, -11, -19 all leave the same remainder 5 when dividing by m (note: 21 = 2 8 + 5, -3 = -1 * 8 + 5, -19 = -3 * 8 + 5, etc.). The numbers -17, -9, -1, 7, 15, ... also belong in a remainder class. If one denotes these remainder classes after the smallest positive remainder, then:

0*: = {..., - 24, -16, -8,0,8,16,24, ...} = {x x = k · 8 + 0 and kZ}
1*: = {..., - 23, -15, -7,1,9,17,25, ...} = {x x = k · 8 + 1 and kZ}
.....................................................................................
7*: = {...., - 17, -9, -1,7,15,23,31, ..} = {x x = k · 8 + 7 and kZ}

Then the elements are repeated so that you get exactly 8 classes. Actually one should still set indices for the classes according to the number that determines the remainder. However, since this is generally evident from the context, the index is omitted for the sake of simplicity. This number, in our example 8, is called the "module" that generates the remainder of the class and the following designation is introduced:

DEFINITION 3.1
Two whole numbers a and b are called "congruent modulo m"(mN>1), if they leave the same remainder r when divided by m.
In characters: from mod m a = k m + r and b = l m + r with k, l Z and 0r

Example: 37 73 mod 6, because 37 = 6 6 + 1 and 73 = 12 6 + 1, but 37 73 mod 7, because 37 = 57 + 2 and 73 = 10 7 + 3. (Unfortunately I have not found a character set that provides a "non-congruent character" - so a "" must be used instead.)
12100 mod 11, because 1210 = 110 11 + 0

So a b mod m applies if a and b are in the same remainder class mod m. Any module m> 1 generates the m remainder classes 0*, 1*, 2*, ..., (m-1)*. A selection of m numbers that come in pairs from different remainder classes mod m is called a "complete remainder system mod m" and we write R for itm (also Z \ m). For example, the numbers 16, -7,2,43, -12,13, -2 and 23 form a complete remainder of the system mod 8. For the sake of simplicity, however, one usually chooses R.8= {0,1,2,3,4,5,6,7} and - also for the sake of simplicity - leaves out the asterisks.

EXERCISE 3.1
a) In which remainder classes do the numbers 67, 2345, 99876, -345, -12333 belong with regard to modules 8 or 13 or 137?
b) True or False? If wrong, correct:
34521 mod 47 879360 mod 123 345129 335 mod 789

EXERCISE 3.2
Determine in each case the smallest natural number n, for which the following applies:

 a) 39n mod 5 b) -39n mod 5 c) 23768n mod 11709 d) n234 mod 11 e) 24517 mod n f) 789182 mod n g) 1111162 mod n h) 22112111 mod n i) n82 mod 131 n> 82

EXERCISE 3.3
Calculate all nN with:

 a) 187 410 mod n b) 35 n0 mod 7 c) 35n0 mod 11 d) 22 n1 mod 7 e) 345n7 mod 133 f) 35 n9 mod 135

Next we want to deal with the rules of the operations with the newly introduced remainder classes. As we shall see in a moment, you can count on them in almost the same way as in Z

So let r* and s* two remainder classes mod m. If we take a representative (technical jargon: representative) from each of these classes, e.g. a = k · m + r and b = l · m + s, then the sum a + b = (k + l ) M + (r + s). If r + s * and s* a representative of class t* is. So we can also say briefly: r*+ s*= t*, where t* is clearly determined. So we have an addition to Rm Are defined.

Accordingly, we can ensure a multiplication. With the notations above, the following applies: ak · b = (klm + ks + rl) · m + rs, that is, the remainder of the product of a and b when divided by m only depends on which remainder a and b itself when dividing let through m, ie from which remainder class a and b come; otherwise nothing need be known about the nature of a and b. So we can say analogously to addition: r*· S*= t*, where t* is clearly determined. So we also have a multiplication on Rm Are defined.

If it is clear from the context that you are dealing with the remainder classes mod m, you omit the unwieldy asterisks on the remainder classes. We want to do that now when we look at the links in some remainder classes:

R.2:

R.3:

 + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1
 · 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

R.5:

 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3
 & middot 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

Some things take a bit of getting used to when you inspect the tables: e.g. 2 4 = 3 in R5 or 2 * 2 = 1 in R3. But other things are simple as usual: x · 0 = 0 in all examples or also x + 0 = x. One can also solve equations:

2x + 4 = 1 + (- 4) [-4 denotes the additively inverse element of 4, i.e. 1]
2x = 2 (2-1) [correspondingly is 2-1 the multiplicative inverse to 2, so 3]
x = 2 * 3
x = 1

EXERCISE 3.4
Solve the following equations in R.5:
a) 3x + 2 = 2 b) 4x + 2 = 4 c) 3x-1 = 3 d) x2= 4 e) x2-1 = 4 f) x2=2

Let's look at another example:
R.6:

 + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4
 · 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

Obviously, things are no longer so simple here. The addition table looks quite neat - every element appears in every row and every column; however, the multiplication table leaves something to be desired. For example, if you look for the inverse of the multiplication of 3, you will be disappointed: There is no element xR6 with 3 x = 1. The equation 3x + 2 = 0 cannot be solved either, because it is equivalent to 3x = 4 - and that this equation cannot be solved can be seen in the corresponding column of the multiplication table.

Why is it that there are very pleasant and handy linkage tables and corresponding disgusting pieces?

EXERCISE 3.5
Place addition and multiplication tables for R.10 and R11 on. Then solve each of the following equations in R.10 and R11. Do a sample!
a) 7x + 8 = 5 b) 5x + 9 = 3 c) 6x-2 = 8 d) 4x + 9 = 8 e) x2=5

It would of course be cumbersome to have to stand up for various m addition and multiplication tables on all possible occasions. No, you can use the calculus introduced above quite easily and directly. For this purpose, we will set up and prove the calculation rules for congruences in the following, in order to then use them to solve the problems mentioned above and many more.
The first sentence gives us some simple transformations that we will make great use of in the following proofs:

SENTENCE 3.1
from mod m a-b 0 mod m ma-b

Proof: ab mod m a = k m + r b = l m + r a-b = (k m + r) - (l m + r) = (k-l) m + 0 a-b0 mod m m a-b

SENTENCE 3.2 (Calculation rules for congruences)
For a, b, c, dZ and mN>1 applies:
(K1) from mod m ba mod m
(K2) from mod m bc mod m ac mod m
(K3) from mod m a + c b + c mod m
(K4) from mod m a c b c mod m
(K5) from mod m anbn mod m for nN
(K6) ab mod m cd mod m a + c b + d mod m
(K7) from mod m c d mod m a · cb · d mod m
(K8) gcd (m, n) = 1 a b mod m a b mod n from mod m n
(K9) a b0 mod p p prim a 0 mod p b0 mod p
(K10) ggT (a, m) = 1: a ba c mod m bc mod m (reduction rule)

Proof of (K3): Before .: from mod m, i.e. a-b 0 mod m
to show: (a + c) - (b + c) 0 mod m
in fact: (a + c) - (b + c) = a-b0 as expected. (q.e.d.)

Proof of (K4): to show: m ac-bc
holds, because because of ma-b we have mc (a-b) = ac-bc

Proof of (K5): m a-b a-b an-bn (Chapter 1, Sentence 2) m an-bn

EXERCISE 3.6
Prove the rules (K1), (K2), (K6) and (K7).

EXERCISE 3.7
Show with two examples and two counterexamples that the additional requirements in rules (K8), (K9) and (K10) are necessary.

Proof of (K8): m from n from from = km from = ln km = ln ml (because of gcd (m, n) = 1) l = tm km = (tm) n = t (mn) from = t (mn) mna-b (qed)

Proof of (K9): For prime numbers p the following applies: if p does not divide a and p does not divide b, then p does not divide a · b either. This statement is equivalent to: If p divides a · b, then p divides a or p divides b. But that is the claim!

Proof of (K10): "" mab-ac = a (b-c) m does not divide a mb-c
"mb-c ma (b-c) mab-ac

Now we are able to solve the first of the problems posed at the beginning:

222 = 31 7 + 5, i.e. 2225 mod 7 (with K5) 2225555555 mod 7
Now let's examine 5n mod 7:
52 4 mod 7 53=5254 5 = 20 6-1 mod 7
so summarized: 2225555555 5185·3=(53)185 (-1)185= -16 mod 7
The same procedure is used with the second summand:
5552222222=(23)74174= 1 mod 7
From both considerations and (K6) it finally follows:
222555+555222 -1 + 1 = 0 mod 7, so 7 divides 222555+555222.
(for information only: 222555 has 1303 digits, 555222 at least 610 digits!)

In addition to some useful sentences that we will derive later, the algorithm used in the following example (consecutive squaring) helps with problems with high powers:

wanted 2960 mod 99
We first calculate:

 292= 84149 mod 99 294=(292)2 492= 240125 mod 99 and likewise 298252= 62531 mod 99 2916312= 96170 mod 99 2932702= 490049 mod 99

So: 2960=2932+16+8+4=2932·2916· 298·294 (49 x 70) x (31 x 25) = 3430 x 775 64 x 82 = 52481 mod 99

EXERCISE 3.8
(I) Compute a) 3177 mod 57 b) 123345 mod 678 c) 731100 mod 567
(II) Which digits end in a) 6811 b) 21000 c) 3999 d) 6787 ?
(III) Find the last two digits of the powers from (II)!

EXERCISE 3.9
Examine the terms (a) 1055-5510 and (b) 111101-79100 on their remainder when dividing by 3, 4, 5, 7, 9, 11, 19 and 23.

EXERCISE 3.10
a) Show: (1 + 9 + 9 + 3)1+9+9+4- (1 + 9 + 9 + 5) 1 + 9 + 9 + 2 mod (1 + 9 + 9 + 4)
b) Is 1 + 19951995 divisible by 1996?
c) Is 19951994-19931994 divisible by 4?

We can now also more easily solve linear congruences according to any modules:

Calculate: 37 x15 mod 19
We transform: 37x = k · 19 + 15 37x-19k = 15: We have already solved such equations in 2.3. We even already know when these equations can be solved! It has to be a divisor of 15, which is obviously true. The BA continues:

 37 1 0 0 19 0 1 1 18 1 -1 1 1 -1 2 18 0 - - .

So x is0= -1 and thus x = -15 4 mod 19. We check: 37 4 = 148 = 7 19 + 15.
This is of course only one solution among an infinite number, but the smallest positive one.

According to the example, it immediately follows

SENTENCE 3.3
The linear congruence ax b mod m is solvable if and only if gcd (a, m) b. The solutions of the equation are obtained from ax-my = b according to Theorem 2.2.

Remark 1: Theorem 3.3 ensures that a · x 1 mod p for GCF (a, p) = 1 is uniquely solvable. Thus for primes p there exists for every a

p) is a multiplicative inverse element. So this answers the question on page 3 below.

Note 2: Incidentally, it is not always necessary to work with the BA, as the following example shows:

 88x16 mod 84 (*) 22x4 mod 21 (22 1 mod 21) x4 mod 21
The step (*) is explained as follows: 88x 16 mod 84 88x = 84k + 16 22x = 21k + 4 22x 4 mod 21; so one can divide ax b mod c by gcd (a, b, c).

EXERCISE 3.11
Solve the following linear congruences:

 a) 23x47 mod 253 b) 67x1 mod 127 c) 1243x1000 mod 2347 d) 12123x8765 mod 42017 e) 11101x11102 mod 42073 f) 7307x1001 mod 9999 g) 21x35 mod 77 h) 88x10 mod 84 i) 1210x 396 mod 77
 With the adjacent button you can start an exercise program for linear congruences.

EXERCISE 3.12
Often the multiplicative inverse to x is of interest. Calculate:
a) 66x1 mod 109 b) 96x1 mod 173 c) 324x 1 mod 381

 With the adjacent button you can start an exercise program for calculating the multiplicative inverse.

Remark 3: Diophantine equations can also be solved with the help of the calculus of linear congruences.
Example:

 7x + 3y = 29 (*) 7x = 3y + 29 7x29 mod 3 x2 mod 3 x = 3k + 2 in (*): 3y = 29-7x = 29-7 (3k + 2) = 15-21k y = 5-7k

Solve with this procedure:
(1) 10x + 8y = 6 (2) 33x + 21y = 9 (3) 22x-443y = 159 Download Kap3_1 (19 KB)     