چینی تقسیم باقی مسئلہ اثباتی

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش

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

دو یکلخت مطابقت مساوات
\ w \equiv a_1 \mod m_1
\ w \equiv a_2 \mod m_2
جہاں \ \gcd(m_1,m_2)=1 ۔ اب اگر ہم x اور y اس طرح نکالیں کہ \ m_1 x \equiv 1  \mod m_2 اور \ m_2 y \equiv 1  \mod m_1
تو دونوں مطابقت مساوات کی تسکین کرتا ہؤا ایک حل یہ ہے \ w = m_1 x a_2 + m_2 y a_1
یہ حل بہ چکر \ m_1 m_2 ہے۔ اس لئے کوئی بھی عدد جو اس حل سے مطابقت رکھے بہ چکر \ m_1 m_2، دونوں مساوات کا یکلخت حل ہے۔ یعنی \ w^\prime \equiv w \mod m_1 m_2 مساوات کے حل ہیں۔
قدیم چین میں یہ مسلئہ اثباتی معلوم تھا اس لیے اس کو "چینی" کہتے ہیں۔

مثال[ترمیم]

دو یکلخت مطابقت مساوات
\ w \equiv 11 \mod 15
\ w \equiv -11 \mod 14
دیکھو کہ \ \gcd(14,15)=1
اب چونکہ
\ 15 x \equiv 1  \mod 14 \longrightarrow x=1
اور
\ 14 y \equiv 1  \mod 15 \longrightarrow y=14
اسلئے مساوات کا حل یہ ہے: \ w = 15 \times 1 \times -11 + 14 \times 14 \times 11 = 1991
اب چونکہ یہ حل بہ چکر  14 \times 15 = 210  ہے، اس لئے سب سے چھوٹا مثبت حل  w=101  ہے۔

مثال[ترمیم]

بابر جمعے جمعے نہاتا ہے۔ اور ہر پانچویں دن منڈی جاتا ہے۔ اس بار وہ ہفتے کے دن منڈی گیا تھا۔ کب ایسا دن آئے گا جب بابر کو جمعے کو منڈی جانا پڑے گا۔
اس جمعے کو ہم صفر لکھتے ہیں، ہفتے کو ایک، اور اس طرح۔ اب جمعے کو نہانے کو ہم ایسے مساوات میں لکھ سکتے ہیں:
\ w \equiv 0 \mod 7
ہر پانچویں دن منڈی جانے کو، اور اس ہفتے، ہفتے والے دن کو منڈی جانے کو یہ مساوات بتاتی ہے:
\ w \equiv 1 \mod 5
اب چونکہ 7 اور 5 باہمی مفرد عدد ہیں، اس لیے چینی مسلئہ اثباتی استعمال ہو سکتا ہے۔
\ 7 x \equiv 1  \mod 5 \longrightarrow x=3
\ 5 y \equiv 1  \mod 7 \longrightarrow y=3
اسلئے ان مساوات کا حل یہ ہے: \ w = 7 \times 3 \times 1 + 5 \times 3 \times 0 = 21
یعنی بابر کو ہر تیسرے جمعے منڈی جانا اور نہانا اسی دن کرنا ہوں گے۔

مسلئہ اثباتی کی زیادہ عام صورت[ترمیم]

یہاں n مطابقت مساوات

\begin{matrix}
 w \equiv a_1 \mod m_1 \\
 w \equiv a_2 \mod m_2 \\
\vdots                             \\
 w \equiv a_n \mod m_n 
\end{matrix}
جہاں مثبت اعداد \ m_1, m_2, \cdots, m_n میں سے ہر دو اعداد باہمی مفرد ہیں (یعنی کسی بھی دو اعداد کا عاد اعظم ایک (1) ہے) ۔
چلو  M = m_1 m_2 \cdots  m_n
اب اگر x_j نیچے دی مطابقت مساوات کا حل ہے
 \ \frac{M}{m_j} x_j \equiv 1  \mod m_j \,,\, j=1,2,\cdots,n
تو تمام n یکلخت مطابقت مساوات کا ایک حل یوں ہو گا
 \ w= \sum_{j=1}^n a_j \frac{M}{m_j} x_j
یہ حل بہ چکر M ہے۔ اس لئے کوئی بھی عدد جو اس حل سے مطابقت رکھے بہ چکر M، تمام n مساوات کا یکلخت حل ہے۔ یعنی \ w^\prime \equiv w \mod M مساوات کے حل ہیں۔

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات