Integers modulo m)

 

It has been kindly ackhnowledged that this lecture was downloaded from the website:http://home.scarlet.be/math for some students learning the congruences.

 

Modular arithmetic is quite a useful tool in number theory. In particular, it can be used to obtain information about the solutions (or lack thereof) of a specific equation. This page gives a fairly detailed introduction. Another good introduction, in the form of an interactive tutorial, can be found in Part 2 of Math Alive: Cryptography. Contents I. An Introductory Example II. Definition and Further Examples III. Properties of Congruence IV. Exercises I. An Introductory Example Everyone knows that set of integers can be broken up into the following two classes: the even numbers (..., –6, –4, –2, 0, 2, 4, 6,...); and the odd numbers (..., –5, –3, –1, 1, 3, 5,...). There are certain generalizations we can make about the arithmetic of numbers based on which of these two classes they come from. For example, we know that the sum of two even numbers is even. The sum of an even number and an odd number is odd. The sum of two odd numbers is even. The product of two even numbers is even, etc. Modular arithmetic lets us state these results quite precisely, and it also provides a convenient language for similar but slightly more complex statements. In the above example, our modulus is the number 2. The modulus can be thought of as the number of classes that we have broken the integers up into. It is also the difference between any two "consecutive" numbers in a given class. Now we represent each of our two classes by a single symbol. We let the symbol "0" mean "the class of all even numbers" and the symbol "1" mean "the class of all odd numbers". There is no great reason why we have chosen the symbols 0 and 1; we could have chosen 2 and 1, or –32 and 177, but 0 and 1 are the conventional choices. The statement "the sum of two even numbers is even" can be expressed by the following: 0 + 0 ≡ 0 mod 2. Here, the "≡" symbol is not equality but congruence, and the "mod 2" just signifies that our modulus is 2. The above statement is read "Zero plus zero is congruent to zero, modulo two." The statement "the sum of an even number and an odd number is odd" is represented by 0 + 1 ≡ 1 mod 2. Those examples are natural enough. But how do we write "the sum of two odd numbers is even"? It is the (at first strange looking) expression 1 + 1 ≡ 0 mod 2. Here the symbols "≡" and "mod 2" are suddenly very important! We have analogous statements for multiplication: 0 × 0 ≡ 0 mod 2, 0 × 1 ≡ 0 mod 2, 1 × 1 ≡ 1 mod 2. In a sense, we have created a number system with addition and multiplication but in which the only numbers that exist are 0 and 1. You may ask what use this has. Well, our number system is the system of integers modulo 2, and because of the previous six properties, any arithmetic done in the integers translates to arithmetic done in the integers modulo 2. This means that if we take any equality involving addition and multiplication of integers, say 12 × 43 + 65 × 78 = 5586, then reducing each integer modulo 2 (i.e. replacing each integer by its class "representative" 0 or 1), then we will obtain a valid congruence. The above example reduces to 0 × 1 + 1 × 0 ≡ 0 mod 2, or 0 + 0 ≡ 0 mod 2. More useful applications of reduction modulo 2 are found in solving equations. Suppose we want to know which integers might solve the equation 3a – 3 = 12. Of course, we could solve for a, but if we didn't need to know what a is exactly and only cared about, say, whether it was even or odd, we could do the following. Reducing modulo 2 gives the congruence 1a + 1 ≡ 0 mod 2, or a ≡ –1 ≡ 1 mod 2, so any integer a satisfying the equation 3a – 3 = 12 must be odd. Since any integer solution of an equation reduces to a solution modulo 2, it follows that if there is no solution modulo 2, then there is no solution in integers. For example, assume that a is an integer solution to 2a – 3 = 12, which reduces to 0 · a + 1 ≡ 0 mod 2, or 1 ≡ 0 mod 2. This is a contradiction because 0 and 1 are different numbers modulo 2 (no even number is an odd number, and vice versa). Therefore the above congruence has no solution, so a couldn't have been an integer. This proves that the equation 2a – 3 = 12 has no integer solution. Less trivially, consider the system of equations 6a – 5b = 4, 2a + 3b = 3. Modulo 2, these equations reduce to 0 + 1b ≡ 0 mod 2, 0 + 1b ≡ 1 mod 2. This says that b is both even and odd, which is a contradiction. Therefore we know that the original system of equations has no integer solutions, and to prove this we didn't even need to know anything about a. As shown by the preceding examples, one of the powers of modular arithmetic is the ability to show, often very simply, that certain equations and systems of equations have no integer solutions. Without modular arithmetic, we would have to find all of the solutions and then see if any turned out to be integers. II. Definition and Further Examples Of course, there is nothing special about the number 2. Any integer (except 0) will work for the modulus m. We now give the mathematical definition of congruence. Definition. Let m ≠ 0 be an integer. We say that two integers a and b are congruent modulo m if there is an integer k such that a – b = km, and in this case we write a ≡ b mod m. Notice that the condition "a – b = km for some integer k" is equivalent to the condition "m divides a – b". In the previous section we used the modulus m = 2. Although we wrote congruences using only 0 and 1, really any integers are valid. Modulo 2, all of the even numbers are congruent to each other since the difference of any two even numbers is divisible by 2: ... ≡ –6 ≡ –4 ≡ –2 ≡ 0 ≡ 2 ≡ 4 ≡ 6 ≡ ... mod 2. Also, every odd number is congruent to every other odd number modulo 2 since the difference of any two odd numbers is even: ... ≡ –5 ≡ –3 ≡ –1 ≡ 1 ≡ 3 ≡ 5 ≡ ... mod 2. Therefore, anywhere we wrote "0" we could have written any other even number, and similarly "1" could have been replaced by any odd number. For example, instead of writing 0 × 1 + 1 × 0 ≡ 0 mod 2, an equally valid statement would have been 10 × (–13) + 27 × 6 ≡ –122 mod 2. Let's now look at other values for the modulus m. For example, let m = 3. All multiples of 3 are congruent to each other modulo 3 since the difference of any two is divisible by 3. Similarly, all numbers of the form 3n + 1 are congruent to each other, and all numbers of the form 3n + 2 are congruent to each other. ... ≡ –9 ≡ –6 ≡ –3 ≡ 0 ≡ 3 ≡ 6 ≡ 9 ≡ ... mod 3. ... ≡ –8 ≡ –5 ≡ –2 ≡ 1 ≡ 4 ≡ 7 ≡ ... mod 3. ... ≡ –7 ≡ –4 ≡ –1 ≡ 2 ≡ 5 ≡ 8 ≡ ... mod 3. How about when m = 1? The difference of any two integers is divisible by 1, so all integers are congruent to each other modulo 1: ... ≡ –3 ≡ –2 ≡ –1 ≡ 0 ≡ 1 ≡ 2 ≡ 3 ≡ ... mod 1. For this reason, m = 1 is not very interesting, and reducing an equation modulo 1 doesn't give any information about its solutions. The modulus m = 12 comes up quite frequently in everyday life, and its application illustrates a good way to think about modular arithmetic — the "clock arithmetic" analogy. If it's 7:00, what time will it be in 25 hours? Since 25 ≡ 1 mod 12, we simply add 1 to 7: 7 + 25 ≡ 7 + 1 ≡ 8 mod 12. So the clock will read 8:00. Of course, we don't need the formality of modular arithmetic in order to compute this, but when we do this kind of computation in our heads, this is really what we are doing. With m = 12, there are only 12 numbers ("hours") we ever need to think about. We count them 1, 2, 3, ..., 10, 11, 12, 1, 2, ... , starting over after 12. The numbers 1, 2, ..., 12 represent the twelve equivalence classes modulo 12: Every integer is congruent to exactly one of the numbers 1, 2, ..., 12, just as the hour on the clock always reads exactly one of 1, 2, ..., 12. These classes are given by 12n + 1, 12n + 2, 12n + 3, ..., 12n + 11, 12n as n ranges over the integers. Of course, the minutes and seconds on a clock are also modular. In these cases the modulus is m = 60. If we think of the days of the week as labeled by the numbers 0, 1, 2, 3, 4, 5, 6, then the modulus is m = 7. The point is that we measure many things, both in mathematics and in real life, in periodicity, and this can usually be thought of as an application of modular arithmetic. III. Properties of Congruence It is fairly easy to show that for any integers a, b, c, and m ≠ 0, the following properties hold: reflexivity: a ≡ a mod m. symmetry: If a ≡ b mod m, then b ≡ a mod m. transitivity: If a ≡ b mod m and b ≡ c mod m, then a ≡ c mod m. Therefore congruence modulo m is an equivalence relation, and this relation partitions the integers into m equivalence classes: mn + 0, mn + 1, mn + 2, ..., mn + (m – 1). (Since 0 ≡ m mod m, we can either choose 0 or m as a representative for the first class. It is conventional to choose 0.) To be a little more formal than we were above, we can write the equivalence class of an integer a as [a]. The brackets signify that this is an equivalence class and not simply a number. In this way we can write ... = [–3m] = [–2m] = [–m] = [0] = [m] = [2m] = [3m] = ..., ... = [–3m + 1] = [–2m + 1] = [–m + 1] = [1] = [m + 1] = [2m + 1] = [3m + 1] = ..., ... = [–3m + 2] = [–2m + 2] = [–m + 2] = [2] = [m + 2] = [2m + 2] = [3m + 2] = ..., ... = [–3m + 3] = [–2m + 3] = [–m + 3] = [3] = [m + 3] = [2m + 3] = [3m + 3] = ..., : ... = [–2m – 1] = [–m – 1] = [–1] = [m – 1] = [2m – 1] = [3m – 1] = [4m – 1] = ... . (Notice that each congruence symbol "≡" has been replaced by equality "=".) With this notation, we have the following property for any integers a and b, which justifies "reduction under addition": [a + b] = [a] + [b]. Similarly, for any integers a and b we have [a · b] = [a] · [b], justifying "reduction under multiplication". (In the fancy language of abstract algebra, these two properties can be summarized by saying that reduction modulo m is a homomorphism of rings. In this case the two rings are the ring of integers and the ring of integers modulo m.) IV. Exercises 1. Show that the system of equations 11x – 5y = 7, +9x + 10y = –3. has no integer solutions. 2. Show that the system of equations 24x – 5y = 10, 11x – 9y = 13. has no integer solutions. 3. Show that if x, y, z are integers such that x2 + y2 = z2, then at least one of them is divisible by 2, at least one is divisible by 3, and at least one is divisible by 5. 4. Show that if x, y, z are integers such that x3 + y3 = z3, then at least one of them is divisible by 7.

