What Is Congruence Modulo N?

সংখ্যাতত্ত্বের অত্যন্ত গুরুত্বপূর্ণ একটি শাখা হলো Modular Arithmatic. বিখ্যাত জার্মান গণিতবিদ কার্ল ফ্রেডরিক গাউস (Carl Friedrich Gauss) এর হাতে এর ব্যুৎপত্তি। পরবর্তীতে ফার্মা (Pierre De Fermat),অয়লার (Leonhard Euler) সহ বিভিন্ন গণিতবিদের হাতে এর উৎকর্ষ সাধন হয়।

ধর, $a,b,m$ পূর্ণসংখ্যা এবং $m \neq 0$. এখন $a-b$ যদি $m$ দ্বারা নিঃশেষে বিভাজ্য হয় তাহলে আমরা লিখি $a \equiv b$ $\text{(mod m)}$ এবং একে পড়া হয়: $a$ and $b$ are congruent modulo $m$.

আর $a-b$ যদি $m$ দ্বারা নিঃশেষে বিভাজ্য না হয় তাহলে আমরা লিখি $a \not\equiv b$ $\text{(mod m)}$ এবং একে পড়া হয়: $a$ and $b$ are not congruent modulo $m$.

যেমন: $10 \equiv 2$ $\text{(mod 8)}$ কিন্তু $13 \not\equiv 2$ $\text{(mod 10)}$.

এখন,যদি $m$, $(a-b)$ কে নিঃশেষে ভাগ করে, তাহলে আমরা বলতে পারি, $a$ কে $m$ দ্বারা ভাগ করলে $b$ ভাগশেষ থাকে। যেমন: $7$ দ্বারা $(17-3)$ নিঃশেষে বিভাজ্য । আবার, $17$ কে $7$ দ্বারা ভাগ করলে $3$ ভাগশেষ থাকে.

"$\equiv$" দ্বারা চিহ্নিত এই সম্পর্ককে বলা হয় ‘কনগ্রুয়েন্স রিলেশন’ (Congruence Relation)। সংখ্যাতত্ত্বের যে শাখায় এই সম্পর্ক নিয়ে আলোচনা করা হয় তাকেই বলা হয় Modular Arithmatic.

একটা কনগ্রুয়েন্স কে আমরা অনেকভাবেই লিখতে পারি, যেমন: $25 \equiv 1$ $\text{(mod 8)}$, $25 \equiv 9$ $\text{(mod 8)}$, $25 \equiv -7$ $\text{(mod 8)}$.

এখানে প্রত্যেকক্ষেত্রেই $(a-b)$, $m$ দ্বারা নিঃশেষে বিভাজ্য।

অর্থাৎ আমরা বলতে পারি, $a \equiv b$ $\text{(mod m)}$ হলে, $a \equiv b+mk$ $\text{(mod m)}$ যেখানে $k$ যেকোনো পূর্ণসংখ্যা।

এবার আমরা কনগ্রুয়েন্সের কয়েকটি বৈশিষ্ট্য(Proposition) নিয়ে আলোচনা করব।

(i) $a \equiv a$ $\text{(mod m)}$

(ii) $a \equiv b$ $\text{(mod m)}$ হলে, $b \equiv a$ $\text{(mod m)}$ হবে।

(iii) যদি $a \equiv b$ $\text{(mod m)}$ হয় এবং $b \equiv c$ $\text{(mod m)}$ হয়, তাহলে $a \equiv c$ $\text{(mod m)}$ হবে।

(iv) $a \equiv b$ $\text{(mod m)}$ এবং $c \equiv d$ $\text{(mod m)}$ হলে, $a+c \equiv b+d$ $\text{(mod m)}$ এবং $a-c \equiv b-d$ $\text{(mod m)}$ হবে।

(v) ধর, $a \equiv c$ $\text{(mod m)}$ এবং $b \equiv d$ $\text{(mod m)}$। তাহলে $a \equiv b$ $\text{(mod m)}$ হবে যদি এবং কেবল যদি $c \equiv d$ $\text{(mod m)}$ হয়।

(vi) যদি $a \equiv b$ $(\mod m)$ হয়,তাহলে যেকোনো পূর্ণসংখ্যা $k$ এর জন্য $ak \equiv bk$ $\text{(mod m)}$ হবে।

