الأعداد الصحيحة الأولية

في نظرية الأعداد ، يكون عددان صحيحان 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. في كتابهم المدرسي Concrete Mathematics لعام 1989 ، اقترح رونالد جراهام ودونالد كنوث وأورين باتاشنيك صيغة بديلة للإشارة إلى أن a و b عددان أوليان نسبيًا وأن مصطلح "أولي" يجب استخدامه بدلاً من العدد الأولي المشترك (كما في a هو عدد أولي بالنسبة إلى b ). ^[3]${\displaystyle a\perp b}$

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

عدد الأعداد الصحيحة الأولية ذات العدد الصحيح الموجب 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 له معكوس مضاعف modulo a ، مما يعني أنه يوجد عدد صحيح y بحيث يكون by ≡ 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 ، أي المضاعف المشترك الأصغر ( a ، b ) = ab . ^[4]

كنتيجة للنقطة الثالثة، إذا كان a و b عددين أوليين مشتركين و br ≡ bs (mod a ) ، فإن r ≡ s (mod a ) . ^[5] وهذا يعني أنه يمكننا "القسمة على b " عند العمل بمعامل a . وعلاوة على ذلك، إذا كان كل من b ₁ و b ₂ عددين أوليين مشتركين مع a ، فإن حاصل ضربهما b ₁ b ₂ يكون كذلك (أي بمعامل 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/ π ² ، وهو ما يعادل حوالي 61% (انظر § احتمالية الأولية المتماثلة، أدناه).

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

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

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

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

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

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

يُطلق على المثاليتين A و B في حلقة تبادلية R اسم المثاليتين الأوليتين المشتركتين (أو المثاليتين المشتركتين ) إذا كان هذا يعمم متطابقة بيزوت : وفقًا لهذا التعريف، يكون المثاليان الرئيسيان ( a ) و( b ) في حلقة الأعداد الصحيحة مثاليتين مشتركتين إذا وفقط إذا كان a و b مثاليتين مشتركتين. إذا كانت المثاليتان A و B في R مثاليتين مشتركتين، فبالإضافة إلى ذلك، إذا كانت C مثالية ثالثة بحيث تحتوي A على BC ، فإن A تحتوي على C. يمكن تعميم نظرية الباقي الصيني على أي حلقة تبادلية، باستخدام المثاليات المشتركة. ${\displaystyle A+B=R.}$${\displaystyle \mathbb {Z} }$${\displaystyle AB=A\cap B;}$

إذا تم اختيار عددين صحيحين عشوائيًا 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 يكون احتمال أن يكون رقمان مختاران عشوائيًا في أوليين مشتركين. على الرغم من أن P _N لن يساوي أبدًا 6/ π ² تمامًا، فمن خلال العمل ^[9] يمكن للمرء أن يُظهر أنه في الحد حيث يقترب الاحتمال P _N من 6/ π ² . ${\displaystyle \{1,2,\ldots ,N\}}$${\displaystyle N\to \infty ,}$

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

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

• الفرع الأول:${\displaystyle (2م-ن،م)}$
• الفرع الثاني:${\displaystyle (2م+ن،م)}$
• الفرع الثالث:${\displaystyle (م+2ن،ن)}$

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

• إذا كان إذن طفلًا من الفرع 3؛${\displaystyle a>3b,}$${\displaystyle (أ،ب)}$${\displaystyle (م، ن)=(أ-2ب، ب)}$
• إذا كان طفلًا من الفرع 2؛${\displaystyle 2b<a<3b,}$${\displaystyle (أ،ب)}$${\displaystyle (م،ن)=(ب،أ-2ب)}$
• إذا كان إذن طفلًا للفرع 1.${\displaystyle b<a<2b,}$${\displaystyle (أ،ب)}$${\displaystyle (م،ن)=(ب،2ب-أ)}$

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

هناك طريقة أخرى (أبسط كثيرًا) لتوليد شجرة من أزواج الأعداد الأولية الموجبة ( m ، n ) (حيث 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}}$

في تصميم الماكينة، يتم تحقيق تآكل متساوي وموحد للتروس من خلال اختيار عدد أسنان الترسين المتداخلين معًا ليكونا أساسيين نسبيًا. عندما تكون نسبة التروس 1:1 مطلوبة، يمكن إدخال ترس أساسي نسبيًا لترسين متساويين الحجم بينهما.

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

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

• بستان إقليدس
• عدد مضاعف

• هاردي، جي إتش ؛ رايت، إي إم (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.