القاسم المشترك الأكبر

في الرياضيات ، يُعرف القاسم المشترك الأكبر ( GCD )، أو العامل المشترك الأكبر (GCF) ، لعددين صحيحين أو أكثر ، ليست جميعها أصفارًا، بأنه أكبر عدد صحيح موجب يقسم كل عدد من هذه الأعداد. بالنسبة لعددين صحيحين $x$ و $y$ ، يُرمز للقاسم المشترك الأكبر لـ $x$ و $y بالرمز التالي:$ $\gcd(x,y)$ على سبيل المثال، القاسم المشترك الأكبر للعددين 8 و12 هو 4، أي أن $gcd(8, 12) =$ 4. ^{[ 1 ]}^{[ 2 ]}

في مصطلح "القاسم المشترك الأكبر"، يمكن استبدال صفة "الأعظم" بـ"الأعلى"، وكلمة "القاسم" بـ"العامل"، بحيث تتضمن أسماء أخرى العامل المشترك الأكبر (ق.م.أ) ، إلخ. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}^{[ 6 ]} تاريخيًا، تضمنت أسماء أخرى لنفس المفهوم مقياس القاسم المشترك الأكبر . ^{[ 7 ]}

يمكن توسيع هذا المفهوم ليشمل كثيرات الحدود (انظر القاسم المشترك الأكبر لكثيرات الحدود ) والحلقات التبديلية الأخرى (انظر § في الحلقات التبديلية أدناه).

ملخص

تعريف

القاسم المشترك الأكبر ( GCD) لعددين صحيحين $a$ و $b$ ، أحدهما على الأقل غير صفري، هو أكبر عدد صحيح موجب $d$ بحيث يكون $d$ قاسمًا لكل من $a$ و $b$ ؛ أي، يوجد عددان صحيحان $e$ و $f$ بحيث $a = de$ و $b = df$ ، ويكون $d$ هو أكبر عدد صحيح يحقق هذا الشرط. يُرمز إلى القاسم المشترك الأكبر لـ $a$ و $b$ عمومًا بـ $gcd(a, b)$ . ^{[ 8 ]}

عندما يكون أحد العددين $a$ أو $b$ يساوي صفرًا، فإن القاسم المشترك الأكبر هو القيمة المطلقة للعدد الصحيح غير الصفري: $gcd(a, 0) = gcd(0, a) = | a |$ . هذه الحالة مهمة لأنها الخطوة الأخيرة في خوارزمية إقليدس .

التعريف أعلاه غير مناسب لتعريف $القاسم المشترك الأكبر للعددين 0 و0$ ، إذ لا يوجد عدد صحيح أكبر $n$ بحيث يكون $0 \times n = 0.$ مع ذلك، يُعتبر الصفر قاسمًا أكبر لنفسه إذا فُهم مفهوم "الأكبر " في سياق علاقة قابلية القسمة، لذا يُعرَّف $القاسم المشترك الأكبر للعددين 0 و0 عادةً على أنه$ $0.$ يحافظ هذا على المتطابقات المعتادة للقاسم المشترك الأكبر، ولا سيما متطابقة بيزو ، أي أن $القاسم المشترك الأكبر للعددين$ $a وb يُولِّد نفس المُثُل التي يُولِّدها {a, b}$ $.$ $[$ $9$ ] [ 10 ] $[11$ $]$ $تتبع$ $العديد$ من ^{أنظمة الجبر الحاسوبي}^{هذا الاصطلاح .}^{[ 12 ]} مع ذلك ، ^{يترك بعض المؤلفين} تعريف القاسم $المشترك الأكبر للعددين 0 و0.$ ^{[ 13 ]}

القاسم المشترك الأكبر للعددين $a$ و $b هو$ أكبر قاسم مشترك موجب لهما في علاقة الترتيب الجزئي للقسمة . وهذا يعني أن القواسم المشتركة للعددين $a$ و $b$ هي بالضبط قواسم قاسمهما المشترك الأكبر. ويُبرهن على ذلك عادةً باستخدام مبرهنة إقليدس ، أو النظرية الأساسية في الحساب ، أو خوارزمية إقليدس . وهذا هو معنى كلمة "الأكبر" المستخدم في تعميمات مفهوم القاسم المشترك الأكبر.

مثال

يمكن التعبير عن العدد 54 كحاصل ضرب عددين صحيحين بعدة طرق مختلفة:

54\times 1=27\times 2=18\times 3=9\times 6.

وبالتالي، فإن القائمة الكاملة لقواسم العدد 54 هي: 1، 2، 3، 6، 9، 18، 27، 54. وبالمثل، فإن قواسم العدد 24 هي: 1، 2، 3، 4، 6، 8، 12، 24. والأعداد المشتركة بين هاتين القائمتين هي القواسم المشتركة للعددين 54 و24، أي:

1,2,3,6.

من بين هذه الأعداد، أكبرها هو 6، لذا فهو القاسم المشترك الأكبر :

\gcd(54,24)=6.

عادةً ما تكون عملية حساب جميع قواسم العددين بهذه الطريقة غير فعّالة، خاصةً للأعداد الكبيرة التي لها قواسم كثيرة. تُشرح طرق أكثر كفاءة في قسم الحساب .

الأعداد الأولية فيما بينها

يُطلق على عددين اسم الأعداد الأولية النسبية، أو الأعداد الأولية المشتركة ، إذا كان قاسمهما المشترك الأكبر يساوي $1.$ ^{[ 14 ]} على سبيل المثال، 9 و28 أعداد أولية مشتركة.

منظور هندسي

"مستطيل طويل ونحيف مقسم إلى شبكة من المربعات. يبلغ عرض المستطيل مربعين وارتفاعه خمسة مربعات." — يتم تغطية مستطيل أبعاده 24 × 60 بعشرة بلاطات مربعة أبعادها 12 × 12، حيث 12 هو القاسم المشترك الأكبر للعددين 24 و 60. وبشكل عام، يمكن تغطية مستطيل أبعاده a × b ببلاطات مربعة طول ضلعها c فقط إذا كان c قاسمًا مشتركًا للعددين a و b .