(vii) যদি $a_{1} \equiv b_{1}$ $\text{(mod m)}$, $a_{2} \equiv b_{2}$ $\text{(mod m)}$,..........., $a_{k} \equiv b_{k}$ $\text{(mod m)}$ হয়,তাহলে $a_{1} \times a_{2} \times .....\times a_{k} \equiv b_{1} \times b_{2} \times……\times b_{k}$ $\text{(mod m)}$ হবে।

এখান থেকে বলা যায়, $a \equiv b$ $(\mod m)$ হলে,যেকোনো পূর্ণসংখ্যা $k$ এর জন্য $a^{k} \equiv b^{k}$ $\text{(mod m)}$ হবে।

(viii) $a \equiv b$ $(\mod m_{i})$ (যেখানে $i=1,2,3,…..,k$) হবে যদি এবং কেবল যদি $a\equiv b (\mod lcm(m_1,m_2,\ldots m_k))$ হয়।

এখন যদি $m_{1},m_{2},......m_{k}$ এদের সকল জোড়া $(m_{i},m_{j})$ এর গ.সা.গু $1$ হয়,(যেখানে, $1 \leq i < j \leq n$) তাহলে $lcm(m_{1},m_{2},......m_{k})=m_{1} \times m_{2} \times......\times m_{k}$. অর্থাৎ সেক্ষেত্রে $a\equiv b\mod m_i)$ (যেখানে $i=1,2,3,…..,k$) হবে যদি এবং কেবল যদি $a \equiv b (\mod m_1m_2......m_k)$ হয়।

*$lcm(m_{1},m_{2},......m_{k})$ অর্থ $m_{1},m_{2},......m_{k}$ সংখ্যাগুলোর ল.সা.গু।

এগুলোর প্রমাণ খুবই সহজ। সাধারণ বিভাজ্যতার সূত্র দিয়েই করা যায়। নিজে নিজে করার চেষ্টা কর। আর বৈশিষ্ট্যগুলো অনুভব করার চেষ্টা কর।

বৈশিষ্ট্যগুলোর প্রমাণ :

(i) $a-a=0$ সকল সংখ্যা দ্বারাই বিভাজ্য।

(ii) $m$ যদি $a-b$ কে নিঃশেষে ভাগ করে, তাহলে $-1 \times (a-b)=b-a$ কেও নিঃশেষে ভাগ করবে।

(iii) $m$ যদি $a-b$ এবং $b-c$ উভয়কে নিঃশেষে ভাগ করে, তাহলে এদের যোগফল $(a-b)+(b-c)=a-c$ কেও নিঃশেষে ভাগ করবে।

(iv) $m$, $a-b$ কে নিঃশেষে ভাগ করে। এখন, $a-b$ কে আমরা $a-b+c-c=a+c-b-c=(a+b)-(b-c)$ আকারে লিখতে পারি।তাহলে $a+c \equiv b+c$ $\text{(mod m)}$.একইভাবে, $b+c \equiv b+d$ $\text{(mod m)}$.

তাহলে (ii) থেকে বলতে পারি, $a+c \equiv b+c \equiv b+d$ $\text{(mod m)}$.

একইভাবে প্রমাণ করতে পারবে যে, $a-c \equiv b-d$ $\text{(mod m)}$.

(v) (iv) থেকে আমরা জানি, $a-b \equiv c-d$ $\text{(mod m)}$.সুতরাং, $a \equiv b$ $\text{(mod m)}$ অর্থাৎ $a-b \equiv 0$ $\text{(mod m)}$ হবে যদি এবং কেবল যদি $c \equiv d$ $\text{(mod m)}$ হয়।

(vi) $m$ যদি $a-b$ কে নিঃশেষে ভাগ করে, তাহলে যেকোনো পূর্ণসংখ্যা $k$ এর জন্য $k(a-b)=ka-kb$ কেও নিঃশেষে ভাগ করবে।

(vii) $a_{1} \equiv b_{1}$ $\text{(mod m)}$, (v) থেকে লিখতে পারি, $a_{1} \times a_{2} \equiv b_{1} \times a_{2}$ $\text{(mod m)}$.

