Congruences : Number Theory #Congruences #: #Number #Theory

Congruences :

The property of congruence provides a way of classifying integers according to the remainder obtained upon division by a fixed positive integer. In fact the remainder is the only thing of interest.

In this section we study a relation on the integers that is defined in terms of remainders.

Definition :

Let m be a fixed positive integer and a,b 𝛜 Z. 'a' is said to be " congruent to 'b' modulo m " if m/(a-b).

Notation :

'a' is congruent to 'b' modulo m is denoted by a ≡ b mod m.

If m / (a-b) , then we say that 'a ' is not congruent to 'b' modulo m and write a ≢ b(modm).

Note:

* a ≡ b (modm) ⇔ m / (a-b) ⇔ a-b = qm , q 𝛜 Z ⇔ (a-b) is a multiple of m.

* m / a ⇔ a ≡ 0 (mod m)

for example : 5 / (18 - 3 ) 18 ≡ 3 (mod 5 )

7 / 17 - (-4) 17 ≡ -4 (mod 7 )

Results :

* Two integers a and b are congruent modulo m iff they leave the same remainder when divided by m.

* For a fixed integer m > 0 the relation a ≡ b (mod m) is an equivalence relation on the set of integers Z.

* If a ≡ b (mod m) and x 𝛜 Z then i) a ± x ≡ b ± x(mod m)

ii) ax ≡ bx (mod m)

* If a ≡ b (mod m) and c ≡ d (modm) then i) a+c ≡ b+d (mod m)

ii) ac ≡ bd (mod m)

iii) a-c ≡ b-d (mod m)

* We write a+c ≡ b+d (mod m) as a+_mc = b+_md and

ac ≡ bd (mod m) as ax_mc = bx_md

* ab ≡ ac (mod m) and (a,m) = 1 , then b ≡ c (mod m)

* ab ≡ ac (mod m) ⇔ b ≡ c (mod m/(a,m)).

* a ≡ b (mod m) and n is a positive divisor of m then a ≡ b (mod n)

* ax ≡ ay (modm) ⇔ x ≡ y (mod ( m / (a,m) )

Residue Classes or Congruence Classes :

We know that an equivalence relation on a set splits the set into anumber of subsets.

Since congruence modulo m is an equivalence relation on Z , this relation partitions Z into a collection of disjoint subsets , called " residue classes " or " Congruence classes "

Results :

* Let m be a positive integer and S = { 0,1,2,...,m-1 } . Then no two integers of S are congruent modulo m.

* Let m be a positive integer and S = { 0,1,2,...,m-1 } . Then every integer x is congruent modulo m to one of the integer of S.

Definition :

The remainder r , upon division of x by m , is called the residue of x mod m.The set of integers Z_m= { 0,1,2,...,m-1 } is called the set of least positive residues modulo m .

For example : { 0,1,2,3,4,5,6} is the set of least positive residues modulo 7. These integers are such that x 𝛜 Z is congruent mod 7 to exactly one of them.

If m is positive integer , then there exist exactly m equivalence classes for the equivalence relation " Congruence modulo m " . The equivalence class [r] is the set { x 𝛜 Z / x ≡ r (mod m) } .

It is also called r- residue class or r- congruence class.

Linear Congruences :

Definition 1:

If f(x) = a₀xⁿ + a₁x^n-1+…+a_n-1x + a_n is a polynomial with integral coefficients and a₀ ≢ 0 (mod m) then f(x) ≡ 0 (mod m) is called a polynomial congruence of n^th degree.

A polynomial congruence of first degree is called a linear congruence.

Definition 2 :

If there exist x₀ 𝛜 Z such that f(x₀) ≡ 0 (mod m) then x₀ 𝛜 Z is called a solution of f(x) ≡ 0 (mod m).

Any linear congruence can be put in the form ax ≡ b (mod m) where a ≢ 0 (mod m)

Note :

* t is a solution of the congruence ax ≡ b (mod m) ⇔ at ≡ b (mod m).

* If t is a solution of ax ≡ b (mod m) and s ≡ t (mod m) then s is also a solution of ax ≡ b (mod m)

* When we say that x ≡ t (mod m) is a solution of ax ≡ b (mod m) we mean that x = t + rm, for some integer r is a complete solution (a set of congruent solutions) of ax ≡ b (mod m).

Definition :

Let { x₀,x₁,x₂,…,x_m-1 } be a complete set of residue modulo m. The number of solutions of ax ≡ b (mod m) is the number x_i ( i = 0,1,2,…,m-1) such that ax_i ≡ b (mod m) .

Note :

* The number of solutions is independent of the choice of the complete set of residues modulo m.

* The number of solutions can not exceed the modulus m.

* If (m,n) 1, then the linear congruence ax ≡ b (mod m) has a unique solution.

* If ( a,m) = d and d/b then the congruence ax ≡ b (mod m) has no solution.

Inverse Modulo m:

If ab ≡ 1 (mod m) then a,b, are said to be inverses modulo m. Also 'b' is called inverse of 'a' and 'a' is called inverse of 'b' under modulo m.

Note :

An integer 'a ' has an inverse modulo m if and only if (a,m) = 1.

* Dirichlet Multiplication

* Euclidean Algorithm

* Fundamental Theorem of Arithmetic

* Properties of Numbers

* Historical Introduction to Number Theory

* GCD of morethan 2 numbers

* The Mobius Function 𝝻 ( n ) .

* The Euler Totient Function

* Formal Power Series

* Liouville’s function λ(n)