مطابقت

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

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


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

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

مسلئہ اثباتی

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

• اگر $a\equiv bmodm$، تو پھر

$b\equiv amodm$

• اگر $a\equiv bmodm$ اور $b\equiv cmodm$، تو پھر

$a\equiv cmodm$

• $(a+b)modm=(amodm)+(bmodm)$
• $(a\times b)modm=(amodm)\times (bmodm)$
• اگر $a\equiv bmodm$ اور $m_1|m$، تو پھر

$a\equiv bmod{m}_1$

مثال:
$\begin{array}{ccc}{3}^{3}mod4& =& ((3\times 3)mod4)\times 3mod4\\ & =& (9mod4)\times 3mod4\\ & =& 5\times 3mod4\\ & =& 15mod4=3\end{array}$

مثلئہ اثباتی

اگر صحیح اعداد a اور b کا عاد اعظم $\gcd (a,b)=m_1>0$ ہو اور $m=m_1\times m_2>0$، تو
$ax\equiv aymodm⟺x\equiv ymod{m}_2$

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

مسلئہ اثباتی

اگر $a\equiv bmodm$
تو پھر $a^n\equiv b^{n}modm$
کسی بھی مثبت n کے لیے۔

مطابقت جماعت

بہ چکر n کا عمل صحیح اعداد کو n جماعتوں میں بانٹ دیتا ہے۔ مثلاً n=3 کے لیے، یہ تین جماعتیں بنتی ہیں: $\begin{array}{c}\{\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{array}$
ان جماعتوں کے نمائندہ ارکان 0، 1 اور 2، ہیں۔ گویا n=3 کا ایک مطابقت نظام $\{0,1,2\}$ ہے، جو اس کا بنیادی مطابقت نظام کہلاتا ہے۔ اسی طرح دوسرے مطابقت نظاموں میں شامل ہیں:
$\{1,2,3\}$، $\{2,3,4\}$ وغیرہ۔

مطابقت مساوات

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

مثال

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

مزید دیکھیے

• محدود میدان