التقسيم الإقليدي

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 67 صور
الموسوعة الحرة
ينقسم العدد 17 إلى 3 مجموعات من 5، ويتبقى منه 2. في هذه الحالة، المقسوم هو 17، والمقسوم عليه هو 3، وناتج القسمة هو 5، والباقي هو 2 (وهو أصغر من المقسوم عليه 3)، أو بصورة رمزية أكثر، 17 = (3 × 5) + 2.

في الحساب ، القسمة الإقليدية - أو القسمة مع الباقي - هي عملية قسمة عدد صحيح (المقسوم عليه) على عدد صحيح آخر (المقسوم عليه)، بحيث يكون الناتج عددًا صحيحًا ، والباقي عددًا طبيعيًا أصغر من القيمة المطلقة للمقسوم عليه. ومن خصائصها الأساسية أن الناتج والباقي موجودان وفريدان، في ظل شروط معينة. وبسبب هذه الخاصية الفريدة، غالبًا ما تُدرس القسمة الإقليدية دون الإشارة إلى أي طريقة حسابية، ودون حساب الناتج والباقي بشكل صريح. تُسمى طرق الحساب هذه بخوارزميات القسمة الصحيحة ، وأشهرها القسمة المطولة .

تُعدّ القسمة الإقليدية، وخوارزميات حسابها، أساسيةً للعديد من المسائل المتعلقة بالأعداد الصحيحة، مثل خوارزمية إقليدس لإيجاد القاسم المشترك الأكبر لعددين صحيحين، [ 1 ] والحساب النمطي ، الذي يُعنى فقط بالباقي. [ 2 ] تُسمى العملية التي تتضمن حساب الباقي فقط بعملية النمط ، [ 3 ] وتُستخدم بكثرة في كلٍّ من الرياضيات وعلوم الحاسوب.

تحتوي الفطيرة على 9 شرائح، لذا يحصل كل شخص من الأشخاص الأربعة على شريحتين وتبقى شريحة واحدة.

نظرية القسمة

تعتمد عملية القسمة الإقليدية على النتيجة التالية، والتي تسمى أحيانًا بنظرية القسمة الإقليدية .

بفرض عددين صحيحينأ{\displaystyle a}وب{\displaystyle b}، معب≠0{\displaystyle b\neq 0}توجد أعداد صحيحة فريدةq{\displaystyle q}ور{\displaystyle r}بحيث

أ=بq+ر{\displaystyle a=bq+r}،

و

0≤ر<|ب|{\displaystyle 0\leq r<|b|}،

أين|ب|{\displaystyle |b|}يشير إلى القيمة المطلقة لـب{\displaystyle b}[ 4 ]​

في النظرية المذكورة أعلاه، لكل عدد من الأعداد الصحيحة الأربعة اسم خاص به:أ{\displaystyle a}يُطلق عليه اسم الأرباح الموزعة ،ب{\displaystyle b}يُسمى المقسوم عليه ،q{\displaystyle q}يُطلق عليه اسم الناتج ور{\displaystyle r}يُطلق عليه اسم الباقي .

تُسمى عملية حساب ناتج القسمة والباقي من المقسوم والمقسوم عليه بالقسمة ، أو في حالة الغموض، بالقسمة الإقليدية . يُشار إلى هذه النظرية غالبًا باسم خوارزمية القسمة (مع أنها نظرية وليست خوارزمية)، لأن برهانها كما هو موضح أدناه يُسهّل استخدام خوارزمية قسمة بسيطة لحسابq{\displaystyle q}ور{\displaystyle r}(انظر قسم البرهان للمزيد).

لا يُعرَّف القسمة في الحالة التيب=0{\displaystyle b=0}انظر القسمة على صفر .

أما بالنسبة للباقي وعملية باقي القسمة ، فهناك اصطلاحات أخرى غير0≤ر<|ب|{\displaystyle 0\leq r<|b|}انظر §  فترات أخرى للباقي .

تعميم

على الرغم من أن القسمة الإقليدية ونظرية القسمة كانتا تقتصران في الأصل على الأعداد الصحيحة، إلا أنه يمكن تعميمهما على كثيرات الحدود أحادية المتغير على حقل وعلى المجالات الإقليدية.

