Congruences

Congruence

Let $n$ be a positive integer, and let $a$ and $b$ be any integers. We say that $a$ is congruent to $b \pmod {n}$, or $a$ is a residue of $b \pmod{ n}$, written

$$a \equiv b   \pmod {n}$$

If $a$ and $b$ leave the same remainder when divided by $n$.To be more precise, we use the division algorithm to put $a=qn+r$ with $0 \le r \lt n$, and $b=q'n+r'$ with  $0 \le r' \lt n$, and then we say that $a \equiv b \pmod {n}$  if and only if $r=r'$

Example:both 28 and 48 leave the same reminder when divided by 5. ie $48 \equiv 28 \pmod{5}$

We will use the notation $a \not \equiv b \pmod {n}$ to denote that $a$ and $b$ are not congruent $\pmod{n}$,that is, they leave different remainders when divided by $n$.

Example: 

$100\equiv 2 \pmod{7}$

$20 \not \equiv 3 \pmod{5}$ 

 

Theorem: $a \equiv b \pmod{m}$ if and only if $a=b+km$ for some integer $k$.

Proof:suppose $a \equiv b \pmod{m}$, then $m |(a-b)$, so $a-b=km$ for some integer $k$, tht is $a= b+km$.

Example:$23 \equiv 3 \pmod{5}$ and $23=3+4.5$

Note:If $a \equiv 0 \pmod{m}$ if and only if $m|a$, Eg: $28 \equiv 0 \pmod{4}$

 

Lemma:For any fixed $n \ge 1$ , we have $a \equiv b \pmod {n}$, if and only if $n|a-b$

Proof:Putting $a=qn+r$ and $b=q'n+r'$ as above, we have $a-b=(q-q')n+(r-r')$ with $-n<r-r'<n$.If $a \equiv b \pmod {n}$, then $r=r'$,so $r-r'=0$ and $a-b=(q-q')n$, which is divisible by$n$.Conversely if $n$ divides $a-b$, then it divides $a-b-(q-q')n=r-r'$; now the only integer strictly between $-n$ and $n$ which is divisible by $n$ is 0.So $r-r'=0$ giving $r=r'$  and hence $a \equiv b \pmod {n}$.

Example:

since $5|(23-3)$ ,we can say $23 \equiv 3 \pmod{5}$.

Lemma:

For any fixed $n \ge 1$, we have

1)$a \equiv a$ for all integers $a$  ; reflexivity

2)If $a \equiv b$  then $b \equiv a$   ;symmetry

3)If $a \equiv b$ and $b \equiv c$ then $a \equiv c$ ; transitivity

proof: 

• since $m|(a-a), a \equiv a \pmod{m}$ 
• suppose $a \equiv b \pmod{m}$. Then $m|(a-b)$ ie; $m|-(b-a)$. So $m|(b-a)$, that is $b \equiv a \pmod{m}$
• suppose $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$. Then $m|(a-b)$ and $m|(b-c)$, so $m|[(a-b)+(b-c)]$ ie; $m|(a-c)$, consequently  $a \equiv c \pmod{m}$
  

When these three properties are the properties for equivalence relation.So these lemma proves that for each fixed $n$, congruence mod $n$ is an equivalence relation on $\mathbb{Z}$.It follows that $\mathbb{Z}$ is partitioned into disjoint equivalence classes, these are the congruence classes.

Example:$since$7 \equiv -5 \pmod{4}$and$-5 \equiv 15 \pmod{4}$,$7 \equiv 15 \pmod{4}$.

When $n=1$ all integers are congruent to each other, so there is a single congruent class, coinciding with $\mathbb{Z}$.When $n=2$, the two classes $[0]=[0]_2$ and $[1]=[1]_2$ consist of even and odd integers respectively.

