Skip to main content

What Is the Concept of Congruences in Number Theory?

I am a PhD student of mathematics. I have complete MS in math from the University of Pakistan and have been writing online since 2020.

what-is-the-concept-of-congruences-in-number-theory

Congruences in Number Theory

A congruence is simply a declaration of divisibility. One of history's greatest mathematicians, Carl Friedrich Gauss (1777–1855), developed the notion of congruences. Gauss made numerous notable contributions to the theory of numbers, including the fundamental concepts. Although number theory had been studied somewhat systematically earlier by Pierre de Fermat (1601–1665), Gauss was the first to develop the field as a branch of mathematics rather than just a distributed collection of interesting issues.

Gauss established the idea of congruences in his book Disquisitions Arithmetical, which was written at the age of 24 and quickly became recognized as a key instrument for the study of number theory. The theorems of Fermat and Euler are particularly important, which offer effective methods for examining the multiplicative properties of congruences. These two number theory founders approached their work in quite different ways.

Fermat, a lawyer by trade, enjoyed mathematics as a pastime. Through correspondence with other mathematicians, he shared his mathematical concepts while providing very little information about the justifications for his claims. (One of his statements is referred to as Fermat's "final theorem," despite the fact that it has never been proven and is, therefore, not a theorem at all.) On the other hand, Leonard Euler (1707–1783) covered nearly all of the known fields of mathematics throughout his lifetime.

Definition of Congruences

If the difference between a and b is divided by an integer m, other than zero, we say that a is congruent to b modulo m and write a ≡ b. (mod m).

Important Results of Congruences

a, b, c, d are integers.

Then:

  • a ≡ b (mod m), b =a (mod m), and a - b = 0 (mod m) are equivalent statements.
  • If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).
  • Ifa ≡ b (mod m) and c ≡ d (mod m), then a+ c ≡ b + d (mod m).
  • If a ≡b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m).
  • If a ≡ b (mod m) and d / m where d > 0, then a ≡ b (mod d).
  • If a ≡ b (mod m) then ac ≡ bc (mod mc) for c > 0.

Definition of Residue and Complete Residue

If x ≡ y (mod m), then y is called a residue of x modulo m. A set x 1, x2, ……xm is called a complete residue system modulo m if, for every integer y, there is one and only one xi such that y = xi (mod m).

Example

The set 1, 2….m - 1, m is an illustration of how there are essentially an endless number of complete residue systems modulo m.

A set of m integers forms a complete residue system modulo m if and only if no two integers in the set are congruent modulo m. The set of all numbers x satisfying x = a (mod m) is the arithmetic progression for fixed integers a and m > 0. ···, a - 3m, a - 2m, a - m, a, a + m, a + 2m, a+ 3m, · · ·. This set is called a residue class, or congruence class, modulo m. There are m distinct residue classes modulo m, obtained, for example, by taking successively a = 1, 2, 3, · · ·, m.

Important Results of Residue and Complete Residue

If b ≡ c (mod m), then (b, m) ≡ (c, m).

Definition of Reduced Residue

A reduced residue system modulo m is a set of integers ri, such that (ri, m) = 1, ri is not congruent to ri (mod m) if i ≠ j, and such that every x prime to m is congruent modulo m to some member ri of the set.

Important Note About Complete Residue

It is obvious that a complete residue system modulo m can be transformed into a reduced residue system modulo m by removing the members that are not comparatively prime to m. additionally, the number of members in all reduced residue systems modulo m, represented by the symbol φ (m). It is sometimes referred to as the totient and is known as Euler's φ-function.

Important Results About Complete Residue

  • The number φ (m) is the number of positive integers less than or equal to m that are relatively prime to m.
  • Let (a, m) = 1. Let r1, r2…..rn be a complete, or a reduced, residue system modulo m. Then ar1, ar2 ……arn is a complete, or a reduced, residue system, respectively, modulo m.

Fermat's Theorem

Let p denote a prime. If p is not divide a then ap-1 = l (mod p). For every integer a, ap ≡ a (mod p).

Euler's Generalization of Fermat's Theorem

If (a, m) = 1, then a^ φ -1 ≡1 (mod m).

  • If (a, m) = 1 then there is an x such that ax= 1 (mod m). Any two such x are congruent (mod m). If (a, m) > 1 then there is no such x.
  • Let p be a prime number. Then x2 ≡ 1 (mod p) if and only if x ≡ ± l (mod p).
  • Let p denote a prime. Then x2 ≡ 1 (mod p) has solutions if and only if

p = 2 or p ≡ 1 (mod 4).

  • Let q be a prime factor of a2+ b2. If q ≡ 3 (mod 4) then q / a and q / b.