في حالة كثيرات الحدود أحادية المتغير ، يكمن الاختلاف الرئيسي في أن المتباينات0≤ر<|ب|{\displaystyle 0\leq r<|b|}يتم استبدالها بـ

ر=0{\displaystyle r=0}أودرجة⁡ر<درجة⁡ب،{\displaystyle \deg r<\deg b,}

أيندرجة{\displaystyle \deg }يشير إلى درجة متعددة الحدود .

في التعميم إلى المجالات الإقليدية، تصبح المتباينة

ر=0{\displaystyle r=0}أوو(ر)<و(ب)،{\displaystyle f(r)<f(b),}

أينو{\displaystyle f}يشير إلى دالة محددة من المجال إلى الأعداد الطبيعية تسمى "الدالة الإقليدية".

تظل خاصية تفرد ناتج القسمة والباقي صحيحة بالنسبة لكثيرات الحدود، ولكنها خاطئة بشكل عام.

تاريخ

على الرغم من أن "القسمة الإقليدية" سميت على اسم إقليدس ، إلا أنه يبدو أنه لم يكن يعرف نظرية الوجود والوحدانية، وأن طريقة الحساب الوحيدة التي كان يعرفها هي القسمة عن طريق الطرح المتكرر .

قبل اختراع نظام الأرقام الهندية العربية ، الذي أدخله فيبوناتشي إلى أوروبا خلال القرن الثالث عشر ، كانت عملية القسمة بالغة الصعوبة، ولم يكن يتقنها إلا أفضل علماء الرياضيات . أما اليوم، فمعظم خوارزميات القسمة ، بما فيها القسمة المطولة ، تعتمد على هذا النظام أو أحد مشتقاته، كالأعداد الثنائية . ويُستثنى من ذلك قسمة نيوتن-رافسون ، التي لا تعتمد على أي نظام عددي .

ظهر مصطلح "القسمة الإقليدية" خلال القرن العشرين كاختصار لـ "قسمة الحلقات الإقليدية ". وقد اعتمده علماء الرياضيات بسرعة لتمييز هذه القسمة عن أنواع القسمة الأخرى للأعداد.

مثال بديهي

لنفترض أن فطيرة تحتوي على 9 شرائح، ويراد تقسيمها بالتساوي بين 4 أشخاص. باستخدام القسمة الإقليدية، فإن 9 مقسومة على 4 تساوي 2 والباقي 1. بعبارة أخرى، يحصل كل شخص على شريحتين من الفطيرة، وتبقى شريحة واحدة.

يمكن التأكد من ذلك باستخدام الضرب، وهو عكس القسمة: إذا حصل كل شخص من الأشخاص الأربعة على شريحتين، فإن المجموع الكلي هو 4 × 2 = 8 شرائح. وبإضافة الشريحة المتبقية، يصبح المجموع 9 شرائح. باختصار: 9 = 4 × 2 + 1.

بشكل عام، إذا تم تحديد عدد الشرائحأ{\displaystyle a}ويُشار إلى عدد الأشخاصب{\displaystyle b}ثم يمكن تقسيم الكعكة بالتساوي بين الناس بحيث يحصل كل شخص علىq{\displaystyle q}شرائح (الناتج)، مع عدد معين من الشرائحر<ب{\displaystyle r<b}وهو المتبقي (الباقي). وفي هذه الحالة، تكون المعادلةأ=بq+ر{\displaystyle a=bq+r}يحجز.

إذا تم تقسيم 9 شرائح بين 3 أشخاص بدلاً من 4، فسيحصل كل منهم على 3 ولن يتبقى أي شريحة، مما يعني أن الباقي سيكون صفرًا، مما يؤدي إلى استنتاج أن 3 يقسم 9 بالتساوي، أو أن 3 يقسم 9.

يمكن أيضًا توسيع القسمة الإقليدية لتشمل المقسوم السالب (أو المقسوم عليه السالب) باستخدام نفس الصيغة؛ على سبيل المثال −9 = 4 × (−3) + 3، مما يعني أن −9 مقسومًا على 4 يساوي −3 مع الباقي 3.