ProjectsExpositions Pascal's Simplices • Pythagorean Triples • Regular Polygons Regular Polyhedra • Regular Polytopes • Sums of Consecutive Powers Mathematical Induction • Modular Arithmetic • Polynomial Equations Investigations • Calculators • Popular Books Eric S. Rowland

 

Congruences ( Integers modulo m)

---

---

• Prerequisites
  
• Definition
  
• Properties
  
• Simplification law
  
• Cancellation law
  
• The equation ax = b mod m
  
  • Solvability condition
    
  • Simplify the equation
    
  • Solving the equation

The equation a^x = 1 mod m

• Theorem of Fermat
  
• Euler function phi
  
  • Properties of the Euler function phi
• Generalisation of the theorem of Fermat
  
• The smallest solution of a^x = 1 mod m with (a,m) = 1

Second method to solve ax = b mod m

Solving systems with equations x = a mod m

---

Prerequisites

In this section all letters stand for integers.
The greatest common divisor of n and m is noted as (n,m).
Let d = (n,m). All the linear combinations r.n + s.m of n and m are multiples of d.
If a is a divisor of b we write a | b.

Definition

Let m be a strictly positive integer.

a = b mod m <=> m | (b - a)

In the following sections we assume that m is a strictly positive integer in an expression like 'modulo m' or 'mod m'

