## Congruence Classes and Modular Arithmetic

*Congruence classes* (or shorter *congruences*) are powerful mathematical tools, simplifying many calculations with integers. The arithmetic associated with congruences is called **modular arithmetic**. In this kind of arithmetic, we simplify calculations by replacing each integer with its remainder when divided by some fixed positive integer $n.$ The simplification effect of this is that the whole, infinite set of integers $\mathbb Z$ is replaced by a much smaller set $\mathbb Z_n$ which contains only a finite number $n$ of elements. We will see that we can add, subtract and multiply numbers in $\mathbb Z_n.$ Just as it is the case in $\mathbb Z$, there are some difficulties with the division. In this sense, $\mathbb Z_n$ inherits many properties of integers but, because it is finite, it is much easier to work with.

| | | | created: 2014-02-20 21:52:51 | modified: 2019-04-10 20:12:07 | by: *bookofproofs* | references: [1272], [8152]

## 1.**Definition**: Congruent, Residue

## 2.**Proposition**: Congruence Classes

## 3.**Proposition**: Congruences and Division with Quotient and Remainder

## 4.**Explanation**: Explanation of Congruence Classes

## 5.**Proposition**: Addition, Subtraction and Multiplication of Congruences

## 6.**Proposition**: Cancellation of Congruences With Factor Co-Prime To Module

## 7.**Proposition**: Cancellation of Congruences with General Factor

## 8.**Proposition**: Multiplication of Congruences with a Positive Factor

## 9.**Proposition**: Congruence Modulo a Divisor

## 10.Diophantine Equations and Complete and Reduced Residue Systems

[8152] **Jones G., Jones M.**: “Elementary Number Theory (Undergraduate Series)”, Springer, 1998

[1272] **Landau, Edmund**: “Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

© 2018 Powered by BooOfProofs, All rights reserved.