أمثلة

  • إذا كان a = 7 و b = 3، فإن q = 2 و r = 1، لأن 7 = 3 × 2 + 1.
  • إذا كان a = 7 و b = −3، فإن q = −2 و r = 1، لأن 7 = −3 × (−2) + 1.
  • إذا كان a = −7 و b = 3، فإن q = −3 و r = 2، لأن −7 = 3 × (−3) + 2.
  • إذا كان a = −7 و b = −3، فإن q = 3 و r = 2، لأن −7 = −3 × 3 + 2.

دليل

يعتمد البرهان التالي لنظرية القسمة على حقيقة أن متتالية متناقصة من الأعداد الصحيحة غير السالبة تتوقف في النهاية. وينقسم إلى جزأين: أحدهما لإثبات وجود متتاليات متناقصة، والآخر لإثبات تفردها.q{\displaystyle q}ور{\displaystyle r}تستخدم براهين أخرى مبدأ الترتيب الجيد (أي، التأكيد على أن كل مجموعة غير فارغة من الأعداد الصحيحة غير السالبة تحتوي على أصغر عنصر) لتبسيط الاستدلال، ولكن يعيبها عدم توفير خوارزمية مباشرة لحل القسمة (انظر §  الفعالية لمزيد من المعلومات). [ 5 ]

وجود

لإثبات وجود القسمة الإقليدية، يمكن للمرء أن يفترضب>0،{\displaystyle b>0,}بما أن، إذاب<0،{\displaystyle b<0,}المساواة أ=بq+ر{\displaystyle a=bq+r}يمكن إعادة كتابتهاأ=(-ب)(-q)+ر.{\displaystyle a=(-b)(-q)+r.}لذا، إذا كانت المساواة الأخيرة عبارة عن قسمة إقليدية مع-ب>0،{\displaystyle -b>0,}الأول هو أيضاً تقسيم إقليدي.

منحب>0{\displaystyle b>0}وأ،{\displaystyle a,}يوجد عدد صحيحq1{\displaystyle q_{1}}ور1≥0{\displaystyle r_{1}\geq 0}بحيثأ=بq1+ر1؛{\displaystyle a=bq_{1}+r_{1};}على سبيل المثال،q1=0{\displaystyle q_{1}=0}ور1=أ{\displaystyle r_{1}=a}لوأ≥0،{\displaystyle a\geq 0,}وغير ذلكq1=أ{\displaystyle q_{1}=a}ور1=أ-أب.{\displaystyle r_{1}=a-ab.}

يتركq{\displaystyle q}ور{\displaystyle r}ليكن زوجًا من الأرقام بحيثر{\displaystyle r}غير سالبة وقيمة دنيا. إذار<ب،{\displaystyle r<b,}لدينا قسمة إقليدية. وبالتالي، علينا أن نثبت أنه إذار≥ب،{\displaystyle r\geq b,}ثمر{\displaystyle r}ليس الحد الأدنى. في الواقع، إذار≥ب،{\displaystyle r\geq b,}يمتلك المرءأ=ب(q+1)+(ر-ب)،{\displaystyle a=b(q+1)+(rb),}مع0≤ر-ب<ر،{\displaystyle 0\leq rb<r,}ور{\displaystyle r}ليس الحد الأدنى

يثبت هذا وجودها في جميع الحالات. كما يوفر خوارزمية لحساب ناتج القسمة والباقي، بدءًا منq=0{\displaystyle q=0}(لوأ≥0{\displaystyle a\geq 0}) وإضافة1{\displaystyle 1}إلى ذلك حتىأ-بq<ب.{\displaystyle a-bq<b.}إلا أن هذه الخوارزمية ليست فعالة، لأن عدد خطواتها من رتبةأ/ب{\displaystyle a/b}

رجل فريد