Properties

The following properties are easy to prove from the definition.

If a = b mod m and c = d mod m Then a+c = b+d mod m a-c = b-d mod m a.c = b.d mod m an = bn mod m (with n > 0) n.a = n.b mod m

Simplification law

If e divides a, b and m Then a = b mod m <=> a/e = b/e mod m/e

Cancellation law

If (k,m) = 1 Then ak = bk mod m <=> a = b mod m

Proof:

 
        ak = bk mod m

<=>     m | (a-b)k
                        since (k,m) = 1
<=>     m | (a-b)

<=>     a = b mod m

The equation ax = b mod m

Solvability condition

 
        ax = b mod m  has a solution x
<=>     there is a k and an x such that ax - b = km
<=>     there is a k and an x such that ax - km = b
<=>     there is a linear combination of a and m that gives b.
<=>     b is a multiple of (a,m)

The last assertion holds because all linear combinations of a and m are exactly all the multiples of (a,m)

ax = b mod m has a solution <=> b is a multiple of (a,m)

Simplify the equation

To solve the equation ax = b mod m, first check if the solvability condition is satisfied.
Then d = (a,m) divides a, b and m. So, the equation can be simplified to

 
        ax/d = b/d mod m/d

<=>     a'x = b' mod m'   with (a',m')=1

