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

في نظرية الأعداد ، يُقال عن عددين صحيحين a و b أنهما أوليان فيما بينهما أو أوليان متبادلان إذا كان العدد الصحيح الموجب الوحيد الذي يقسمهما معًا هو 1. ^{[ 1 ]} وبالتالي، فإن أي عدد أولي يقسم a لا يقسم b ، والعكس صحيح. وهذا يُكافئ أن يكون قاسمهما المشترك الأكبر (GCD) هو 1. ^{[ 2 ]} ويُقال أيضًا أن a أولي بالنسبة إلى b أو أن a أولي نسبيًا مع b .

العددان 8 و9 أوليان فيما بينهما، على الرغم من أن أياً منهما - عند النظر إليه بشكل منفرد - ليس عدداً أولياً، لأن 1 هو قاسمهما المشترك الوحيد. من ناحية أخرى، فإن 6 و9 ليسا أوليان فيما بينهما، لأنهما يقبلان القسمة على 3. بسط ومقام الكسر المختزل أوليان فيما بينهما، بحسب التعريف.

عندما يكون العددان الصحيحان a و b أوليين فيما بينهما، فإن الطريقة القياسية للتعبير عن هذه الحقيقة في الترميز الرياضي هي الإشارة إلى أن قاسمهما المشترك الأكبر هو واحد، وذلك باستخدام الصيغة gcd( a , b ) = 1 أو ( a , b ) = 1. في كتابهم المدرسي " الرياضيات الملموسة" الصادر عام 1989 ، اقترح رونالد غراهام ودونالد كنوث وأورين باتاشنيك ترميزًا بديلًا .${\displaystyle a\perp b}$للإشارة إلى أن a و b عددان أوليان فيما بينهما، وأن مصطلح "أولي" يُستخدم بدلاً من "أولي نسبيًا" (كما في a أولي بالنسبة إلى b ). ^{[ 3 ]}

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

عدد الأعداد الصحيحة الأولية فيما بينها مع عدد صحيح موجب n ، بين 1 و n ، يتم إعطاؤه بواسطة دالة أويلر ، والمعروفة أيضًا باسم دالة أويلر فاي، φ ( n ) .

يمكن تسمية مجموعة من الأعداد الصحيحة بالأعداد الأولية فيما بينها إذا لم يكن لأي من عناصرها عامل موجب مشترك سوى 1. وهناك شرط أقوى على مجموعة من الأعداد الصحيحة وهو الأعداد الأولية فيما بينها، أي أن a و b عددان أوليان فيما بينهما لكل زوج ( a , b ) من أعداد صحيحة مختلفة في المجموعة. فالمجموعة {2, 3, 4} هي مجموعة أولية فيما بينها، ولكنها ليست أولية فيما بينها لأن 2 و 4 ليسا أوليين نسبيًا.

العددان 1 و -1 هما العددان الصحيحان الوحيدان اللذان يكونان أوليين فيما بينهما مع كل عدد صحيح، وهما العددان الصحيحان الوحيدان اللذان يكونان أوليين فيما بينهما مع 0.

عدد من الشروط تعادل كون a و b عددين أوليين فيما بينهما:

• لا يوجد عدد أولي يقسم كلاً من a و b .
• يوجد عددان صحيحان x و y بحيث يكون ax + by = 1 (انظر متطابقة بيزو ).
• للعدد الصحيح b معكوس ضربي بتردد a ، مما يعني أنه يوجد عدد صحيح y بحيث يكون b ≡ 1 (mod a ) . بلغة نظرية الحلقات، b هو عنصر محايد في الحلقة .${\displaystyle \mathbb {Z} /a\mathbb {Z} }$من الأعداد الصحيحة modulo a .
• كل زوج من علاقات التطابق لعدد صحيح غير معروف x ، من الشكل x ≡ k (mod a ) و x ≡ m (mod b ) ، له حل ( نظرية الباقي الصينية )؛ في الواقع يتم وصف الحلول بعلاقة تطابق واحدة modulo ab .
• المضاعف المشترك الأصغر لـ a و b يساوي حاصل ضربهما ab ، أي lcm( a , b ) = ab . ^{[ 4 ]}