على سبيل المثال، يمكن تقسيم مساحة مستطيلة أبعادها 24 × 60 إلى شبكة من: مربعات 1×1، أو مربعات 2×2، أو مربعات 3×3، أو مربعات 4×4، أو مربعات 6×6، أو مربعات 12×12. وبالتالي، فإن 12 هو القاسم المشترك الأكبر للعددين 24 و60. لذا، يمكن تقسيم مساحة مستطيلة أبعادها 24 × 60 إلى شبكة من مربعات 12×12، بحيث يكون هناك مربعان على أحد الأضلاع ( $24/12 = 2$ ) وخمسة مربعات على الضلع الآخر ( $60/12 = 5$ ).

التطبيقات

تبسيط الكسور

يُعدّ القاسم المشترك الأكبر مفيدًا لتبسيط الكسور إلى أبسط صورة . ^{[ 15 ]} على سبيل المثال، $القاسم المشترك الأكبر للعددين 42 و56 يساوي 14$ ، وبالتالي،

{\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.

المضاعف المشترك الأصغر

يمكن حساب المضاعف المشترك الأصغر لعددين صحيحين ليسا كلاهما صفرًا من خلال قاسمهما المشترك الأكبر، باستخدام العلاقة التالية:

\operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.

حساب

استخدام التحليل إلى العوامل الأولية

يمكن حساب القاسم المشترك الأكبر بتحديد التحليل إلى العوامل الأولية للعددين ومقارنة هذه العوامل. على سبيل المثال، لحساب $القاسم المشترك الأكبر للعددين 48 و180$ ، نجد التحليل إلى العوامل الأولية: 48 ^{= 2⁴ × 3² = 1 و180 = 2² × 3² × 5² = 1} ؛ وبالتالي ^، يكون القاسم ^{المشترك} الأكبر هو 2ⁿ⁻¹ ( ^4,2⁾ × 3ⁿ⁻¹ ( 1,2 ⁾ × 5ⁿ⁻¹ ⁽ 0,1 ) ⁼ 2² ^× 3² = 1² = 12. ^ويكون المضاعف المشترك الأصغر المقابل هو 2ⁿ⁻¹ ^(4,2) × 3ⁿ⁻¹ ^(1,2) × 5ⁿ⁻¹ ^(0,1) = ^2ⁿ⁻¹⁽⁴ × 3² = 5² = ¹² .

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

خوارزمية إقليدس

تعتمد الطريقة التي قدمها إقليدس لحساب القواسم المشتركة الكبرى على حقيقة أنه إذا تم إعطاء عددين صحيحين موجبين $a$ و $b$ بحيث يكون $a > b$ ، فإن القواسم المشتركة لـ $a$ و $b$ هي نفسها القواسم المشتركة لـ $a - b$ و $b$ .

لذا، فإن طريقة إقليدس لحساب القاسم المشترك الأكبر لعددين صحيحين موجبين تتكون من استبدال العدد الأكبر بالفرق بين العددين، وتكرار ذلك حتى يصبح العددان متساويين: وهذا هو القاسم المشترك الأكبر لهما.

على سبيل المثال، لحساب $القاسم المشترك الأكبر (48، 18)$ ، يتم اتباع الخطوات التالية:

\displaystyle \begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)\\&\to \quad \gcd(30-18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)\\&\to \quad \gcd(12-6,6)=\gcd(6,6).\end{aligned}}}

إذن $القاسم المشترك الأكبر (48، 18) = 6$ .

قد تكون هذه الطريقة بطيئة للغاية إذا كان أحد الرقمين أكبر بكثير من الآخر. لذا، يُفضّل عمومًا استخدام الصيغة التالية.

خوارزمية إقليدية

رسم متحرك يوضح تطبيق خوارزمية إقليدس لإيجاد القاسم المشترك الأكبر للعددين 62 و36، وهو 2

الطريقة الأكثر كفاءة هي خوارزمية إقليدس ، وهي صيغة يتم فيها استبدال الفرق بين العددين $a$ و $b$ بباقي القسمة الإقليدية (وتسمى أيضًا القسمة مع الباقي ) لـ $a$ على $b$ .

وباعتبار هذا الباقي هو $a mod b$ ، فإن الخوارزمية تستبدل $(a, b)$ بـ $(b, a mod b)$ بشكل متكرر حتى يصبح الزوج $(d, 0)$ ، حيث $d$ هو القاسم المشترك الأكبر.

على سبيل المثال، لحساب القاسم المشترك الأكبر (48، 18)، تكون العملية الحسابية كما يلي:

\displaystyle \begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd(6,0).\end{aligned}}}

وهذا يعطينا مرة أخرى $القاسم المشترك الأكبر (48، 18) = 6$ .

خوارزمية القاسم المشترك الأكبر الثنائي

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

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

الطريقة هي كما يلي، بدءًا من $a$ و $b$ وهما العددان الصحيحان الموجبان اللذان يتم البحث عن قاسمهما المشترك الأكبر.

إذا كان كل من $a$ و $b$ زوجيًا، فاقسم كليهما على اثنين حتى يصبح أحدهما على الأقل فرديًا؛ ليكن $d$ عدد عمليات القسمة المزدوجة هذه.
إذا كان العدد $a$ زوجيًا، فاقسمه على اثنين حتى يصبح فرديًا.
إذا كان $b$ عددًا زوجيًا، فاقسمه على اثنين حتى يصبح فرديًا.
الآن، كل من $a$ و $b$ عددان فرديان وسيظلان كذلك حتى نهاية العملية الحسابية.
بينما a ≠ b، افعل
- إذا كان $a > b$ ، فاستبدل $a$ بـ $a - b$ واقسم الناتج على اثنين حتى يصبح $a فرديًا (بما أن$ $a$ و $b$ كلاهما فردي، فهناك على الأقل قسمة واحدة على 2).
- إذا كان $a < b$ ، فاستبدل $b$ بـ $b - a$ واقسم الناتج على اثنين حتى يصبح $b فرديًا.$
الآن، $a = b$ ، والقاسم المشترك الأكبر هو $2^{d}a.$

