Blog Logo
Research Scientist @ Foundation AI
·
read
Image Source: http://wallpaperswide.com/old_clock-wallpapers.html
· · ·

What is Mathematics Series

Index

· · ·

Congruence

Two integers \(a\) and \(b\) are congruent modulo \(d\), where \(d\) is a fixed integer, if \(a\) and \(b\) leave same remainder on division by \(d\), i.e.

It is denoted by,

Following defination of congruences are equivalent:

  • \(a\) is congruent to \(b\) modulo \(d\).
  • \(a = b + nd\) for some integer n.
  • \(d\) divides \(a-b\).

Properties and Proof

Congruence with respect to a fixed modulus has many of the formal properties of ordinary equality.

  • \(a\equiv a\pmod d\)
  • If \(a\equiv b\pmod d\), then \(b\equiv a\pmod d\)
  • If \(a\equiv b\pmod d\) and \(b\equiv c\pmod d\), then \(a\equiv c\pmod d\)

If \(a\equiv a’\pmod d\) and \(b\equiv b’\pmod d\), then

Say,

then,

Geometric Interpretation

Generally, integers are represented geometrically using a number line, where a segment of unit length is chosen and multiplied in either directions to represent negative or positive integers.

Geometric Representation of Congruence

But, when an integer modulo \(d\) is considered, the magnitude is insignificant as long as the behavior on division by \(d\) is same (i.e. they leave the same remainder on division by \(d\)). This is geometrically represented using a circle divided into d equal parts. This is because any integer divided by \(d\) leaves as remainder one of the \(d\) numbers \(0, 1, \cdots, d-1\) which are placed at equal distances on the circumference of the circle. Every integer is congruent modulo \(d\) to one of these numbers and hence can be represented by one of these points. (Two numbers are congruent if they occur at the same point the circle.)

Application of Congruence Properties

The test for divisibility, generally taught in elementary school, is a direct result of the properties of congruence operation.

For example,

since \(10 = -1 + 11\). Successively multiplying this congruence, using \eqref{5}, we obtain,

So using \eqref{3} and \eqref{5}, it can be shown that any two number, z and t of the form shown below will leave the same remainder when divided by 11.

Here, \(z\) is the format of any integer to the base 10. Hence, a number is divisible by 11 (i.e. leaves a remainder 0), if and only if \(t\) is divisible by 11 (which in \eqref{7} basically means that the difference of the sum of all the odd digits and even digits together should be divisible by 11, including 0.)

It can be observed that while such patterns are easier for numbers like 3, 9, 11, they are not easy to remember for other numbers like 7 and 11, as shown below.

From above we reach the result that any number \(z\) in \eqref{6} is divisible by 13 if and only if \(t\) of the form \eqref{8} is divisible by 13 (clearly not an easy one to remember :P).

Using a similar approach one can deduce the divisibility rule for any other integer.

Other Properties

only if either \(a\equiv 0 \pmod d\) or \(b\equiv 0 \pmod d\). Property only holds if \(d\) is a prime number. If \(d\) was a composite, there exist numbers \(a \lt d\) and \(b \lt d\), such that,

Where,

But,

  • Law of Cancellation: With respect to a prime modulus, if \(ab \equiv ac\) and \(a \cancel{\equiv} 0\), then \(b \equiv c\).

Fermat’s Theorem

If \(p\) is any prime which does not divide the integer \(a\), then

Consider multiples of \(a\),

Let two of these numbers, \(m_r\) and \(m_s\) be congruent modulo \(p\), then,

\(p\) must be a factor of \(m_r - m_s = (r-s)a\) for some \(r, s\) such that \(1 \leq r \lt s \leq (p-1)\).

But since it is assumed that \(p\) does not divide \(a\) and also \(p\) cannot be factor of \(r-s\) since it is less than \(p\).

From \eqref{9}, it can be concluded that two numbers from \eqref{11} cannot be congruent modulo \(p\).

So each of the numbers in \eqref{11} must be congruent to \(1, 2, 3, \cdots , (p-1)\) in some arrangement. So,

For simplicity, let \(K = 1 \cdot 2 \cdots (p-1)\), then

where \(K\) is not divisible by \(p\), since none of its factors are, hence from \eqref{9}, \((a^{p-1} - 1)\) must be divisible by \(p\), i.e.

Hence, proving \eqref{10}.

REFERENCES:

What is Mathematics? Second Edition - Chapter I: Natural Numbers

· · ·