مطابقت کا مسودہ

اگر [[عدد#صحیح عدد|صحیح عدد]] ''a'' صحیح عدد ''b'' کو (پورا) تقسیم کرتا ہے، تو اس کو یوں لکھا جاتا ہے:
<math>\ a | b</math>
<br/>
مثال:
<math>\ 2 | 6</math>

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

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

== مسلئہ اثباتی ==
چلو <math>\ m>0</math> [[عدد#قدرتی عدد|قدرتی عدد]] ہو۔ نیچے ''a'' اور ''b'' [[عدد#صحیح عدد|صحیح عدد]] ہیں اور <math>\ m_1>0</math>
* اگر <math>\ a \equiv b \mod m</math>، تو پھر
<math>\ b \equiv a \mod m</math>
* اگر <math>\ a \equiv b \mod m</math> اور <math>\ b \equiv c \mod m</math>، تو پھر
<math>\ a \equiv c \mod m</math>
* <math>\ (a +b) \mod m = (a \mod m) + (b \mod m) </math>
* <math>\ (a \times b) \mod m = (a \mod m) \times (b \mod m) </math>
* اگر <math>\ a \equiv b \mod m</math> اور <math>\ m_1 | m</math>، تو پھر
<math>\ a \equiv b \mod m_1</math>

مثال: <br/>
<math> \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}
</math>

== مثلئہ اثباتی ==
اگر صحیح اعداد ''a'' اور ''b'' کا [[عدد#عادِ اعظم|عاد اعظم]] <math>\ \gcd(a,b)=m_1 > 0</math> ہو اور <math>\ m=m_1 \times m_2 >0</math>، تو
<br/>
<math>\ a x \equiv a y \mod m \iff x \equiv y \mod m_2</math>

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

== مسلئہ اثباتی ==
اگر
<math> a \equiv b \mod m </math> <br/>
تو پھر
<math> a^n \equiv b^n \mod m </math> <br/>
کسی بھی مثبت ''n'' کے لیے۔

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

== مطابقت مساوات ==
مسئلہ اثباتی: درجہ اول کی مطابقت مساوات <br/>
<math>
a x \equiv b \mod m
</math>
<br/>
اس مساوات کا حل ممکن ہے اور صرف اسی صورت ممکن ہے، جب
<math>\ \gcd(a,m) | b </math>
<br/>
اگر ایک حل <math>x=x_0</math> ہے، تو تمام حل یوں لکھے جا سکتے ہیں <br/>
<math> x = x_0 + \frac{m v}{\gcd(a,m)}</math>
جہاں ''v'' بھاگتا ہے بہ چکر <math> \ \gcd(a,b) </math> کے کسی بھی مطابقت نظام میں۔
<br/>
=== مثال ===
مساوات <br/>
<math>
9 x \equiv 33 \mod 48
</math>
<br/>
اب چونکہ <math>\ \gcd(9,48)=3</math> اور 3 تقسیم کرتا ہے 48 کو، اس لیے اس مساوات کا حل موجود ہے۔ ایک حل <math>x_0=9</math> ہے۔ اور سارے حل یوں ہیں:
<br/>
<math> x = 9 + \frac{48 v}{3} = \{9, 25, 41\}</math>
<br/>
چونکہ ''v'' عدد 3 کے بنیادی مطابقت نظام میں بھاگتا ہے، <math>v=\{0,1,2\}</math>

== مزید دیکھیے ==
* [[متناہی میدان|محدود میدان]]
{{ریاضی مدد}}


[[زمرہ:نظریہ گروہ]]
[[زمرہ:نظریۂ عدد]]