مطابقت

تعریف: اگر صحیح عدد a صحیح عدد b کو (پورا) تقسیم کرتا ہے، تو اس کو یوں لکھا جاتا ہے: $\ a | b$
مثال: $\ 2 | 6$

مطابقت (تعریف): چلو $\ m>0$ ۔ ہم کہتے ہیں کہ a مطابق ہے b کے، بہ چکر m ، اگر $\ m | b-a$ اور اس کو یوں لکھتے ہیں
$\ a \equiv b \mod m$
مثال:
$\ 18 \equiv 4 \mod 7$ کیونکہ $\ 7 | 18-4$

$\ 18 \equiv 0 \mod 6$ کیونکہ $\ 6 | 18-0$

مطابقت کو انگریزی میں congruence کہتے ہیں، اور بہ چکر کو modulo یا mod ۔ اس طرح مساوات کے طور پر لکھنا بہت مفید ثابت ہوتا ہے، جیسا کہ ہم نیچے دیکھیں گے۔

[ترمیم] مسلئہ اثباتی

چلو $\ m>0$ قدرتی عدد ہو ۔ نیچے a اور b صحیح عدد ہیں، اور $\ m_1>0$

اگر $\ a \equiv b \mod m$ ، تو پھر

$\ b \equiv a \mod m$

اگر $\ a \equiv b \mod m$ اور $\ b \equiv c \mod m$ ، تو پھر

$\ a \equiv c \mod m$

$\ (a +b) \mod m = (a \mod m) + (b \mod m)$

$\ (a \times b) \mod m = (a \mod m) \times (b \mod m)$

اگر $\ a \equiv b \mod m$ اور $\ m_1 | m$ ، تو پھر

$\ a \equiv b \mod m_1$

مثال:
$\begin{matrix} 3^3 \mod 4 &=& ((3 \times 3) \mod 4) \times 3 \mod 4 \\ &=& (9 \mod 4) \times 3 \mod 4 \\ &=& 5 \times 3 \mod 4 \\ &=& 15 \mod 4 = 3 \\ \end{matrix}$

[ترمیم] مثلئہ اثباتی

اگر صحیح اعداد a اور b کا عاد اعظم $\ \gcd(a,b)=m_1 > 0$ ہو، اور $\ m=m_1 \times m_2 >0$ ، تو
$\ a x \equiv a y \mod m \iff x \equiv y \mod m_2$

مثال: دی گئ مساوات: $35 \equiv 5 \mod 6$
اب چونکہ $\gcd(6,5)=1$ اس لئے ہم مساوات کے دونوں طرف 5 سے کاٹ سکتے ہیں: $7 \equiv 1 \mod 6$
اس مثٓال میں مسلئہ کی ایک خاص صورت استعمال ہوئی ہے، جسے "کاٹنے" کا اصول کہتے ہیں۔

[ترمیم] مسلئہ اثباتی

اگر $a \equiv b \mod m$
تو پھر $a^n \equiv b^n \mod m$
کسی بھی مثبت n کے لیے۔

[ترمیم] مطابقت جماعت

بہ چکر n کا عمل صحیح اعداد کو n جماعتوں میں بانٹ دیتا ہے۔ مثلاً n=3 کے لیے، یہ تین جماعتیں بنتی ہیں: $\begin{matrix} \{ \cdots, -9, -6, -3, 0, 3, 6, 9, \cdots \}, \\ \{ \cdots, -10, -7, -4, 1, 4, 7, 10, \cdots \}, \\ \{ \cdots, -11, -8, -5, 2, 5, 8, 11,\cdots \} \\ \end{matrix}$
ان جماعتوں کے نمائندہ ارکان 0 ، 1 ، اور 2، ہیں۔ گویا n=3 کا ایک مطابقت نظام $\ \{0,1,2\}$ ہے، جو اس کا بنیادی مطابقت نظام کہلاتا ہے۔ اسی طرح دوسرے مطابقت نظاموں میں شامل ہیں:
$\ \{1,2,3\}$ ، $\ \{2,3,4\}$ وغیرہ۔

[ترمیم] مطابقت مساوات

مسلئہ اثباتی: درجہ اول کی مطابقت مساوات
$a x \equiv b \mod m$
اس مساوات کا حل ممکن ہے، اور صرف اسی صورت ممکن ہے، جب $\ \gcd(a,m) | b$
اگر ایک حل $x=x_0$ ہے، تو تمام حل یوں لکھے جا سکتے ہیں
$x = x_0 + \frac{m v}{\gcd(a,m)}$ جہاں v بھاگتا ہے بہ چکر $\ \gcd(a,b)$ کے کسی بھی مطابقت نظام میں۔

[ترمیم] مثال

مساوات
$9 x \equiv 33 \mod 48$
اب چونکہ $\ \gcd(9,48)=3$ ، اور 3 تقسیم کرتا ہے 48 کو، اس لیے اس مساوات کا حل موجود ہے۔ ایک حل $x_0=9$ ہے۔ اور سارے حل یوں ہیں:
$x = 9 + \frac{48 v}{3} = \{9, 25, 41\}$
چونکہ v عدد 3 کے بنیادی مطابقت نظام میں بھاگتا ہے، $v=\{0,1,2\}$