تُحدد الخطوة الأولى قيمة $d$ باعتبارها أعلى قوة للعدد $2$ التي تقسم $a$ و $b$ ، وبالتالي فهي القاسم المشترك الأكبر لهما. لا تُغير أي من الخطوات مجموعة القواسم المشتركة الفردية لـ $a$ و $b$ . وهذا يُبين أن النتيجة صحيحة عند توقف الخوارزمية. تتوقف الخوارزمية في النهاية، لأن كل خطوة تقسم أحد المعاملات على الأقل على $2$ على الأقل . علاوة على ذلك، فإن عدد عمليات القسمة على $2$ ، وبالتالي عدد عمليات الطرح، لا يتجاوز العدد الإجمالي للأرقام.

مثال: ( أ ، ب ، د ) = (48، 18، 0) → (24، 9، 1) → (12، 9، 1) → (6، 9، 1) → (3، 9، 1) → (3، 3، 1) ؛ وبالتالي فإن القاسم المشترك الأكبر الأصلي هو حاصل ضرب 6 في $2 د = 2 1$ و $أ = ب = 3$ .

تتميز خوارزمية القاسم المشترك الأكبر الثنائية بسهولة تطبيقها وكفاءتها العالية على الحواسيب الثنائية. أما تعقيدها الحسابي فهو

O((\log a+\log b)^{2}).

يأتي التربيع في هذا التعقيد من حقيقة أن القسمة على $2$ والطرح يستغرقان وقتًا يتناسب مع عدد بتات الإدخال.

عادةً ما يُعطى التعقيد الحسابي بدلالة طول المدخلات $n . هنا، هذا الطول هو$ $n = log a + log b$ ، وبالتالي يكون التعقيد هو

O(n^{2})

.

خوارزمية ليمر للقاسم المشترك الأكبر

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

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

طرق أخرى

إذا كان كل من $a$ و $b$ غير صفريين، فيمكن حساب القاسم المشترك الأكبر لـ $a$ و $b$ باستخدام المضاعف المشترك الأصغر (LCM) لـ $a$ و $b$ :

\gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}

،

ولكن في أغلب الأحيان يتم حساب المضاعف المشترك الأصغر من القاسم المشترك الأكبر.

باستخدام دالة توماي $f$ ،

\gcd(a,b)=af\left({\frac {b}{a}}\right),

والتي يمكن تعميمها على $a$ و $b$ أعداد نسبية أو أعداد حقيقية قابلة للقياس .

أظهر كيث سلافين أنه بالنسبة لـ $a \geq 1$ الفردي :

\gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})

وهي دالة يمكن تقييمها بالنسبة للمركب b . ^{[ 16 ]} وقد أثبت فولفغانغ شرام أن

\gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}

هي دالة كاملة في المتغير b لجميع الأعداد الصحيحة الموجبة a حيث c _d ( k ) هو مجموع رامانوجان . ^{[ 17 ]}

تعقيد

لقد دُرست التعقيدات الحسابية لحساب القاسم المشترك الأكبر على نطاق واسع. ^{[ 18 ]} إذا استخدمنا خوارزمية إقليدس والخوارزميات الأساسية للضرب والقسمة، فإن حساب القاسم المشترك الأكبر لعددين صحيحين لا يتجاوز عدد بتاتهما $n$ هو $O$ ( $n²$ $)$ $.$ $وهذا$ يعني أن حساب القاسم المشترك الأكبر له، حتى عامل ثابت، نفس تعقيد عملية الضرب.

مع ذلك، إذا استُخدمت خوارزمية ضرب سريعة ، يُمكن تعديل خوارزمية إقليدس لتحسين التعقيد، لكن حساب القاسم المشترك الأكبر يصبح أبطأ من عملية الضرب نفسها. بتعبير أدق، إذا استغرق ضرب عددين صحيحين من $n$ بت زمنًا قدره $T (n)$ ، فإن أسرع خوارزمية معروفة لإيجاد القاسم المشترك الأكبر يكون تعقيدها $O (T (n) log n)$ . وهذا يعني أن أسرع خوارزمية معروفة يكون تعقيدها $O (n (log n) ²)$ .

تعتبر التعقيدات السابقة صالحة للنماذج المعتادة للحوسبة ، وتحديداً آلات تورينج متعددة الأشرطة وآلات الوصول العشوائي .

وبالتالي، فإن حساب القاسم المشترك الأكبر ينتمي إلى فئة المسائل القابلة للحل في زمن شبه خطي . ومن باب أولى ، تنتمي مسألة القرار المقابلة إلى فئة المسائل القابلة للحل في زمن متعدد الحدود ( P) . لا يُعرف ما إذا كانت مسألة القاسم المشترك الأكبر تنتمي إلى فئة NC ، وبالتالي لا توجد طريقة معروفة لموازاتها بكفاءة؛ كما أنها ليست مسألة كاملة من فئة P ، مما يعني أنه من غير المرجح إمكانية موازاة حساب القاسم المشترك الأكبر بكفاءة. أظهر شالكروس وآخرون أن مسألة ذات صلة (EUGCD، تحديد متتالية الباقي الناتجة أثناء خوارزمية إقليدس) مكافئة من فئة NC لمسألة البرمجة الخطية الصحيحة بمتغيرين؛ فإذا كانت أي من المسألتين تنتمي إلى فئة NC أو كانت كاملة من فئة P ، فإن الأخرى كذلك. ^{[ 19 ]} وبما أن فئة NC تحتوي على فئة NL ، فإنه من غير المعروف أيضًا ما إذا كانت هناك خوارزمية فعالة من حيث المساحة لحساب القاسم المشترك الأكبر، حتى بالنسبة لآلات تورينج غير الحتمية.