For a given $n \ge 1$, we denote the set of $n$ equivalence class$\pmod{n}$ by $\mathbb{Z}_n$.We can do arithmetic with these congruence classes, so that $\mathbb{Z}_n$ become a number system with properties very similar to that of $\mathbb{Z}$.If $[a]$ and $[b]$ are elements of $\mathbb{Z}_n$ ie; congruent classes mod $n$.We define the sum, difference and product to be the classes.

$$[a]+[b]=[a+b]$$

$$[a]-[b]=[a-b]$$

$$[a][b]=[ab]$$

containing the integers $a+b$,$a-b$ and $ab$ respectively.

If we try to define exponentiation of classes in $\mathbb{Z}_n$ such that

$$[a]^{[b]}=[a^b]$$

restricting $b$ to non-negative values to ensure that $a^b$ is an integer.If we take $n=3$, for instance this gives

$$[2]^{[1]}=[2^1]=[2]$$

unfortunately $[1]=[4]$ in $\mathbb{Z}_3$, and our definition is also gives

$$[2]^{[4]}=[2^4]=[16]=[1] \ne [2]$$

So exponentiation of congruence class is not well defined.We therefore confine arithmetic in $\mathbb{Z}_n$ to operations which are well defined, like addition,subtraction,multiplication and powers.A restricted form of division can also be defined.

A set of $n$ integers, containing one representative from each of the $n$ congruent class in $\mathbb{Z}_n$,is called complete set of residues $\mod n$.A sensible choice of such a set can ease calculations considerably.One obvious choice is provided by the division algorithm. We can divide an integer $a$ by $n$  to give $a=qn+r$ for some unique $r$ satisfying $0 \le r \lt n$; thus each class $[a] \in \mathbb{Z}$ contains a uniqe $r=0,1,\ldots,n-1$, so these $n$ integers form a complete set of residues, called the least non-negative residues mod $n$. The remainder $r$ satisfying $-n/2 \lt r \le n/2$.These reminders are the least absolute residues $\mod n$, those with least absolute value; when $n$ is odd they are $0,\pm 1,\pm 2,\ldots,\pm (n-1)/2$ and when $n$ is even they are $0,\pm 1,\pm 2,\dots,\pm (n-2)/2,\pm n/2$

Example:

Lets calculate the least non-negative residue of  $28 \times 33 \pmod {35}$ 

We have $28 \equiv -7 (\mod 35)$ and $33 \equiv -2 \pmod {35}$

So $28 \times 33=-7 \times -2=14 \pmod {35}$

Example:

Lets calculate the least absolute residue of $15 \times 59 \pmod{75}$. We have 

$15 \times 59=15 \times 16=-15 \times 4 \times 4=-60 \times 4=15 \times 4=60 =-15 \pmod{75}$ 

Example:

Lets calculate the least non negative residue of $3^8  \pmod {13}$

$3^2=9=-4 \pmod{13}$

$3^4=(3^2)^2=(-4)^2=16=3 \pmod{13}$

$3^8=(3^4)^2=3^2=9 \pmod{13}$

Since $n$ divides $m$  if and only if $m \equiv 0 \pmod {n}$, it follows that problem about divisibility is equivalent to problems about congruences and these can be sometimes easier to solve.

Example:

Lets prove $a(a+1)(2a+1)$ is divisible by 6 for every integer $a$.By taking least absolute residues mod 6, we can see that $a \equiv 0,\pm 1,\pm 2$ and $3$.

if $a=0$ then $a(a+1)(2a+1)\equiv 0.1.1\equiv 0$

if $a=1$ then $a(a+1)(2a+1)\equiv 1.2.3\equiv 0$

We can show this for other values also hence

$6|a(a+1)(2a+1)$ for all $a$

 

Theorem: let $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$. Then $a+c \equiv b+d \pmod{m}$ and $ac \equiv bd \pmod{m}$

Example:We have $17 \equiv -4 \pmod{3}$ and $28 \equiv 7 \pmod{3}$.So by the theorem $17+28 \equiv -4 + 7 \pmod{3}$ie; $45 \equiv 3 \pmod{3}$.Also $17.28 \equiv (-4).7 \pmod{3}$ ie; $476 \equiv -28 \pmod{3}$

