Number Theory/Congruences

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Contents

[edit] Notation and introduction

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.

[edit] Definition

Let a, b and m be integers where m > 0. The numbers a and b are congruent modulo m, in symbols a \equiv b \pmod{m}, if m divides the difference a − b.

[edit] Lemma

We have a \equiv b \pmod{m} if and only if a and b have the same smallest nonnegative remainder when dividing by m.

Proof:

Let a \equiv b \pmod{m}. Then there exists an integer c such that cm = a-b\,. Let now q,q',r,r'\, be those integers with

a=qm+r,\quad 0\leq r<m

and

b=q'm+r',\quad 0\leq r'<m.

It follows that

cm = a-b = m(q-q') + (r-r')\,

which yields m|(r-r')\, or m\ \mbox{divides} \ (r-r')\, and hence r=r'\,.

Suppose now that r=r'\,. Then, a-b = m(q-q')\,, which shows that m|(a-b)\,.

[edit] Fundamental Properties

First, if a\equiv b \pmod{m} and c\equiv d \pmod{m}, we get ac\equiv bd \pmod{m}, and a+c\equiv b+d \pmod{m}.

As a result, if a\equiv b \pmod{m}, then a^p\equiv b^p \pmod{m}

[edit] Congruence Equations

[edit] Residue Systems

[edit] Chinese Remainder Theorem

[edit] Polynomial Congruences

Retrieved from "http://en.wikibooks.org/wiki/Number_Theory/Congruences"