আবার যেহেতু, $a_{2} \equiv b_{2}$ $\text{(mod m)}$, সুতরাং $a_{2} \times b_{1} \equiv b_{2} \times b_{1}$ $\text{(mod m)}$. অর্থাৎ,

$a_{1} \times a_{2} \equiv b_{1} \times a_{2} \equiv b_{1} \times b_{2}$ $\text{(mod m)}$.

একইভাবে যেকোনো $k$ এর জন্যই প্রমাণ করা যায় যে,

$a_{1} \times a_{2} \times .....\times a_{k} \equiv b_{1} \times b_{2} \times……\times b_{k}$ $\text{(mod m)}$.

এখন যদি $a_{1}=a_{2}=………….=a_{k}$ এবং $b_{1}=b_{2}=………=b_{k}$ হয়, তাহলে

$a_{1} \times a_{2} \times .....\times a_{k}=(a_{1})^{k} \equiv b_{1} \times b_{2} \times……\times b_{k}=(b_{1})^{k}$ $\text{(mod m)}$.

(viii) $a\equiv b(\mod m_i)$ যেখানে $i=1,2,………,k$.

অর্থাৎ $(a-b)$, $m_{1},m_{2},……..,m_{k}$ দ্বারা নিঃশেষে বিভাজ্য। সুতরাং, $(a-b)$ এদের একটি সাধারণ গুণিতক। তাই এদের ল.সা.গু দ্বারাও $(a-b)$ নিঃশেষে বিভাজ্য।

আবার $(a-b)$ যদি $m_{1},m_{2},………,m_{k}$ এর ল.সা.গু দ্বারা নিঃশেষে বিভাজ্য হয়, তাহলে অবশ্যই এদের প্রত্যেকটি দ্বারা আলাদাভাবে নিঃশেষে বিভাজ্য হবে।

উপরে আমরা দেখলাম যে সাধারণ সমীকরণের মতো কনগ্রুয়েন্সেও আমরা উভয় পাশে একই সংখ্যা যোগ,বিয়োগ,গুণ করতে পারি।এখন কথা হচ্ছে ভাগের ক্ষেত্রে কি হবে?

কনগ্রুয়েন্সে আমরা হুটহাট ভাগ দিতে পারি না। যেমন: $21 \equiv 14$ $\text{(mod 7)}$. এখন উভয়পক্ষকে $7$ দ্বারা ভাগ দিয়ে পাই, $3 \equiv 2$ $\text{(mod 7)}$ যা সঠিক নয়। আবার, $20 \equiv 6$ $\text{(mod 7)}$ এর উভয়পক্ষকে $2$ দ্বারা ভাগ দিয়ে পাই, $10 \equiv 3$ $\text{(mod 7)}$, যা সত্য।

দুইবার দুইরকম কেন হল চিন্তা কর।

আসলে, (ix) $ac \equiv bc(\mod m)$ হলে,আমরা বলতে পারি, $a \equiv b(\mod \dfrac {m} {gcd(c,m)})$.

*$\text{gcd(x,y)}$ দ্বারা $x,y$ এর গ.সা.গু বোঝানো হয়।

এবার কনগ্রুয়েন্সের একটা অত্যন্ত গুরুত্বপূর্ণ থিওরেম শিখব।

ধর,$m$ একটি ধনাত্মক পূর্ণসংখ্যা। $a,b$ $m$ এর সাথে সহমৌলিক দুটি পূর্ণসংখ্যা। যদি $x,y$ দুটি পূর্ণসংখ্যা হয় যেন $a^{x} \equiv b^{x}$ $\text{(mod m)}$ এবং $a^{y} \equiv b^{y}$ $\text{(mod m)}$, তাহলে

$a^{gcd(x,y)} \equiv b^{gcd(x,y)}$ $\text{(mod m)}$ হবে।

প্রমাণ: Bezout’s Identity থেকে আমরা জানি যে, $\text{gcd}$$(x,y)=ux-vy$ যেখানে $u,v$ অঋণাত্মক পূর্ণসংখ্যা।

(vii) থেকে বলতে পারি, $(a^{x})^{u} = a^{ux} \equiv (b^{x})^{u} = b^{ux}$ $\text{(mod m)}$.

