Congruence (superior arithmetic)

The congruence in the upper arithmetic or number theory, is a relationship that allows us to compare two integers, by his remains to the divide for an entire third issue fixed. This is different from zero and one. Preferably it is a positive integer.

Summary

[ hide ]

  • 1 Definition
  • 2 Theorem
  • 3 Properties
  • 4 Partition
    • 1 Denomination
  • 5 Employment
  • 6 Sources
  • 7 See also

Definition

Let k be a natural number. we say that c and d are congruent modulo k if its difference cd is a multiple of k. to denote this we use the notation

c: = d (mod k)

For example: 18: = 14 (mod 4); 44: = 24 (mod 5);

Obviously c: = d (mod k) sss exists s integer such that c = d + sk

Theorem

c: = d (mod k) if only if the divisions of c and d by k provide the same remainder

For this case, the divisions of 31 and 47 by 4 give the same remainder, therefore 31: = 47 (mod 4)

Properties

  1. The congruence relationship is reflexive: c: = c (mod k).
  2. The congruence relationship is symmetric: c: = d (mod k) → d: = c (mod k)
  3. The consistency relationship is transitive:

c: = d (mod k) and d: = e (mod k) → c: = e (mod k)

  1. if c: = d (mod k) and e: = f (mod k) then c + e: = d + f (mod k), compatible with the sum
  2. when c: = d (mod k) and e: = f (mod k) then c · e: = d · f (mod k), compatible with the product
  3. if c: = d (mod k) then if c × l: = d × l (mod k) for any integer l, it does not alter by multiplying by a constant factor
  4. Assumption c: = d (mod k) then if c p: = d p(mod k), here p is a natural number. Supports natural exponent enhancement

8 when c: = d (mod k) and Q (y) is a polynomial with integer coefficients, it follows that Q (c): = Q (d)

Partition

Since the modulus k congruence relationship is reflective, symmetric, and transitive, it determines a partition in the set Z of the integers in k equivalence classes, so that

Any integer is in a class and only one.

If c: = d (mod k) then c and d are in the same equivalence class

The union of all k equivalency classes is equal to the set Z of all integers.

Denomination

the equivalence classes that determine a congruence modulo k, are called the remainder classes modulo k

If we consider the congruence modulo 5, there are five classes of modulo 5 rests: those that give rest 0, 1, 2, 3 and 4

For example in the remainder class 1, module 5 are the integers of the form x = 5k + 1

job

  • To mark the hours of the day we use the remainders of division between 24
  • In classifying the integers into odd and even we use the remainders of division by 2.
  • In the study of the Gaussian cousins ​​we are interested in the congruence module 4.

 

Leave a Comment

Scroll to Top