نتيجةً للنقطة الثالثة، إذا كان a و b عددين أوليين فيما بينهما، وكان br ≡ bs (mod a ) ، فإن r ≡ s (mod a). [5] أي أنه يجوز لنا "القسمة على b" عند العمل بتردد a. علاوة على ذلك، إذا كان b1 و b2 أوليين فيما بينهما مع a، فإن حاصل ضربهما b1 b2 أوليٌّ أيضًا ( ^{أي أنه بتردد} a يكون حاصل ضرب _عناصر قابلة _للعكس ، وبالتالي قابل للعكس ) ؛ [ _{6 ]} وهذا يتبع أيضًا ^{من النقطة الأولى} من خلال مبرهنة إقليدس ، التي تنص على أنه إذا كان عدد أولي p يقسم حاصل ضرب bc ، فإن p يقسم على الأقل أحد العاملين b أو c .

ونتيجة للنقطة الأولى، إذا كان a و b أوليين فيما بينهما، فإن أي قوتين a ^k و b ^m تكونان أوليتين أيضاً .

إذا كان a و b أوليين فيما بينهما وكان a يقسم حاصل ضرب bc ، فإن a يقسم c . ^{[ 7 ]} يمكن اعتبار هذا تعميمًا لـ "ليما إقليدس".

يكون العددان الصحيحان a و b أوليين فيما بينهما إذا وفقط إذا كانت النقطة ذات الإحداثيات ( a , b ) في نظام الإحداثيات الديكارتية "مرئية" عبر خط رؤية غير محجوب من نقطة الأصل (0, 0) ، بمعنى أنه لا توجد نقطة ذات إحداثيات صحيحة في أي مكان على القطعة المستقيمة بين نقطة الأصل والنقطة ( a , b ) . (انظر الشكل 1).

بمعنى يمكن تحديده بدقة، فإن احتمال أن يكون عددان صحيحان تم اختيارهما عشوائيا أوليين فيما بينهما هو 6/ π2 ^، وهو ما يقارب 61% (انظر §  احتمالية الأولية المشتركة ، أدناه).

يكون العددان الطبيعيان a و b أوليين فيما بينهما إذا وفقط إذا كان العددان 2a ^- 1 و 2b ^- 1 أوليين فيما بينهما. ^{[ 8 ]} وكتعميم لهذا، يمكن استنتاجه بسهولة من خوارزمية إقليدس في الأساس n > 1 :

${\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}$

مجموعة من الأعداد الصحيحة${\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}$يمكن أيضًا تسميتها بأعداد أولية فيما بينها أو أعداد أولية فيما بينها على مستوى المجموعة إذا كان القاسم المشترك الأكبر لجميع عناصر المجموعة هو 1. على سبيل المثال، الأعداد الصحيحة 6 و10 و15 هي أعداد أولية فيما بينها لأن 1 هو العدد الصحيح الموجب الوحيد الذي يقسمها جميعًا.

إذا كان كل زوج من الأعداد الصحيحة في مجموعة ما أوليًا فيما بينه، فإن المجموعة تُسمى أولية فيما بينها (أو أولية نسبيًا فيما بينها ، أو أولية متبادلة ، أو أولية متبادلة ). وتُعدّ أولية الأزواج شرطًا أقوى من أولية المجموعات؛ فكل مجموعة منتهية أولية فيما بينها هي أيضًا أولية فيما بينها، ولكن العكس غير صحيح. على سبيل المثال، الأعداد الصحيحة 4 و5 و6 أولية فيما بينها (لأن العدد الصحيح الموجب الوحيد الذي يقسمها جميعًا هو 1)، ولكنها ليست أولية فيما بينها (لأن القاسم المشترك الأكبر لـ 4 و6 هو 2 ).

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

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

بفرض اختيار عددين صحيحين عشوائيين a و b ، فمن المنطقي التساؤل عن احتمالية أن يكون a و b أوليين فيما بينهما. في هذا التحديد، من المفيد استخدام خاصية أن a و b أوليان فيما بينهما إذا وفقط إذا لم يقسمهما أي عدد أولي (انظر النظرية الأساسية للحساب ).

