# Number Theory/Congruences

From Wikibooks, open books for an open world

## Contents

# Notation and introduction[edit]

We will call two integers *a* and *b* congruent modulo a positive integer *m*, if *a* and *b* have the same (smallest nonnegative) remainder when dividing by *m*. The formal definition is as follows.

## Definition[edit]

Let *a*, *b* and *m* be integers where . The numbers *a* and *b* are **congruent modulo m**, in symbols , if

*m*divides the difference .

### Lemma[edit]

We have if and only if *a* and *b* have the same smallest nonnegative remainder when dividing by *m*.

**Proof:**

Let . Then there exists an integer *c* such that . Let now be those integers with

and

.

It follows that

which yields or and hence .

Suppose now that . Then, , which shows that .

# Fundamental Properties[edit]

First, if and , we get , and .

As a result, if , then