Number Theory/Congruences

From Wikibooks, open books for an open world
Jump to: navigation, search

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 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.

Lemma[edit]

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)\,.

Fundamental Properties[edit]

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}

Congruence Equations[edit]

Residue Systems[edit]

Chinese Remainder Theorem[edit]

Polynomial Congruences[edit]