بصورة غير رسمية، فإن احتمال أن يكون أي عدد قابلاً للقسمة على عدد أولي (أو في الواقع أي عدد صحيح) p هو ⁠${\displaystyle {\tfrac {1}{p}};}$على سبيل المثال ، كل عدد صحيح سابع يقبل القسمة على 7. وبالتالي فإن احتمال أن يكون عددان كلاهما يقبل القسمة على p هو${\displaystyle {\tfrac {1}{p^{2}}},}$واحتمالية أن يكون واحد منهم على الأقل ليس كذلك هي${\displaystyle 1-{\tfrac {1}{p^{2}}}.}$أي مجموعة منتهية من أحداث قابلية القسمة المرتبطة بأعداد أولية مختلفة تكون مستقلة عن بعضها البعض. على سبيل المثال، في حالة حدثين، يكون العدد قابلاً للقسمة على العددين الأوليين p و q إذا وفقط إذا كان قابلاً للقسمة على pq ؛ احتمال الحدث الأخير هو ⁠${\displaystyle {\tfrac {1}{pq}}.}$إذا افترضنا بشكل استدلالي أن هذا المنطق يمكن تعميمه على عدد لا نهائي من حالات قابلية القسمة، فسنصل إلى تخمين أن احتمال كون عددين أوليين فيما بينهما يُعطى بضرب جميع الأعداد الأولية.

${\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}$

هنا يشير ζ إلى دالة زيتا لريمان ، والهوية التي تربط الضرب على الأعداد الأولية بـ ζ (2) هي مثال على ضرب أويلر ، وتقييم ζ (2) على أنه π ² /6 هو مسألة بازل ، التي حلها ليونارد أويلر في عام 1735.

لا توجد طريقة لاختيار عدد صحيح موجب عشوائيًا بحيث يظهر كل عدد صحيح موجب باحتمالية متساوية، ولكن يمكن صياغة عبارات حول "الأعداد الصحيحة المختارة عشوائيًا" مثل تلك المذكورة أعلاه باستخدام مفهوم الكثافة الطبيعية . لكل عدد صحيح موجب N ، ليكن P_{_N} احتمال ظهور عددين مختارين عشوائيًا في${\displaystyle \{1,2,\ldots ,N\}}$هي أعداد أولية فيما بينها. على الرغم من أن ^P N _لن تساوي أبدًا 6/ π² ^بالضبط ، إلا أنه ^{يمكن إثبات} ذلك في النهاية عندما${\displaystyle N\to \infty ,}$يقترب احتمال P _N من 6/ π ² .

وبشكل أعم، فإن احتمال أن تكون k أعداد صحيحة مختارة عشوائياً أولية فيما بينها هو${\displaystyle {\tfrac {1}{\zeta (k)}}.}$[ ^{9 ]​}

يمكن ترتيب جميع أزواج الأعداد الأولية الموجبة فيما بينها ( m , n ) (حيث m > n ) في شجرتين ثلاثيتين كاملتين منفصلتين ، تبدأ إحداهما من (2, 1) (للأزواج الزوجية-الفردية والفردية-الزوجية)، ^{[ 10 ]} وتبدأ الأخرى من (3, 1) (للأزواج الفردية-الفردية). ^{[ 11 ]} يتم توليد أبناء كل رأس ( m , n ) كما يلي:

• الفرع 1:${\displaystyle (2m-n,m)}$
• الفرع 2:${\displaystyle (2m+n,m)}$
• الفرع 3:${\displaystyle (m+2n,n)}$

هذا المخطط شامل وغير زائد عن الحاجة، ولا يحتوي على عناصر غير صالحة. ويمكن إثبات ذلك من خلال ملاحظة أنه إذا${\displaystyle (a,b)}$هو زوج أولي فيما بينه${\displaystyle a>b,}$ثم

