Congruence Equations

11 Key excerpts on "Congruence Equations"

• 

  eBook - PDF

  The Higher Arithmetic

  An Introduction to the Theory of Numbers

  • H. Davenport(Author)
  • 2008(Publication Date)
  • Cambridge University Press

    (Publisher)

  A linear congruence, by analogy with a linear equation in elementary algebra, means a congruence of the form ax ≡ b (mod m). (2) It is an important fact that any such congruence is soluble for x , pro- vided that a is relatively prime to m. The simplest way of proving this is to observe that if x runs through the numbers of a complete set of residues, then the corresponding values of ax also constitute a complete set of residues. For there are m of these numbers, and no two of them are con- gruent, since ax 1 ≡ ax 2 (mod m) would involve x 1 ≡ x 2 (mod m), by the cancellation of the factor a (permissible since a is relatively prime to m). Since the numbers ax form a complete set of residues, there will be exactly one of them congruent to the given number b. As an example, consider the congruence 3x ≡ 5 (mod 11). 34 The Higher Arithmetic If we give x the values 0, 1, 2, . . . , 10 (a complete set of residues to the modulus 11), 3x takes the values 0, 3, 6, . . . , 30. These form another com- plete set of residues (mod 11), and in fact they are congruent respectively to 0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8. The value 5 occurs when x = 9, and so x = 9 is a solution of the congru- ence. Naturally any number congruent to 9 (mod 11) will also satisfy the congruence; but nevertheless we say that the congruence has one solution, meaning that there is one solution in any complete set of residues. In other words, all solutions are mutually congruent. The same applies to the gen- eral congruence (2); such a congruence (provided a is relatively prime to m) is precisely equivalent to the congruence x ≡ x 0 (mod m), where x 0 is one particular solution. There is another way of looking at the linear congruence (2). It is equiv- alent to the equation ax = b + my , or ax − my = b. We proved in I.8 that such a linear Diophantine equation is soluble for x and y if a and m are relatively prime, and that fact provides another proof of the solubility of the linear congruence.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Theory of Numbers

  Second English Edition (edited by A. Schinzel)

  • W. Sierpinski(Author)
  • 1988(Publication Date)
  • North Holland

    (Publisher)

  CHAPTER V CONGRUENCES 1. Congruences and their simplest properties Let a and b be two integers. We say that a is congruent to b with respect to the modulus m if the difference of a and b is divisible by m. Using the notation introduced by Gauss, we write (1) a == b (mod m). Thus formula (1) is equivaient to the formula mia-b. It is clear that, if two integers are congruent with respect to the modulus m, then the division of either of them by m gives the same remainder and vice versa. There is an analogy between congruence and equality (this justifies the use of the symbol ==, similar to the symbol of equality). We list here some of the more important properties which illustrate this analogy: I. Reflexivity means that every integer is congruent to itself with respect to any modulus; i.e. a == a (mod m) for any integer a and any natural number m. To prove this it is sufficient to observe that the number a -a = 0 is divisible by every natural number m. II. Symmetry means that congruence (1) is equivalent to the congru-ence b == a (mod m). To prove this it is sufficient to note that the numbers a -band b -a are either both divisible or both not divisible by a natural number m. III. Transitivity means that, if a == b (mod m) and b == c (mod m), then a == c (mod m). To prove this we apply the identity a-c = (a-b)+(b-c) CH 5,1] CONGRUENCES AND THEIR SIMPLEST PROPERTIES 199 and recall the fact that the sum of two numbers, each of them divisible by m, is divisible by m. Similarly, it is very easy to prove some other properties of congruence. We prove that two congruences can be added or subtracted from each other provided both have the same modulus. Let (2) a = b(modm) and c = d(modm). In order to prove that a + c = b + d (mod m) and a -c = b -d (mod m) it is sufficient to apply the identities (a+c)-(b+d) = (a-b)+(c-d) and (a-c)-(b-d) = (a-b)-(c-d). Similarly, using the identity ac-bd = (a-b)c+(c-d)b, we prove that congruences (2) imply the congruence ac = bd (mod m).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Mathematical Foundations of Public Key Cryptography

  • Xiaoyun Wang, Guangwu Xu, Mingqiang Wang, Xianmeng Meng(Authors)
  • 2015(Publication Date)
  • CRC Press

    (Publisher)

  C H A P T E R 3 Congruence Equations T he main focus of this chapter is to introduce the solvability of Congruence Equations in one variable and systems of linear con-gruence equations and provide some concrete methods for finding their solutions. For a system of linear Congruence Equations, we will mainly discuss how to solve them using the Chinese remainder theorem. For general Congruence Equations, we describe a general process of finding solutions. For quadratic Congruence Equations, we consider the case of prime modulus, that is, the quadratic residue problem with prime modulus. Finally, we introduce an arithmetic function that is related to the quadratic residues, the Legendre symbol, and define a more general arithmetic function, the Jacobi symbol. The content of this chapter consists of not only key materials for the congruence theory in elementary number theory, but also the most important and fundamental theory for public key cryptography. Various methods of solving Congruence Equations can contribute signifi-cantly to the design and analysis of many cryptographic algorithms. For example, solving linear Congruence Equations is one of the most basic operations for the encryption, decryption, and even breaking of many cryptosystems; the Chinese remainder theorem has played important roles in efficient implementations of several cryptographic systems, and it also has a direct application to the design of cryptographic systems of special forms; quadratic residues and the Jacobi symbol can be used in the primality testing and pseudorandom number generators. 3.1 BASIC CONCEPTS OF CONGRUENCES OF HIGH DEGREES In this section, we will mainly introduce general congruence equa-tions and related concepts. We will also touch on simplified forms 47 48 Mathematical Foundations of Public Key Cryptography of Congruence Equations. Unless otherwise stated, the congruence equation mentioned here will be a congruence equation with one variable.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Public Key Cryptography

  Applications and Attacks

  • Lynn Margaret Batten(Author)
  • 2013(Publication Date)
  • Wiley-IEEE Press

    (Publisher)

  2 Congruence Equations

  In this chapter, we introduce three areas of mathematics needed for the development of the theory and implementation of the public key cryptographic systems discussed in this book. Mathematical systems of most use in developing cryptographic algorithms are finite systems, as computers are by nature finite. Thus, we deal with finite or discrete number systems. The three topics we cover are first congruence arithmetic, second the Euclidean algorithm, and finally, the dual concepts of exponential and logarithmic equations in the discrete setting of congruence arithmetics.

  Congruence arithmetic is essentially arithmetic in discrete number systems. The standard arithmetic operations of addition, subtraction, multiplication, and division are needed. The first three of these are easy enough to define, but division is a little more complex, and not always available! The Euclidean Algorithm, presented in Section 2.2, is a very efficient method of enabling division in discrete systems. Perhaps surprisingly, this algorithm will be useful in every chapter of the book.

  In Section 2.3 of this chapter, we show how to use the arithmetic of discrete systems to establish keys for securing data in transit. We then go on in Section 2.4 to show how this same congruence arithmetic can be used to attack the key establishment method.

  2.1 Congruence Arithmetic

  In many early symmetric key cryptosystems, the basis was the alphabet used in everyday writing. Thus, we might use today's English alphabet based on 26 letters. Other alphabets have different numbers of letters, and even additional symbols, but the principle is the same. In our case, we have to choose 26 numbers that will correspond to these 26 letters. We use the numbers 0, 1, 2, 3, ..., 25 to correspond to a , b , c , d

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Elementary Theory of Numbers

  • William J. LeVeque(Author)
  • 2014(Publication Date)
  • Dover Publications

    (Publisher)

  3–6 Polynomial congruences. As is well known, the equality sign is used between polynomials in two essentially different ways. In the equation

  (x + a )2 = x 2 + 2ax + a 2 ,

  for example, it means that the left- and right-hand sides are identical polynomials, i.e., that the coefficients of x 2 , and of x , are equal, as are the constant terms. In the equation x 2 − 2 = 0, it means that the square of the number x is equal to 2, and this may be true or false for particular x . If we temporarily refer to the first as algebraic equality, and to the second as numerical equality, there is the following connection between them: if two polynomials are algebraically equal, they are also numerically equal for every value of x , and if two polynomials are numerically equal for every value of x (or even for infinitely many values of x ), then they are algebraically equal.

  The congruence symbol is also used in two different ways, to relate polynomials. When f (x ) and f 1 (x ) are polynomials, we write

  if the coefficients of each power of x in f and f 1 are congruent (mod m ). For example,

  (x + a )2 ≡ x 2 + a 2 (mod 2),

  and

  This meaning of the congruence symbol is usually intended when there is no reference to numerical values of x , or to roots or solutions of the congruence. The other meaning of the symbol is that x is a number for which the numerical values f (x ) and f 1 (x ) are congruent (mod m ).

  It should be noted that the connection indicated above between the two meanings of equality does not extend to congruences; that is, (1) is not equivalent to

  f (x ) ≡ f 1 (x ) (mod m )      for all x ,

  since, for example, x 3 ≡ x (mod 3) for all x , whereas obviously x 3 and x are not “algebraically” congruent (mod 3).

  There are other ways as well in which polynomial congruences behave differently from polynomial equations. It is a theorem (though possibly not one familiar to the reader) that every polynomial with integral coefficients factors in a unique way into irreducible polynomials with integral coefficients. The congruence (2) above shows that this is no longer true for polynomials whose coefficients are integers (mod 6), since the two factorizations given for x 2 − x are genuinely different, while the linear factors are clearly incapable of further factorization, and so are irreducible. We also see from (2) that there is no general analog of the familiar theorem from algebra that the number of roots of a polynomial equation is equal to the degree of the polynomial, since the quadratic congruence x 2 − x ≡ 0 (mod 6) has the four solutions x ≡ 0, 1, 3, 4 (mod 6). If there were fewer solutions than the degree would indicate, there might be some hope of finding further ones by considering larger number systems, in much the same way that the equation x 2

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Theory of Numbers

  • C Y Hsiung(Author)
  • 1992(Publication Date)
  • WSPC

    (Publisher)

  Chapter 2. CONGRUENCES In the above chapter, we have discussed the divisibility by means of the divisor. But the discussion is only for the individual integer. How shall we do it for the whole of integers? We proceed as follows. To divide the whole set of integers by a fixed integer, we get a set of remainders, then the whole of integers can be separated into classes according to their remainders such that two integers are in a same class if and only if they have the same remainder. We discuss the properties of the integers in the same one class, and the properties of integers in different classes. Then the properties of the whole of integers can be obtained. In the following chapters, we shall use this same remainder theory, or congruence, to study the problems. In this chapter we introduce the elementary concepts and elementary properties of congruences. The concept of congruence was proposed by K. F. Gauss about 1800. His notation simplifies the proof of theorems that would have been difficult even to state without it. Congruences often arise in everyday life. For instance, if the second of January is Sunday, then 9, 16, 23, 30 of the same month are all Sundays, since when they are divided by 7, the remainders are all 2. 51 52 Elementary Theory of Numbers 2.1. Concept of Congruence and its Elementary Properties From Sec. 1.1 Theorem 2 we have remainder and quotient, but the remainder is always used. Let ra be a positive integer. Two integers a and 6 leave remainders when divided by m. If the remainders are the same, we say that a is congruent to b modulo ra, and write a = b (mod ra) or a = 6(ra) . If the remainders are different, we say that a and b are incongruent modulo ra, and write a ^ b (mod ra) or a ^ b(m) . Evidently, if a and b are congruent modulo ra, then ra|(a—6); if a and 6 are incongruent modulo ra, then ra/ (a — 6). Hence the necessary and sufficient condition that a = 6 (mod ra) is ra|(a — 6).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Proofs and Ideas

  A Prelude to Advanced Mathematics

  • B. Sethuraman(Author)
  • 2021(Publication Date)
  • American Mathematical Society

    (Publisher)

  9 Equivalence Relations Much of mathematics consists of studying objects governed by some loose notion of equality. The meaning of this will become clearer as we study more examples later in the chapter (and in other courses as you proceed further in your study of mathematics), but here is an example from high school geometry: when we study triangles in the plane, we typically do not differentiate between congruent triangles—all that matters to us is the lengths of the three sides, not where it is located in the plane or how it is aligned. Here is another example, this time from trigonometry: when considering trigonometric ratios in right triangles, we do not differentiate between similar right triangles—all that matters to us is the angles in that right triangle, not the lengths of the sides. And here is an example that you have already considered in Exercise 1.3.1, Chapter 1: we create a new number system ℤ/2ℤ by considering all even integers to be a new number, and all odd integers to be another new number, that is, we do not differentiate between two integers that leave the same remainder on dividing by 2 —all that matters to us is whether the remainder is 0 or 1 . We will develop in this chapter the machinery to describe this concept of objects being the same up to some loose notion of “sameness.” The basic idea that we will consider is that of a relation on a set (and more generally, of a relation from a set ? to a set ? ). We will specialize this notion of relation to the notion of an equivalence relation, which is precisely the concept used in mathematics to specify an appropriate notion of sameness. 9.1 Relations, Equivalence Relations, Equivalence Classes To motivate the definition of relations, let us consider the following: Example 9.1. Take ? to be the set of all adults in a room, and take ? to be the set of all children.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Modern Algebra

  An Introduction

  • John R. Durbin(Author)
  • 2015(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER III EQUIVALENCE. CONGRUENCE. DIVISIBILITY The first section in this chapter is devoted to equivalence relations, which occur often not only in algebra but throughout mathematics. The other sections are devoted to elementary facts about the integers. These facts are used to construct examples of groups and of other algebraic systems yet to be introduced. They will also help us understand some of the elementary facts about groups to be proved in the next chapter. SECTION 9 EQUIVALENCE RELATIONS Consider the following statements: 1. If x , y ∈ R, then either x = y or x = y . 2. If x , y ∈ R, then either x ≤ y or x ≤ / y . 3. If ABC and DEF are triangles, and ∼ = denotes congruence, then either ABC ∼ = DEF or ABC  ∼ = DEF. In each statement, there is a set (R, R, and all triangles, respectively) and a relation on that set (=, ≤, and ∼ =, respectively). The relationship may or may not hold between ordered pairs of elements from the set. We are concerned now with relations of this type that satisfy three specific conditions. (The symbol ∼ in the following definition is read tilde.) Definition. A relation ∼ on a nonempty set S is an equivalence relation on S if it satisfies the following three properties: If a ∈ S, then a ∼ a. reflexive If a, b ∈ S and a ∼ b, then b ∼ a. symmetric If a, b, c ∈ S and a ∼ b and b ∼ c, then a ∼ c. transitive 52 SECTION 9 EQUIVALENCE RELATIONS 53 Of the relations in 1, 2, and 3, the first and third are equivalence relations, but the second is not (because it is not symmetric). In the first relation, R can be replaced by any nonempty set, and the result will still be an equivalence relation; that is, for any nonempty set S, equality (=) is an equivalence relation on S. If ∼ is an equivalence relation and a ∼ b, we say that a and b are equivalent, or we use the specific term involved if there is one (such as equal or congruent).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Guide to Abstract Algebra

  • Carol Whitehead, David A Towers(Authors)
  • 2003(Publication Date)
  • Red Globe Press

    (Publisher)

  Rela tion s Notation The statement 'a is congrue nt to b modul o m' is written symbolically as a = b (mod m ). Equivalent statements of the definition of congruence The definition of congruence can be expressed symbolically as follows: 45 (a) a = b (mod m) {:} there exists k E 7L such t hat a - b = km. (b) a = b (mod m) {:} there exists k E 7L such tha t a = b + km. (This is just a slight rearrangement of definition (a).) (c) a = b (mod m) {:} a and b leave the same remainder on division by m . You sho uld convince yourself that we are really saying the same thing in thre e slightly different ways; that is, any pair of integers which are congruent by any one definition will also be congruent by either of the other two. In (c), we assume that when we divide a numb er by m, we can always choo se the quotient so that the remainder is one of the numbers 0, I, ... ,m - 1. We shall prove in Chapter 4 that in this case, the quotient and remainder are uniquely determined. 1. 33 = 23 = 193 = 3 (mod 10). 2.2 = - 5=- 12 =23( mod 7). • In Chapter 4 we look at the arithmetic of congruence relations in detail. In this chapter, our interest in them is explained by the following theorem. Proof (i) We show rv is reflex ive. Let a E 7L . Then a - a = 0 = Om . Hence a = a (mod m) and so a rv a, V a E 7L. (ii) We show rv is symmetric. Let a, b E 7L and suppose a rv b. The n a - b = km for some k E 7L . But a - b = km =} b - a = ( -k)m =} b = a (mod m), since - k E 7L . Hence a rv b =} b rv a, V a,b E 7L . (iii) We show rv is transitive. Let a,b, c E 7L and suppose a rv ba nd b rv c. Then there exist integers k,h E 7L such that a - b = km and b - c = hm. Then a - c = (k + h )m and hence a = c (mod m), since k + h E 7L . Thu s a rv band b rv c =} a rv C, V a, b, c E 7L . • 46 Guide to Abstract Algebra Congruence classes The equivalence classes determined by the relation of congruence mod m on 7L are called the congruence (or residue) classes mod m.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Number Theory in Mathematics Education

  Perspectives and Prospects

  • Rina Zazkis, Stephen R. Campbell, Rina Zazkis, Stephen R. Campbell(Authors)
  • 2012(Publication Date)
  • Routledge

    (Publisher)

  The course in which the study was conducted was not specifically focused on providing students with opportunities to make connections between undergraduate and secondary mathematics concepts. The results presented in this chapter suggest that having students examine familiar concepts in a new context provides valuable opportunities for instructors to lead the class to reexamine the structure of fundamental concepts in algebra. It may be that carefully guided experiences in novel and unfamiliar contexts, such as those afforded by elementary number theory, can help preservice teachers develop a more sophisticated mathematical perspective, as well as a deeper understanding of the mathematics they will be teaching.

  Background

  The concept of congruence is related to several different areas of mathematics: elementary and abstract algebra, equivalence, divisibility, and division with remainder. In this section, I review and summarize relevant research on the teaching and learning of these topics.

  The teaching of algebra is arguably the largest component of the job of a secondary school mathematics teacher. Secondary schools in the United States typically offer three levels of courses in algebra, and most universities in the United States require students applying for admission to have completed at least 2 years of algebra study. In addition, algebra is the foundation for much of the mathematics secondary school students will study. According to the National Council of Teachers of Mathematics (2001), algebra is an “essential component of contemporary mathematics and its applications in many fields” (p. 1). Many researchers have emphasized that, in addition to studying a good deal of mathematics at the undergraduate level, prospective teachers need to develop knowledge of mathematics for teaching, an understanding of the underlying processes and structures of concepts, the relationships between different areas of mathematics, and knowledge of students’ ways of thinking and mathematical backgrounds (CBMS, 2001; Fennema & Franke, 1992; Ma, 1999).

  It has become clear in recent years that knowledge of mathematics for teaching is not easily developed. For most prospective teachers, there is what Cuoco (2001) called a vertical disconnect

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Integral Matrices

  • Morris Newman(Author)
  • 1972(Publication Date)
  • Academic Press

    (Publisher)

  Chapter IV Conjyruenoe The material of this chapter finds its application in the theory of quadratic forms and is the basis of much of classical matrix theory and classical number theory. 1. Definition of congruence Let A, B be elements of R,. We say that A is congruent to B (written A B) if there is a unit matrix U of R, such that A = UTBU. Once again this is an equivalence relationship. It is not as strong as similarity since it does not define a homomorphism of R, into R,, but it is certainly more restrictive than equivalence. 2. Definition of quadratic form Let x = [x,, x2, . . . , xnIT be an n x 1 vector with entries from R, and let A = (a,,) be an element of R,. Then the quadratic form associated with A is q = X T A X = c u,lx,x, ISi,lln 56 3. The Skew Normal Form 57 The transformation A -+ UTAU corresponds to the substitution x = Uy, which replaces xTAx by the “congruent form” yTUTAUy. Since the value of q is unchanged if A is replaced by AT, the study of congru- ence transformations is usually restricted to symmetric matrices (those for which AT = A) or skew-symmetric matrices (those for which AT = -A), and these properties are preserved under congruence. As with similarity, the general problem of deciding when two given matrices of R, are congruent is unsolved. In fact, it has not even been solved completely when R is a field. However for the skew-symmetric matrices there is a complete and simple solution, provided that the characteristic of R is not 2. We note that if an elementary row operation is performed on the rows of a matrix, and if the corresponding elementary column operation is then performed on the columns, the net result is the same as applying a congruence transformation, since the elementary column matrix corresponding to the elementary row matrix E is ET. 3. The skew normal form We first treat the skew-symmetric matrices.

  Sign up to read

  Learn more about book