زوج الأعداد الصحيحةر{\displaystyle r}وq{\displaystyle q}بحيثأ=بq+ر{\displaystyle a=bq+r}فريد من نوعه، بمعنى أنه لا يمكن أن يوجد زوج آخر من الأعداد الصحيحة يحقق نفس الشرط في نظرية القسمة الإقليدية. بعبارة أخرى، إذا كان لدينا قسمة أخرى لـأ{\displaystyle a}بواسطةب{\displaystyle b}، يقولأ=بq′+ر′{\displaystyle a=bq'+r'}مع0≤ر′<|ب|{\displaystyle 0\leq r'<|b|}إذن يجب أن يكون لدينا ذلك

q′=q و ر′=ر{\displaystyle q'=q{\text{ و }}r'=r}.

لإثبات هذه العبارة، نبدأ أولاً بالافتراضات التالية:

0≤ر<|ب|{\displaystyle 0\leq r<|b|}
0≤ر′<|ب|{\displaystyle 0\leq r'<|b|}
أ=بq+ر{\displaystyle a=bq+r}
أ=بq′+ر′{\displaystyle a=bq'+r'}

بطرح المعادلتين نحصل على

ب(q-q′)=ر′-ر{\displaystyle b(qq')=r'-r}.

لذاب{\displaystyle b}هو قاسم لـر′-ر{\displaystyle r'-r}. مثل

|ر′-ر|<|ب|{\displaystyle |r'-r|<|b|}

من خلال المتباينات المذكورة أعلاه، نحصل على

ر′-ر=0{\displaystyle r'-r=0}،

و

ب(q-q′)=0{\displaystyle b(qq')=0}.

منذب≠0{\displaystyle b\neq 0}، فهمنا ذلكر=ر′{\displaystyle r=r'}وq=q′{\displaystyle q=q'}وهذا يثبت الجزء الخاص بالتفرد في نظرية القسمة الإقليدية.

فعالية

بشكل عام، لا يُقدّم برهان الوجود خوارزمية لحساب ناتج القسمة والباقي، لكن البرهان المذكور أعلاه يُقدّم خوارزمية مباشرة (انظر القسمة بالطرح المتكرر )، مع أنها ليست فعّالة جدًا لأنها تتطلب عددًا من الخطوات يُساوي حجم ناتج القسمة. ويرجع ذلك إلى أنها تستخدم فقط عمليات الجمع والطرح والمقارنة للأعداد الصحيحة، دون استخدام الضرب، أو أي تمثيل خاص للأعداد الصحيحة كالترميز العشري.

فيما يتعلق بالتدوين العشري، تُعدّ القسمة المطولة خوارزمية أكثر كفاءة لحل مسائل القسمة الإقليدية. كما أن تعميمها على التدوين الثنائي والسداسي عشري يُتيح مزيدًا من المرونة وإمكانية التنفيذ الحاسوبي. مع ذلك، بالنسبة للمدخلات الكبيرة، تُفضّل عادةً الخوارزميات التي تُختزل القسمة إلى ضرب، مثل قسمة نيوتن-رافسون ، لأنها لا تحتاج إلا إلى وقت يتناسب مع وقت الضرب اللازم للتحقق من النتيجة، بغض النظر عن خوارزمية الضرب المستخدمة (للمزيد، انظر: طرق القسمة السريعة ).

المتغيرات

يسمح التقسيم الإقليدي بعدد من المتغيرات، بعضها مدرج أدناه.

فترات أخرى للباقي

في القسمة الإقليدية مع d كمقسوم عليه، يُفترض أن الباقي ينتمي إلى الفترة [0, d ) التي طولها | d | . يمكن استخدام أي فترة أخرى بنفس الطول. بتعبير أدق، عند إعطاء أعداد صحيحةم{\displaystyle m}،أ{\displaystyle a}،د{\displaystyle d}معم>0{\displaystyle m>0}توجد أعداد صحيحة فريدةq{\displaystyle q}ور{\displaystyle r}معد≤ر<م+د{\displaystyle d\leq r<m+d}بحيثأ=مq+ر{\displaystyle a=mq+r}.

على وجه الخصوص، إذاد=-⌊م2⌋{\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }ثم-⌊م2⌋≤ر<م-⌊م2⌋{\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }يُطلق على هذا القسم اسم القسمة المركزية ، وباقي القسمةر{\displaystyle r}يُطلق عليه اسم الباقي المركزي أو الباقي المطلق الأصغر .

يُستخدم هذا لتقريب الأعداد الحقيقية : القسمة الإقليدية تحدد القطع ، والقسمة المركزية تحدد التقريب .

قسم مونتغمري

معطى أعداد صحيحةأ{\displaystyle a}،م{\displaystyle m}وR،{\displaystyle R,}معم>0{\displaystyle m>0}والقاسم المشترك الأكبر(R،م)=1،{\displaystyle \gcd(R,m)=1,}يتركR-1{\displaystyle R^{-1}}ليكن المعكوس الضربي المعياري لـR{\displaystyle R}(أي،0<R-1<م{\displaystyle 0<R^{-1}<m}معR-1R-1{\displaystyle R^{-1}R-1}كونه من مضاعفاتم{\displaystyle m}إذا كان ، فإنه يوجد عدد صحيح فريدq{\displaystyle q}ور{\displaystyle r}مع0≤ر<م{\displaystyle 0\leq r<m}بحيثأ=مq+R-1⋅ر{\displaystyle a=mq+R^{-1}\cdot r}تُعمم هذه النتيجة قسمة هينسل الفردية (1900). [ 6 ]

القيمةر{\displaystyle r}هو المتبقي N المحدد في اختزال مونتغمري .

في المجالات الإقليدية

تُعرَّف المجالات الإقليدية (المعروفة أيضًا باسم الحلقات الإقليدية ) [ 7 ] بأنها مجالات تكاملية تدعم التعميم التالي للقسمة الإقليدية:

بالنظر إلى عنصرأ{\displaystyle a}وعنصر غير صفريب{\displaystyle b}في مجال إقليديR{\displaystyle R}مزودة بدالة إقليديةد{\displaystyle d}(المعروفة أيضًا باسم التقييم الإقليدي [ 8 ] أو دالة الدرجة [ 7 ] )، يوجدq{\displaystyle q}ور{\displaystyle r}فيR{\displaystyle R}بحيثأ=بq+ر{\displaystyle a=bq+r}وإمار=0{\displaystyle r=0}أود(ر)<د(ب){\displaystyle d(r)<d(b)}.

فرادةq{\displaystyle q}ور{\displaystyle r}ليس ذلك مطلوبًا. [ 1 ] يحدث ذلك فقط في حالات استثنائية، عادةً بالنسبة لكثيرات الحدود أحادية المتغير ، وللأعداد الصحيحة، إذا تحقق الشرط الإضافير≥0{\displaystyle r\geq 0}تمت إضافتها.

تشمل أمثلة المجالات الإقليدية الحقول ، وحلقات كثيرات الحدود ذات المتغير الواحد على حقل، والأعداد الصحيحة الغاوسية . وقد حظي تقسيم كثيرات الحدود الإقليدي باهتمام خاص وتطورات محددة.

انظر أيضاً

مراجع

الاقتباسات

  1. 1 2 "خوارزميات القسمة والإقليدية" . www-groups.mcs.st-andrews.ac.uk . مؤرشف من الأصل بتاريخ 2021-05-06 . تم الاطلاع عليه بتاريخ 2019-11-15 .
  2. ↑ "ما هو الحساب النمطي؟" . أكاديمية خان . تم الاطلاع عليه بتاريخ 15-11-2019 .
  3. ↑ "متعة الحساب النمطي - شرح أفضل" . betterexplained.com . تم الاطلاع عليه بتاريخ 15 نوفمبر 2019 .
  4. ↑ بيرتون، ديفيد م. (2010). نظرية الأعداد الأولية . ماكجرو هيل. ص 17-19 . ISBN  978-0-07-338314-9.
  5. ↑ دوربين، جون ر. (1992). الجبر الحديث : مقدمة ( الطبعة الثالثة). نيويورك: وايلي. ص 63. ISBN    0-471-51001-7.
  6. ↑ هاينينغ فان؛ مينغ غو؛ جياغوانغ صن؛ كوك-يان لام (2012). "الحصول على المزيد من الصيغ الشبيهة بصيغة كاراتسوبا على الحقل الثنائي". أمن المعلومات IET . 6 (1): 14-19 . CiteSeerX 10.1.1.215.1576 . doi : 10.1049/iet-ifs.2010.0114 . 
  7. 1 2 روتمان 2006 ، ص 267
  8. ↑ فرالي 1993 ، ص 376

المراجع

  • Fraleigh، John B. (1993)، دورة أولى في الجبر التجريدي (  الطبعة الخامسة)، أديسون ويسلي، ISBN 978-0-201-53467-2
  • روتمان، جوزيف ج. (2006)، مدخل إلى الجبر المجرد مع تطبيقات (  الطبعة الثالثة)، برنتيس هول، رقم ISBN 978-0-13-186267-8