• لو${\displaystyle a>3b,}$ثم ${\displaystyle (a,b)}$هو ابن${\displaystyle (m,n)=(a-2b,b)}$على طول الفرع 3؛
• لو${\displaystyle 2b<a<3b,}$ثم${\displaystyle (a,b)}$هو ابن${\displaystyle (m,n)=(b,a-2b)}$على طول الفرع 2؛
• لو${\displaystyle b<a<2b,}$ثم${\displaystyle (a,b)}$هو ابن${\displaystyle (m,n)=(b,2b-a)}$على طول الفرع 1.

في جميع الحالات${\displaystyle (m,n)}$هو زوج أولي "أصغر" مع${\displaystyle m>n.}$لا يمكن إيقاف عملية "حساب الأب" إلا إذا${\displaystyle a=2b}$أو${\displaystyle a=3b.}$في هذه الحالات، تعني خاصية الأسبقية المشتركة أن الزوج إما${\displaystyle (2,1)}$أو${\displaystyle (3,1).}$

هناك طريقة أخرى (أبسط بكثير) لتوليد شجرة من أزواج الأعداد الأولية الموجبة ( m , n ) (حيث m > n ) وهي باستخدام مولدين.${\displaystyle f:(m,n)\rightarrow (m+n,n)}$و${\displaystyle g:(m,n)\rightarrow (m+n,m)}$، بدءًا من الجذر${\displaystyle (2,1)}$الشجرة الثنائية الناتجة ، وهي شجرة كالكين-ويلف ، شاملة وغير زائدة، ويمكن توضيح ذلك كما يلي: عند إعطاء زوج من الأعداد الأولية فيما بينها، يتم تطبيق...${\displaystyle f^{-1}}$أو${\displaystyle g^{-1}}$يعتمد ذلك على أيٍّ منهما يُنتج زوجًا أوليًا موجبًا حيث m > n . بما أن واحدًا فقط يُنتج زوجًا أوليًا موجبًا حيث m > n، فإن الشجرة غير زائدة. وبما أن هذه العملية ستؤدي حتمًا إلى الوصول إلى الجذر، فإن الشجرة شاملة.

في تصميم الآلات، يُحقق تآكل متساوٍ ومنتظم للتروس باختيار عدد أسنان الترسين المتشابكين بحيث يكون عدد أسنانهما أكبر من عدد أسنان الترسين الآخرين. عند الرغبة في نسبة تروس 1:1 ، يُمكن إدخال ترس أكبر من عدد أسنان الترسين المتساويين في الحجم بينهما.

في علم التشفير قبل عصر الحاسوب ، كانت بعض آلات تشفير فيرنام تجمع بين عدة حلقات من شريط المفاتيح بأطوال مختلفة. وتجمع العديد من آلات الدوار بين دوارات ذات أعداد مختلفة من الأسنان. وتعمل هذه التركيبات على أفضل وجه عندما تكون جميع الأطوال أعدادًا أولية فيما بينها. ^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]}

يمكن توسيع هذا المفهوم ليشمل هياكل جبرية أخرى غير ⁠${\displaystyle \mathbb {Z}$ ;} على سبيل المثال،تسمىكثيرات الحدودالتييكون قاسمها المشترك الأكبركثيرات الحدود الأولية فيما بينها.

• بستان إقليدس
• عدد الأجزاء الفائقة

• هاردي، جي إتش ؛ رايت، إي إم (2008)، مقدمة في نظرية الأعداد (  الطبعة السادسة)، مطبعة جامعة أكسفورد ، رقم ISBN 978-0-19-921986-5
• نيفن، إيفان؛ زوكرمان، هربرت س. (1966)، مقدمة في نظرية الأعداد (  الطبعة الثانية)، جون وايلي وأولاده
• أور، أويستين (1988) [1948]، نظرية الأعداد وتاريخها ، دوفر، ISBN 978-0-486-65620-5
• روزن، كينيث هـ. (1992)، نظرية الأعداد الأولية وتطبيقاتها (  الطبعة الثالثة)، أديسون-ويسلي، رقم ISBN 978-0-201-57889-8

• لورد، نيك (مارس 2008)، "بناء موحد لبعض المتتاليات اللانهائية الأولية فيما بينها"، المجلة الرياضية ، 92 : 66-70.