Corollary:If $a \equiv b \pmod{m}$ and $c$ is any integer, then

$a+c \equiv b+c \pmod{m}$

$a-c \equiv b-c \pmod{m}$

$ac \equiv bc \pmod{m}$

$a^2 \equiv b^2  \pmod{m}$

Example: Notice that $19 \equiv 5 \pmod{7}$.So $19+11 \equiv 5+11 \pmod{7}$,$19-11 \equiv 5 -11 \pmod{7}$, and $19.11 \equiv 5.11 \pmod{7}$.

Theorem:If $a \equiv b \pmod{m}$, then $a^n \equiv b^n \pmod{m}$ for any positive integer $n$.

This theorem helps in solving the congruence

Example:Find the remainder when $16^{53}$ is divisible by 7.

It is noted that $16 \equiv 2 \pmod{7}$.So by the theorem $16^{53} \equiv 2^{53} \pmod{7}$.

$2^3=8 \equiv 1 \pmod{7}$. So

$2^{53}=2^{3.17+2}=(2^3)^{17}.2^2$

$\equiv 1^{17}.4 \pmod{7}$

$\equiv 4 \pmod{7}$

Theorem:

Let $n$ have prime power factorisation

$$n=p_1^{e_1}.p_2^{e_2}.\ldots.p_k^{e^k}$$

where $p_1,p_2,\ldots,p_k$ are distinct primes.Then for any integers $a$ and $b$ we have

$a \equiv b  \pmod{n}$ if and only if $a \equiv b \pmod {p_i^{e_i}}$ for each $i=1\ldots k$.

Example: $8 \equiv 23 \pmod{15}$

implies that

$8 \equiv 23 \pmod{5}$

$8 \equiv 23 \pmod{3}$

Lemma

let $f(x)$ be a polynomial with integer coefficients and let $n \ge 1$. If $a \equiv b \pmod{n}$. Then $f(a) \equiv f(b)  \pmod{n}$

Lets consider the polynomial $f(x)=x.(x+1).(2x+1)=2x^3+3x^2+x$ and $n=6$. Use the fact that $a \equiv 0,\pm 1,\pm 2 \: \text{or} \: 3$, then $f(a) \equiv f(0),f(\pm 1),f(\pm 2) \: \text{or} \: f(3)$ respectively, all of which are easily seen to be congruent to 0 mod 6.

Suppose that a polynomial $f(x)$ , with integer coefficients , has an integer root $x=a \in \mathbb{Z}$,so that  $f(a)=0$.It follows then that $f(a) \equiv 0 \pmod{n}$ for all integers $n \ge 1$. We can often use the contra-positive of this to show that certain polynomials $f(x)$ has no integer roots; if there exist an integer $n \ge 1$ , such that the congruence $f(x) \equiv 0 \pmod{n}$ has no solutions $x$, then the equation $f(x)=0$ can have no solutions $x$.If $n$ is small, we can check whether $f(x) \equiv 0 \pmod{n}$ has any solutions simply by evaluating $f(x_1),\ldots f(x_n)$, where $x_1,x_2,\ldots, x_n$ for a complete set of residues $\pmod{n}$ ; each $x \in \mathbb{Z}$ is congruent to some $x_i$. This implies that $f(x) \equiv f(x_i)$, and we simply determine whether any of $f(x_1),\ldots,f(x_n)$ is divisible by $n$.

Example:

Lets prove that the polynomial $f(x)=x^5-x^2+x-3$ has no integer roots.To do this lets take $n=4$ and consider the congruence

$f(x)=x^5-x^2+x-3 \equiv 0 \pmod{4}$

Using the least absolute residues $0,\pm 1,2$ , as a complete set of residues(mod 4) we find that

$f(0)=-3\quad f(1)=-2 \quad f(-1)=-6 \quad \text{and} \; f(2)=27$