على الرغم من أن المشكلة غير معروفة بأنها تقع ضمن نطاق NC ، إلا أن هناك خوارزميات متوازية أسرع تقاربياً من خوارزمية إقليدس؛ وأسرع خوارزمية حتمية معروفة هي خوارزمية تشور وغولدريتش ، والتي (في نموذج CRCW-PRAM ) يمكنها حل المشكلة في زمن $O$ $($ $n$ $/log$ $n$ $)$ باستخدام $n1$ $+$ $ε$ معالج. ^[²⁰^] ويمكن للخوارزميات العشوائية حل المشكلة في زمن $O$ $((log$ $n$ $)$ $2$ $)$ على $O\left(e^{\sqrt {n\log n}}\right)$ المعالجات (هذه متعددة الحدود الفائقة ). ^{[ 21 ]}

ملكيات

لكل عدد صحيح موجب $a$ ، $فإن القاسم المشترك الأكبر (a ، a) = a$ .
كل قاسم مشترك لـ $a$ و $b$ هو قاسم لـ $gcd(a, b)$ .
$يمكن تعريف القاسم المشترك الأكبر (gcd(a, b))$ ، حيث لا يساوي كل من a و b الصفر، بشكل بديل ومكافئ على أنه أصغر عدد صحيح موجب d يمكن كتابته على الصورة $d = a \cdot p + b \cdot q$ ، حيث p و q عددان صحيحان. تُسمى هذه الصيغة متطابقة بيزو . ويمكن حساب الأعداد p و q بهذه الصيغة باستخدام خوارزمية إقليدس الموسعة .
$القاسم المشترك الأكبر (أ ، 0) = | أ |$ ، وذلك عندما $يكون أ \neq 0$ ، لأن أي عدد هو قاسم للصفر، وأكبر قاسم لـ أ هو $| أ |$ . ^{[ 2 ]}^{[ 5 ]} وعادةً ما تُستخدم هذه الحالة كحالة أساسية في خوارزمية إقليدس.
إذا كان a يقسم حاصل ضرب b ⋅ c ، وكان $gcd(a, b) = d$ ، فإن a / d يقسم c .
إذا كان m عددًا صحيحًا موجبًا، فإن $gcd(m \cdot a, m \cdot b) = m \cdotgcd(a, b)$ .
إذا كان m أي عدد صحيح، فإن $القاسم المشترك الأكبر (a + m \cdot b, b) = القاسم المشترك الأكبر (a, b)$ . وبالمثل، $فإن القاسم المشترك الأكبر (a mod b, b) = القاسم المشترك الأكبر (a, b)$ .
إذا كان m قاسمًا مشتركًا موجبًا لـ a و b ، فإن $gcd(a / m, b / m) = gcd(a, b)/ m$ .
إذا كان $القاسم المشترك الأكبر (أ ، ب) = د$ ، فإن $القاسم المشترك الأكبر (أ / د ، ب / د) = 1$ .
القاسم المشترك الأكبر هو دالة تبديلية : $gcd(a, b) = gcd(b, a)$ .
القاسم المشترك الأكبر هو دالة تجميعية : $gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)$ . وبالتالي، يمكن استخدام $gcd(a, b, c, ...)$ للدلالة على القاسم المشترك الأكبر لعدة وسائط.
القاسم المشترك الأكبر هو دالة ضربية بالمعنى التالي: إذا كان a ₁ و a ₂ أوليين فيما بينهما، فإن $gcd(a 1 \cdot a 2, b) = gcd(a 1, b)\cdotgcd(a 2, b)$ .
يرتبط القاسم المشترك الأكبر $(gcd($ $a$ $,$ $b$ $)) ارتباطًا وثيقًا$ بالمضاعف المشترك الأصغر $(lcm(a, b))$ : لدينا
$gcd(a, b)\cdotlcm(a, b) = | أ \cdot ب |$ .

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

تنطبق الصيغ التالية من خاصية التوزيع :
$gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))$
$lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))$ .
$إذا$ $كان$ لدينا التحليلان $الوحيدان$ $للعوامل$ $الأولية$ $للعددين$ $a = p₁e₁p₂e₂ \cdot\cdot\cdotpm eₘ$ و $b = p₁f₁p₂f₂ \cdot\cdot\cdotpm fₘ$ حيث $eᵢ \geq 0$ و $fᵢ$ $\geq$ $0$ $،$ $فإن$ القاسم $المشترك$ $الأكبر$ للعددين a $و$ $b$ هو $$ $$ $$ $$ $$ $$ $$ $$
$gcd(a, b) = p 1 min(e 1, f 1) p 2 min(e 2, f 2) \cdot\cdot\cdot p m min(e m, f m)$ .
من المفيد أحيانًا تعريف $القاسم المشترك الأكبر (gcd(0, 0)) = 0$ والمضاعف $المشترك الأصغر (lcm(0, 0)) = 0،$ لأنه عندئذٍ تُصبح الأعداد الطبيعية شبكة توزيعية كاملة ، حيث يُمثل القاسم المشترك الأكبر عملية التقاطع والمضاعف المشترك الأصغر عملية الربط. ^[²²^] هذا التوسع في التعريف متوافق أيضًا مع التعميم الخاص بالحلقات التبديلية المذكور أدناه.
في نظام الإحداثيات الديكارتية ، يمكن تفسير $gcd(a, b)$ على أنه عدد القطع المستقيمة بين النقاط ذات الإحداثيات الصحيحة على القطعة المستقيمة التي تربط النقطتين $(0, 0)$ و $(a, b)$ .
بالنسبة للأعداد الصحيحة غير السالبة $a$ و $b$ ، حيث لا يكون $a$ و $b$ كلاهما صفرًا ، يمكن إثبات ذلك من خلال النظر في خوارزمية إقليدس في الأساس n : ^[²³^]
$gcd(n a - 1, n b - 1) = n gcd(a, b) - 1$ .
متطابقة تتضمن دالة أويلر :
$\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$
دالة جمع القاسم المشترك الأكبر (دالة بيلاي الحسابية):

$\sum _{k=1}^{n}\gcd(k,n)=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)=n\sum _{d|n}{\frac {\varphi (d)}{d}}=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)$ أين $\nu _{p}(n)$ هو التقييم $p$ -adic. (التسلسل A018804 في OEIS )

الاحتمالات والقيمة المتوقعة

في عام 1972، أثبت جيمس إي. نيمان أن $k$ عددًا صحيحًا، يتم اختيارها بشكل مستقل ومنتظم من المجموعة ${1، ...، n}$ ، تكون أولية فيما بينها باحتمال $1/ ζ (k)$ عندما يؤول $n$ إلى اللانهاية، حيث تشير $ζ$ إلى دالة زيتا لريمان . ^{[ 24 ]} (انظر الأعداد الأولية فيما بينها للاطلاع على الاشتقاق). وقد تم توسيع هذه النتيجة في عام 1987 لإثبات أن احتمال أن يكون لـ $k$ عددًا صحيحًا عشوائيًا قاسم مشترك أكبر $d$ هو $d - k /ζ(k)$ . ^{[ 25 ]}

باستخدام هذه المعلومات، يمكن ملاحظة (بشكل غير رسمي) أن القيمة المتوقعة لدالة القاسم المشترك الأكبر غير موجودة عندما $k = 2.$ في هذه الحالة، يكون احتمال أن يكون القاسم المشترك الأكبر مساويًا لـ $d$ هو $d - 2 / ζ (2)$ ، وبالتالي لدينا

\mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d(d^{-2}/\zeta (2))={\frac {1}{\zeta (2)}}\sum _{d=1}^{\infty }{\frac {1}{d}}.

هذا المجموع الأخير هو المتسلسلة التوافقية ، وهي متسلسلة متباعدة. ومع ذلك، عندما يكون $k \geq 3$ ، تكون القيمة المتوقعة محددة جيدًا، وبناءً على الحجة السابقة، فإنها

\mathrm {E} (k)=\sum _{d=1}^{\infty }d^{1-k}\zeta (k)^{-1}={\frac {\zeta (k-1)}{\zeta (k)}}.

بالنسبة لـ $k = 3$ ، فإن هذا يساوي تقريبًا 1.3684. أما بالنسبة لـ $k = 4$ ، فإنه يساوي تقريبًا 1.1106.

في الحلقات التبادلية

يمكن تعريف مفهوم القاسم المشترك الأكبر بشكل أعم لعناصر حلقة تبديلية عشوائية ، على الرغم من أنه ليس بالضرورة أن يوجد قاسم مشترك أكبر لكل زوج من العناصر. ^{[ 26 ]}

إذا كانت $R$ حلقة تبديلية، وكان $a$ و $b$ في $R$ ، فإن العنصر $d$ من $R$ يسمى قاسمًا مشتركًا لـ $a$ و $b$ إذا كان يقسم كلاً من $a$ و $b$ (أي إذا كان هناك عنصران $x$ و $y$ في $R$ بحيث يكون d · x = a و d · y = b ).
إذا كان $d$ قاسمًا مشتركًا لـ $a$ و $b$ ، وكل قاسم مشترك لـ $a$ و $b$ يقسم $d$ ، فإن $d$ يسمى القاسم المشترك الأكبر لـ $a$ و b .

وفقًا لهذا التعريف، قد يكون للعنصرين $a$ و $b$ عدة قواسم مشتركة كبرى، أو قد لا يكون لهما أي قواسم مشتركة كبرى على الإطلاق. إذا كانت $R$ مجالًا تكامليًا ، فإن أي قاسمين مشتركين كبرى للعنصرين $a$ و $b$ يجب أن يكونا عنصرين مترافقين ، لأنه بحسب التعريف يجب أن يقسم أحدهما الآخر. في الواقع، إذا وُجد قاسم مشترك كبرى، فإن أي عنصر مترافق معه هو أيضًا قاسم مشترك كبرى.

لا يُضمن وجود قاسم مشترك أكبر في أي مجال تكاملي. مع ذلك، إذا كان $R$ مجال تحليل فريد أو أي مجال آخر للقاسم المشترك الأكبر ، فإن أي عنصرين فيه يمتلكان قاسمًا مشتركًا أكبر. إذا كان R مجالًا إقليديًا تُعطى فيه القسمة الإقليدية خوارزميًا (كما هو الحال مثلًا عندما R = F[X] حيث F حقل ، $أو$ عندما يكون $R حلقة الأعداد الصحيحة الغاوسية)$ ، $فيمكن$ حساب القواسم $المشتركة$ الأكبر باستخدام صيغة من خوارزمية إقليدية تعتمد على إجراء القسمة.

فيما يلي مثال على مجال تكاملي يحتوي على عنصرين ليس لهما قاسم مشترك أكبر:

R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {-3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\,\,\right)\cdot 2.

العنصران $2$ و $1+{\sqrt {-3}}$ هما قاسمان مشتركان أعظميان (أي أن أي قاسم مشترك يكون من مضاعفات $2$ يرتبط بـ $2$ ، وينطبق الشيء نفسه على $1+{\sqrt {-3}}$ ، لكنهما غير مرتبطين، لذلك لا يوجد قاسم مشترك أكبر لـ $a$ و $b$ .

بالتوافق مع خاصية بيزو، يمكننا في أي حلقة تبديلية اعتبار مجموعة العناصر التي تأخذ الشكل $pa + qb$ ، حيث $p$ و $q$ متغيران على الحلقة. هذا هو المثالي المُوَلَّد بواسطة $a$ و $b$ ، ويُرمز إليه ببساطة $بـ (a, b)$ . في حلقة جميع مثالياتها رئيسية ( مجال مثالي رئيسي أو PID)، سيكون هذا المثالي مطابقًا لمجموعة مضاعفات عنصر حلقة ما $d$ ؛ عندئذٍ يكون $d$ قاسمًا مشتركًا أكبر لـ $a$ و $b$ . لكن المثالي $(a, b)$ قد يكون مفيدًا حتى عندما لا يوجد قاسم مشترك أكبر لـ $a$ و $b$ . (في الواقع، استخدم إرنست كومر هذا المثالي كبديل للقاسم المشترك الأكبر في معالجته لنظرية فيرما الأخيرة ، على الرغم من أنه تصوره على أنه مجموعة مضاعفات عنصر حلقة افتراضي، أو مثالي ، $d$ ، ومن هنا جاء المصطلح المتعلق بنظرية الحلقات).

انظر أيضاً

ملحوظات

1 2 لونغ (1972 ، ص 33)
1 2 3 بيتوفريزو وبيركيت (1970 ، ص 34)
↑ كيلي، دبليو. مايكل (2004). الدليل الكامل للمبتدئين في الجبر . دار بنغوين للنشر. ص 142. ISBN 978-1-59257-161-1..
↑ جونز، ألين (1999). الأعداد الصحيحة، والأعداد العشرية، والنسب المئوية، والكسور - السنة السابعة . دار باسكال للنشر. ص 16. ISBN 978-1-86441-378-6..
1 2 3 هاردي ورايت (1979 ، ص 20)
↑ بعض المؤلفين يتناولونيُستخدم مصطلح "المقام المشترك الأكبر" كمرادفلمصطلح "القاسم المشترك الأكبر". وهذا يناقض المعنى الشائع للكلمات المستخدمة، حيث يشير مصطلح "المقام " إلىالكسور، ولا يوجد مقام مشترك أكبر بين كسرين (إذا كان للكسرين نفس المقام، يتم الحصول على مقام مشترك أكبر بضرب جميع البسط والمقامات في نفسالعدد الصحيح).
↑ بارلو، بيتر ؛ بيكوك، جورج ؛ لاردنر، ديونيسيوس ؛ إيري، السير جورج بيدل ؛ هاميلتون، إتش بي ؛ ليفي، أ.؛ دي مورغان، أوغسطس ؛ موسلي، هنري (1847). موسوعة الرياضيات البحتة . آر. غريفين وشركاه. ص 589. .
↑ يستخدم بعض المؤلفين الرمز $(أ ، ب)$ ،^{[ 1 ]}^{[ 2 ]}^{[ 5 ]،} لكن هذا الرمز غالبًا ما يكون غامضًا. يوضح أندروز (1994 ، ص 16) ذلك قائلًا: "يكتب العديد من المؤلفين $(أ ، ب)$ للدلالة $على القاسم المشترك الأكبر (أ ، ب)$ . نحن لا نستخدمه، لأننا سنستخدم $(أ ، ب)$ غالبًا لتمثيل نقطة في المستوى الإقليدي."
↑ توماس هـ. كورمن وآخرون ، مقدمة في الخوارزميات (الطبعة الثانية، 2001) ISBN 0262032937، ص 852
↑ برنارد ل. جونستون، فريد ريتشمان، الأعداد والتناظر: مقدمة في الجبر ISBN 084930301X، ص 38
↑ مارتن ر. ديكسون وآخرون ، مقدمة في البنى الجبرية الأساسية ، رقم ISBN 1118497759، ص 59
↑ على سبيل المثال، حساب Wolfram Alpha و Maxima
↑ جوناثان كاتز، يهودا ليندل، مقدمة في التشفير الحديث ISBN 1351133012، 2020، القسم 9.1.1، صفحة 45
↑ وايسشتاين، إريك دبليو. "القاسم المشترك الأكبر" . mathworld.wolfram.com . تم الاطلاع عليه بتاريخ 30 أغسطس 2020 .
↑ "القاسم المشترك الأكبر" . www.mathsisfun.com . تم الاطلاع عليه بتاريخ 30 أغسطس 2020 .
↑ سلافين، كيث ر. (2008). "الحدود الثنائية من النوع Q والقاسم المشترك الأكبر" . الأعداد الصحيحة: المجلة الإلكترونية لنظرية الأعداد التوافقية . 8. جامعة غرب جورجيا ، جامعة تشارلز في براغ : A5 . تاريخ الاسترجاع : 26-05-2008 .
↑ شرام، وولفغانغ (2008). "تحويل فورييه لدوال القاسم المشترك الأكبر" . الأعداد الصحيحة: المجلة الإلكترونية لنظرية الأعداد التوافقية . 8. جامعة غرب جورجيا ، جامعة تشارلز في براغ : A50 . تاريخ الاسترجاع : 25 نوفمبر 2008 .
↑ كنوت، دونالد إي. (1997). فن برمجة الحاسوب . المجلد 2: الخوارزميات شبه العددية ( الطبعة الثالثة). أديسون-ويسلي بروفيشنال. ISBN 0-201-89684-2.
↑ شالكروس، د.؛ بان، ف.؛ لين-كريز، ي. (1993). "التكافؤ غير الخطي للبرمجة الخطية العددية المستوية والقاسم المشترك الأكبر الإقليدي" (ملف PDF) . المؤتمر الرابع والثلاثون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . الصفحات 557-564 . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 5 سبتمبر 2006.
↑ تشور، ب.؛ غولدريتش، أ. (1990). "خوارزمية متوازية محسّنة لإيجاد القاسم المشترك الأكبر للأعداد الصحيحة". Algorithmica . 5 ( 1-4 ): 1-10 . doi : 10.1007/BF01840374 . S2CID 17699330 .
↑ أدلمان، إل إم؛ كومبيلا، ك. (1988). "استخدام السلاسة لتحقيق التوازي". المؤتمر السنوي العشرون لجمعية آلات الحوسبة حول نظرية الحوسبة . نيويورك. ص 528-538 . doi : 10.1145/62212.62264 . ISBN 0-89791-264-0. S2CID 9118047 .
^ مولر هويسن، فولكرت. فالتر، هانز أوتو (2012). "دوف تماري (بيرنهارد تيتلر سابقًا)". في مولر هويسن، فولكرت؛ بالو، جان مارسيل؛ ستاشف، جيم (محرران). رابطة الوجوه وشبكات تماري والهياكل ذات الصلة: تماري التذكارية Festschrift . التقدم في الرياضيات. المجلد. 299. بيركهاوزر. ص 1 – 40. ISBN 978-3-0348-0405-9.الحاشية 27، صفحة 9: "على سبيل المثال، الأعداد الطبيعية التي يكون قاسمها المشترك الأكبر ( gcd ) هو عملية التقاطع ومضاعفها المشترك الأصغر ( lcm ) هو عملية الجمع، تُحدد شبكة توزيعية كاملة." إن تضمين هذه التعريفات للصفر ضروري لهذه النتيجة: إذا تم حذف الصفر من مجموعة الأعداد الطبيعية، فإن الشبكة الناتجة لن تكون كاملة.
↑ كنوت، دونالد إي .؛ غراهام، آر إل ؛ باتاشنيك، أو. (مارس 1994). الرياضيات الملموسة: أساس لعلوم الحاسوب . أديسون-ويسلي . ISBN 0-201-55802-5.
↑ نيمان، جيه إي (1972). "حول احتمال أن تكون $k$ أعدادًا صحيحة موجبة أولية فيما بينها" . مجلة نظرية الأعداد . 4 (5): 469-473 . Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .
↑ تشيدامباراسوامي، ج.؛ سيتارماشاندرا راو، ر. (1987). "حول احتمال أن يكون لقيم m من كثيرات الحدود قاسم مشترك أكبر مُعطى". مجلة نظرية الأعداد . 26 (3): 237-245 . doi : 10.1016/0022-314X(87)90081-3 .
↑ لوفيت، ستيفن (2015). "قابلية القسمة في الحلقات التبادلية". الجبر المجرد: الهياكل والتطبيقات . بوكا راتون: مطبعة سي آر سي. ص 267-318 . ISBN 9781482248913.

مراجع

أندروز، جورج إي. (1994) [1971]. نظرية الأعداد . دوفر. ISBN 978-0-486-68252-5.
هاردي، جي إتش ؛ رايت، إي إم (1979). مدخل إلى نظرية الأعداد ( الطبعة الخامسة). أكسفورد: مطبعة جامعة أكسفورد . ISBN 978-0-19-853171-5.
لونغ، كالفن ت. (1972). مقدمة تمهيدية في نظرية الأعداد ( الطبعة الثانية). ليكسينغتون: دي سي هيث وشركاه . LCCN 77171950 .
بيتوفريزو، أنتوني جيه؛ بيركيت، دونالد آر. (1970). عناصر نظرية الأعداد . إنجلوود كليفس: برنتيس هول . LCCN 71081766 .

للمزيد من القراءة

دونالد كنوث . فن برمجة الحاسوب ، المجلد الثاني: الخوارزميات شبه العددية ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89684-2القسم 4.5.2: القاسم المشترك الأكبر، الصفحات 333-356.
توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 31.2: القاسم المشترك الأكبر، الصفحات 856-862.
ساوندرز ماك لين وغاريت بيركوف . مسح للجبر الحديث ، الطبعة الرابعة. شركة ماكميلان للنشر، 1977. ISBN 0-02-310070-21-7: "خوارزمية إقليدس".

روابط خارجية

رسم بياني للدالة gcd(x,y) = y: https://www.desmos.com/calculator/6nizzenog5

[Long_1972_33-1] 1 2 لونغ (1972 ، ص 33)

[Pettofrezzo_1970_34-2] 1 2 3 بيتوفريزو وبيركيت (1970 ، ص 34)

[3] كيلي، دبليو. مايكل (2004). الدليل الكامل للمبتدئين في الجبر . دار بنغوين للنشر. ص 142. ISBN 978-1-59257-161-1..

[4] جونز، ألين (1999). الأعداد الصحيحة، والأعداد العشرية، والنسب المئوية، والكسور - السنة السابعة . دار باسكال للنشر. ص 16. ISBN 978-1-86441-378-6..

[Hardy&Wright_1979_20-5] 1 2 3 هاردي ورايت (1979 ، ص 20)

[6] بعض المؤلفين يتناولونيُستخدم مصطلح "المقام المشترك الأكبر" كمرادفلمصطلح "القاسم المشترك الأكبر". وهذا يناقض المعنى الشائع للكلمات المستخدمة، حيث يشير مصطلح "المقام " إلىالكسور، ولا يوجد مقام مشترك أكبر بين كسرين (إذا كان للكسرين نفس المقام، يتم الحصول على مقام مشترك أكبر بضرب جميع البسط والمقامات في نفسالعدد الصحيح).

[7] بارلو، بيتر ؛ بيكوك، جورج ؛ لاردنر، ديونيسيوس ؛ إيري، السير جورج بيدل ؛ هاميلتون، إتش بي ؛ ليفي، أ.؛ دي مورغان، أوغسطس ؛ موسلي، هنري (1847). موسوعة الرياضيات البحتة . آر. غريفين وشركاه. ص 589. .

[8] يستخدم بعض المؤلفين الرمز $(أ ، ب)$ ،^{[ 1 ]}^{[ 2 ]}^{[ 5 ]،} لكن هذا الرمز غالبًا ما يكون غامضًا. يوضح أندروز (1994 ، ص 16) ذلك قائلًا: "يكتب العديد من المؤلفين $(أ ، ب)$ للدلالة $على القاسم المشترك الأكبر (أ ، ب)$ . نحن لا نستخدمه، لأننا سنستخدم $(أ ، ب)$ غالبًا لتمثيل نقطة في المستوى الإقليدي."

[9] توماس هـ. كورمن وآخرون ، مقدمة في الخوارزميات (الطبعة الثانية، 2001) ISBN 0262032937، ص 852

[10] برنارد ل. جونستون، فريد ريتشمان، الأعداد والتناظر: مقدمة في الجبر ISBN 084930301X، ص 38

[11] مارتن ر. ديكسون وآخرون ، مقدمة في البنى الجبرية الأساسية ، رقم ISBN 1118497759، ص 59

[12] على سبيل المثال، حساب Wolfram Alpha و Maxima

[13] جوناثان كاتز، يهودا ليندل، مقدمة في التشفير الحديث ISBN 1351133012، 2020، القسم 9.1.1، صفحة 45

[14] وايسشتاين، إريك دبليو. "القاسم المشترك الأكبر" . mathworld.wolfram.com . تم الاطلاع عليه بتاريخ 30 أغسطس 2020 .

[15] "القاسم المشترك الأكبر" . www.mathsisfun.com . تم الاطلاع عليه بتاريخ 30 أغسطس 2020 .

[16] سلافين، كيث ر. (2008). "الحدود الثنائية من النوع Q والقاسم المشترك الأكبر" . الأعداد الصحيحة: المجلة الإلكترونية لنظرية الأعداد التوافقية . 8. جامعة غرب جورجيا ، جامعة تشارلز في براغ : A5 . تاريخ الاسترجاع : 26-05-2008 .

[17] شرام، وولفغانغ (2008). "تحويل فورييه لدوال القاسم المشترك الأكبر" . الأعداد الصحيحة: المجلة الإلكترونية لنظرية الأعداد التوافقية . 8. جامعة غرب جورجيا ، جامعة تشارلز في براغ : A50 . تاريخ الاسترجاع : 25 نوفمبر 2008 .

[18] كنوت، دونالد إي. (1997). فن برمجة الحاسوب . المجلد 2: الخوارزميات شبه العددية ( الطبعة الثالثة). أديسون-ويسلي بروفيشنال. ISBN 0-201-89684-2.

[19] شالكروس، د.؛ بان، ف.؛ لين-كريز، ي. (1993). "التكافؤ غير الخطي للبرمجة الخطية العددية المستوية والقاسم المشترك الأكبر الإقليدي" (ملف PDF) . المؤتمر الرابع والثلاثون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . الصفحات 557-564 . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 5 سبتمبر 2006.

[20] تشور، ب.؛ غولدريتش، أ. (1990). "خوارزمية متوازية محسّنة لإيجاد القاسم المشترك الأكبر للأعداد الصحيحة". Algorithmica . 5 ( 1-4 ): 1-10 . doi : 10.1007/BF01840374 . S2CID 17699330 .

[21] أدلمان، إل إم؛ كومبيلا، ك. (1988). "استخدام السلاسة لتحقيق التوازي". المؤتمر السنوي العشرون لجمعية آلات الحوسبة حول نظرية الحوسبة . نيويورك. ص 528-538 . doi : 10.1145/62212.62264 . ISBN 0-89791-264-0. S2CID 9118047 .

[22] مولر هويسن، فولكرت. فالتر، هانز أوتو (2012). "دوف تماري (بيرنهارد تيتلر سابقًا)". في مولر هويسن، فولكرت؛ بالو، جان مارسيل؛ ستاشف، جيم (محرران). رابطة الوجوه وشبكات تماري والهياكل ذات الصلة: تماري التذكارية Festschrift . التقدم في الرياضيات. المجلد. 299. بيركهاوزر. ص 1 – 40. ISBN 978-3-0348-0405-9.الحاشية 27، صفحة 9: "على سبيل المثال، الأعداد الطبيعية التي يكون قاسمها المشترك الأكبر ( gcd ) هو عملية التقاطع ومضاعفها المشترك الأصغر ( lcm ) هو عملية الجمع، تُحدد شبكة توزيعية كاملة." إن تضمين هذه التعريفات للصفر ضروري لهذه النتيجة: إذا تم حذف الصفر من مجموعة الأعداد الطبيعية، فإن الشبكة الناتجة لن تكون كاملة.

[23] كنوت، دونالد إي .؛ غراهام، آر إل ؛ باتاشنيك، أو. (مارس 1994). الرياضيات الملموسة: أساس لعلوم الحاسوب . أديسون-ويسلي . ISBN 0-201-55802-5.

[nymann-24] نيمان، جيه إي (1972). "حول احتمال أن تكون $k$ أعدادًا صحيحة موجبة أولية فيما بينها" . مجلة نظرية الأعداد . 4 (5): 469-473 . Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .

[chid-25] تشيدامباراسوامي، ج.؛ سيتارماشاندرا راو، ر. (1987). "حول احتمال أن يكون لقيم m من كثيرات الحدود قاسم مشترك أكبر مُعطى". مجلة نظرية الأعداد . 26 (3): 237-245 . doi : 10.1016/0022-314X(87)90081-3 .

[26] لوفيت، ستيفن (2015). "قابلية القسمة في الحلقات التبادلية". الجبر المجرد: الهياكل والتطبيقات . بوكا راتون: مطبعة سي آر سي. ص 267-318 . ISBN 9781482248913.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

أنظمة الجبر الحاسوبي

هذا الاصطلاح .

[ 12 ]

يترك بعض المؤلفين

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[

[ 21 ]

[

[

[ 24 ]

[ 25 ]

[ 26 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