✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-072

Congruence Relations and Their Properties

A congruence relation describes when two integers have the same remainder after division by a positive integer. It provides the mathematical foundation for modular arithmetic.

a ≡ b (mod n) ⇔ n | (a − b)

Explanation

Let a, b, and n be integers with n > 0. The integers a and b are said to be congruent modulo n if n divides their difference. This is written as a ≡ b (mod n). For example, 23 ≡ 5 (mod 9) because 23 − 5 = 18, which is divisible by 9. Congruence modulo n is an equivalence relation because it satisfies reflexivity, symmetry, and transitivity. It also behaves consistently with addition, subtraction, and multiplication. If a ≡ b (mod n) and c ≡ d (mod n), then corresponding sums, differences, and products remain congruent modulo n. These properties allow complicated integer expressions to be simplified by replacing numbers with convenient congruent residues.

Variables

A

The first integer.

B

The second integer.

N

The positive modulus.

N | (a − b)

The statement that n divides the difference a − b.

Example or application

Problem

Determine whether 41 is congruent to 11 modulo 10.

Solution

Calculate the difference: 41 − 11 = 30. Since 30 is divisible by 10, the congruence holds.

Answer

41 ≡ 11 (mod 10)

Text

Congruence modulo n groups integers into equivalence classes according to their remainders. For a fixed positive integer n, there are exactly n distinct residue classes, represented by 0, 1, ..., n − 1.

Key Points

  • Congruence modulo n means that the difference between two integers is divisible by n.

  • Every integer is congruent to itself modulo n.

  • If a ≡ b (mod n), then b ≡ a (mod n).

  • If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

  • Congruences are preserved under addition, subtraction, and multiplication.

  • An integer can be replaced by any congruent integer when performing valid modular calculations.

Applications

  • Simplifying large integer calculations.

  • Proving divisibility properties.

  • Solving modular equations.

  • Developing cryptographic systems.

  • Studying periodic sequences and residue classes.

Learning Outcomes

  • Define congruence modulo n.

  • Test whether two integers are congruent modulo a given modulus.

  • Explain the equivalence-relation properties of congruence.

  • Apply congruence rules to simplify expressions.

Practice Questions

  • Determine whether 38 ≡ 8 (mod 6).

  • Prove that congruence modulo n is reflexive.

  • If a ≡ b (mod 7), what can be said about 3a and 3b modulo 7?

  • Find the smallest nonnegative residue of 57 modulo 8.

  • Explain the difference between equality and congruence.

Related Concepts

  • Equivalence Relations

  • Residue Classes

  • Modular Arithmetic

  • Division Algorithm

  • Modular Operations

Common Mistakes

  • Checking whether the two integers themselves are divisible by n instead of checking their difference.

  • Confusing congruence with equality.

  • Applying congruence rules without keeping the same modulus.

  • Assuming that division always preserves congruence.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory