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

مسئلہ اثباتی

دو یکلخت مطابقت مساوات
$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^{'} \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 ⟶ x = 1$
اور
$14 y \equiv 1 mod 15 ⟶ 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 ⟶ x = 3$
$5 y \equiv 1 mod 7 ⟶ 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} \\ ⋮ \\ w \equiv a_{n} mod m_{n} \end{matrix}$
جہاں مثبت اعداد $m_{1}, m_{2}, \dots, m_{n}$ میں سے ہر دو اعداد باہمی مفرد ہیں (یعنی کسی بھی دو اعداد کا عاد اعظم ایک (1) ہے) ۔
چلو $M = m_{1} m_{2} \dots m_{n}$
اب اگر $x_{j}$ نیچے دی مطابقت مساوات کا حل ہے
$\frac{M}{m_{j}} x_{j} \equiv 1 mod m_{j}, j = 1, 2, \dots, n$
تو تمام n یکلخت مطابقت مساوات کا ایک حل یوں ہو گا
$w = \sum_{j = 1}^{n} a_{j} \frac{M}{m_{j}} x_{j}$
یہ حل بہ چکر $M$ ہے۔ اس لیے کوئی بھی عدد جو اس حل سے مطابقت رکھے بہ چکر $M$ ، تمام n مساوات کا یکلخت حل ہے۔ یعنی $w^{'} \equiv w mod M$ مساوات کے حل ہیں۔

سانچہ:ریاضی مدد

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

فہرست

مسئلہ اثباتی

مثال

مثال

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

ویکی پیمائی کی فہرست

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

مسئلہ اثباتی

مثال

مثال

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

ویکی پیمائی کی فہرست

تلاش