একইভাবে, $(a^{y})^{v} = a^{vy} \equiv (b^{y})^{v} = b^{vy}$ $\text{(mod m)}$

বা $b^{vy} \equiv a^{vy}$ $\text{(mod m)}$((iii) থেকে)

এখন (vii) প্রয়োগ করে বলতে পারি,

$a^{ux}b^{vy} \equiv a^{vy}b^{ux}$ $\text{(mod m)}$.

এখন যেহেতু $a,b$ এর সাথে $m$ সহমৌলিক,সুতরাং $a^{vy}b^{vy}$ এর সাথেও সহমৌলিক। (ix) ব্যবহার করে উভয়পক্ষকে $a^{vy}b^{vy}$ দ্বারা ভাগ দিয়ে পাই, $a^{gcd(x,y)} = a^{ux-vy} \equiv b^{ux-vy} = b^{gcd(x,y)}$ $\text{(mod m)}$

এবার কিছু সমস্যা সমাধান করা যাক।

সমস্যা ১: প্রমাণ কর যে,কোনো সংখ্যার অঙ্কগুলোর যোগফল $3$ দিয়ে নিঃশেষে বিভাজ্য হলে মূল সংখ্যাটিও $3$ দ্বারা নিঃশেষে বিভাজ্য হবে।

সমাধান: কোনো সংখ্যা $n$ কে আমরা লিখতে পারি,

$n =10^{x}a_{x}+10^{x-1}a_{x-1}+........+10a_{1}+a_{0}$.

$10 \equiv 1$ $\text{(mod 3)}$ $\Rightarrow$ $10^{i} \equiv 1^{i}=1$ $\text{(mod 3)}$ $\Rightarrow$ $10^{i}a \equiv 1 \times a=a$ $\text{(mod 3)}$.

তাহলে , $10^{x}a_{x}+10^{x-1}a_{x-1}+........+10a_{1}+a_{0} \equiv a_{x}+a_{x-1}+………+a_{1}+a_{0}$.

এখান থেকে আমরা বলতে পারি, $n$ অর্থাৎ $10^{x}a_{x}+10^{x-1}a_{x-1}+........+10a_{1}+a_{0}$, $3$ দ্বারা নিঃশেষে বিভাজ্য হবে যদি এবং কেবল যদি $n$ এর অঙ্কগুলোর যোগফল অর্থাৎ $a_{x}+a_{x-1}+………+a_{1}+a_{0}$, $3$ দ্বারা নিঃশেষে বিভাজ্য হয়।

একইভাবে বিভাজ্যতার অন্য যেসব সূত্র আছে সেগুলোও Modular Arithmatic ব্যবহার করে সমাধান কর।

সমস্যা ২ : $5^{10}$ কে $3$ দ্বারা ভাগ করলে কত ভাগশেষ থাকে?

সমাধান : $5$ কে $3$ দ্বারা ভাগ করলে $2$ ভাগশেষ থাকে। অর্থাৎ,

$5 \equiv 2$ $\text{(mod 3)}$.

বা, $5^{10} \equiv 2^{10}$ $\text{(mod 3)}$. ((vi) থেকে)

এখন,$2^{2} \equiv 1$ $\text{(mod 3)}$.

$\therefore$ $2^{10}=(2^{2})^{5} \equiv 1^{5}=1$ $\text{(mod 3)}$.

তাহলে আমরা পেলাম, $5^{10} \equiv 2^{10}$ $\text{(mod 3}$ এবং $2^{10} \equiv 1$ $\text{(mod 3)}$.

(iii) থেকে আমরা জানি, যদি $a \equiv b$ $\text{(mod m)}$ হয় এবং $b \equiv c$ $\text{(mod m)}$ হয়,তাহলে $a \equiv c$ $\text{(mod m)}$ হবে।

সুতরাং, $5^{10} \equiv 1$ $\text{(mod 3)}$.

সমস্যা ৩ : $17^{9}$ এর শেষ(এককের) অঙ্কটি কত?

এককের অঙ্ক নির্ণয়ের জন্য আমরা কি করতে পারি? কত এর mod নিতে পারি চিন্তা কর।

সমাধান : এককের অঙ্ক নির্ণয়ের ক্ষেত্রে $\text{mod 10}$ নিতে হবে। কারণ যেকোনো সংখ্যাকে $10x+y$ আকারে লেখা যায় যেখানে $0 \leq y \leq 9$।

যেমন: $52147836=10 \times 5214783+6$.

এখানে $10 \times 5214783$, $10$ দ্বারা নিঃশেষে বিভাজ্য। তাই $10 \times 5214783+6$ কে $10$ দ্বারা ভাগ করলে $6$ অবশিষ্ট থাকে যা $52147836$ সংখ্যাটির এককের অঙ্ক।

এখন, $17 \equiv 7$ $\text{(mod 10)}$ $\Rightarrow$ $17^{9} \equiv 7^{9}$ $\text{(mod 10)}$.

আবার, $7^{2} \equiv 49 \equiv -1$ $\text{(mod 10)}$ $\Rightarrow$ $7^{8}=(7^{2})^{4} \equiv (-1)^{4} \equiv 1$ $\text{(mod 10)}$.

এখন, $7^{9}=7^{8} \times 7 \equiv 1 \times 7 \equiv 7$ $\text{(mod 10)}$.

NOTE: একই কারণে শেষ দুটি অঙ্ক (একক ও দশকের অঙ্ক) নির্ণয় করতে বললে $\mod 100$, শেষ তিনটি অঙ্ক (একক,দশক ও শতকের অঙ্ক) নির্ণয় করতে বললে $\mod 1000$ নিতে হবে। অর্থাৎ শেষের $k$ টি অঙ্ক নির্ণয় করতে বললে $\mod 10^k$ নিতে হবে।

Definition

Two integers, $a$ and $b$, are congruent modulo $n$ if and only if they have the same remainder when divided by $n$

In other words, for some integer $k$ (positive or negative):

$$a=b+kn$$

or

$$a-b=kn$$

When two numbers are congruent modulo $n$, it is denoted by:

$$a \equiv b \pmod n$$

Manipulations in congreuence modulo $n$

**A1: ** Given that $a\equiv b \pmod n$, then $a+c\equiv b+c \pmod n$

A2 Given that $a\equiv b \pmod n$ and $c\equiv d \pmod n$, then $a+c\equiv b+d \pmod n$

**M1: ** Given that $a\equiv b \pmod n$, then $ac\equiv bc \pmod n$

**M2: ** Given that $a\equiv b \pmod n$ and $c\equiv d \pmod n$, then $ac\equiv bd \pmod n$

**M3: ** Given that $a\equiv b \pmod n$, then $a^c\equiv b^c \pmod n$

This explanation is going to be quite long because it is going to explain the modulus function. Skip through this next part if you like!

There is an equivalence relation called the "modulo $n$" equivalence relation that is written like this: $a \equiv b \hspace{1mm}mod \hspace{1mm}c .$ a and b are said to be equivalent modulo c if and only if $\frac{\left(a-b\right)}{c}$ is an integer. It should be obvious that $a \equiv a \hspace{1mm}mod \hspace{1mm}c$ for any and all integers a and c.

In math, for convenience, we refer to a number as another number modulo another number. That is, $a \hspace{1mm}mod \hspace{1mm} b = c, where \hspace{1mm}0 \leq c > b.$ So if I asked you,"what is 8 mod 3?", you should say, "2!", because 2 is the only value of c that satisfies the equation above, where a=8 and b=3. Obviously c is unique for all choices of a and b. Now here is a nifty theorem below that you can try to prove yourself:

If a,b and c are integers, $ab\hspace{1mm}mod\hspace{1mm}c=\left[\left(a\hspace{1mm}mod\hspace{1mm}c\right)\cdot\left(b\hspace{1mm}mod\hspace{1mm}c\right)\right]mod\hspace{1mm}c$

Here is a more intuitive and easier to prove theorem: $\left(a+b\right)\hspace{1mm}mod\hspace{1mm}c=\left(a\hspace{1mm}mod\hspace{1mm}c\right)+\left(b\hspace{1mm}mod\hspace{1mm}c\right)$

This is a great introduction to modular arithmetic.