If (a',b') is k, then we can use the cancellation law, to simplify the last equation.
Example:
18x = 6 mod 8 (18,8)=2 is a divisor of 6. The solvability condition is satisfied. Simplification law gives 9x = 3 mod 4 and the cancellation law gives 3x = 1 mod 4

Solving the equation

We start with the simplified equation ax = b mod m with (a,m)=1.
Take the (m-1) multiples a ; 2a ; 3a ; ... ; (m-1)a all taken mod m . All these multiples are different!
If for instance 3a = 5a mod m then canceling a we have 3 = 5 mod m and this is impossible because 3 and 5 are smaller than m. Hence, all these multiples are the numbers 1,2,3,...,m-1 in an arbitrary order. Therefore, the equation ax = b mod m has just one solution modulo m. In previous example, we try x = 1, 2 and 3 and we find that (3 mod 4) is the solution.

The equation a^x = 1 mod m

Now consider the equation

 
        ax  = 1 mod m

The theorem of Fermat gives a solution for a special case.

Theorem of Fermat

If p is prime and (a,p)=1 then a(p-1) = 1 mod p.

Proof:
From above we know that since (a,p)= 1, the (p-1) multiples
a mod p ; 2a mod p ; 3a mod p ; ... ; (p-1)a mod p
are the numbers 1,2,3,...,p-1 in an arbitrary order.
Hence,
(1a)(2a)(3a)...((p-1)a)= 1.2.3. ... .(p-1) mod p
Since (1,p)=(2,p)=(3,p)=..(p-1,p)=1 , we can use the cancellation law.

 
So,
        a(p-1)   = 1 mod p

Euler function phi

Say m is a positive integer.

phi(m) = the number of positive integers n < m such that (n,m)=1.

Properties of the Euler function phi

It can be proved that :

If p is prime then phi(p) = p-1 and phi(p2)=p.(p-1) If (a,b)=1 then phi(a.b) = phi(a).phi(b)

Generalisation of the theorem of Fermat

If (a,m) = 1 then aphi(m) = 1 mod m.

Proof:
Take all the numbers b from the set {1, 2, ... m} such that (b,m)=1.
Let b₁, b₂,..., b_n be these numbers. n = phi(m) . Take the multiples a.b₁ mod m, a.b₂ mod m, ...,a.b_n mod m All these numbers are different!
If for instance a.b_i = a.b_j mod m then from the cancellation law, we have b_i = b_j mod m and this is impossible.
Additionally, each number a.b_i is relative prime to m since a and b_i are relative prime to m. Therefore, these n different numbers
a.b₁ mod m, a.b₂ mod m, ...,a.b_n mod m
are the n different numbers relative prime to m.
So, these numbers are b₁, b₂,... b_n in an arbitrary order. Hence, (a.b₁)(a.b₂)...(a.b_n) = b₁.b₂. ... .b_n mod m

 
Using the cancellation law, we have

        aphi(m)      = 1 mod m

The smallest solution of a^x = 1 mod m with (a,m) = 1

Let n be the smallest strictly positive integer such that

 
           an  = 1 mod m

Now we make the euclidian division phi(m) : n. It gives us a quotient q and a remainder r. phi(m) = n.q + r with r < n or r = 0. Hence,

 
        1 = aphi(m)  = an q + r = 1. ar mod m  => ar = 1 mod m

This is impossible unless r = 0.
Thus phi(m) = n.q + 0 and n divides phi(m). Conclusion

The smallest strictly positive integer n such that an = 1 mod m is a divisor of phi(m).

Second method to solve ax = b mod m

We start with the simplified equation ax = b mod m with (a,m)=1.
Then,

 
                  a. x = b mod m

             multiply both sides with aphi(m)-1

<=>     a.aphi(m)-1 . x = b.aphi(m)-1          mod m

<=>                 x = b.aphi(m)-1            mod m


      b.aphi(m)-1    mod m  is the unique solution!

Solving systems with equations x = a mod m

This topic is treated via this link.

---

Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

The tutorial address is http://home.scarlet.be/math/

Copying Conditions

Send all suggestions, remarks and reports on errors to Johan.Claeys@ping.be The subject of the mail must contain the flemish word 'wiskunde' because other mails are filtered to Trash

---