معيار أويلر

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 39 صور
الموسوعة الحرة

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

ليكن p عددًا أوليًا فرديًا ، وليكن a عددًا صحيحًا أوليًا نسبيًا مع p . عندئذٍ [ 1 ] [ 2 ] [ 3 ]

أص-12≡{1(تعديلص) إذا كان هناك عدد صحيح x بحيث x2≡أ(تعديلص)،-1(تعديلص) إذا لم يكن هناك عدد صحيح بهذا الاسم.{\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ إذا كان هناك عدد صحيح }}x{\text{ بحيث }}x^{2}\equiv a{\pmod {p}},\\-1{\pmod {p}}&{\text{ إذا لم يكن هناك عدد صحيح كهذا.}}\end{cases}}}

يمكن إعادة صياغة معيار أويلر بإيجاز باستخدام رمز ليجندر : [ 4 ]

(أص)≡أص-12(تعديلص).{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}

يعود هذا المعيار إلى ورقة بحثية كتبها ليونارد أويلر عام 1748. [ 5 ] [ 6 ]

دليل

يستند البرهان إلى حقيقة أن فئات البواقي بتردد عدد أولي تُشكّل حقلاً . راجع مقالة "الحقل الأولي" لمزيد من التفاصيل.

بما أن المعامل عدد أولي، فإن نظرية لاغرانج تنطبق: لا يمكن أن يكون لكثير الحدود من الدرجة k أكثر من k جذر. على وجه الخصوص، فإن x² ≡ a (mod p ) له حلان على الأكثر لكل قيمة من a . وهذا يعني مباشرةً أنه بالإضافة إلى الصفر، يوجد على الأقل p − 1 / 2 من البواقي التربيعية المختلفة modulo p : كل قيمة من القيم الممكنة لـ x (p − 1) لا يمكن أن يصاحبها إلا قيمة واحدة أخرى تعطي نفس الباقي.

في الحقيقة،(ص-x)2≡x2(تعديلص).{\displaystyle (px)^{2}\equiv x^{2}{\pmod {p}}.}وذلك لأن(ص-x)2≡ص2-2xص+x2≡x2(تعديلص).{\displaystyle (px)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.} إذن،ص-12{\displaystyle {\tfrac {p-1}{2}}}البقايا التربيعية المتميزة هي: 12،22،...،(ص-12)2(تعديلص).{\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}

بما أن a عدد أولي نسبيًا مع p ، فإن نظرية فيرما الصغيرة تنص على أن

أص-1≡1(تعديلص)،{\displaystyle a^{p-1}\equiv 1{\pmod {p}},}

والتي يمكن كتابتها على النحو التالي

(أص-12-1)(أص-12+1)≡0(تعديلص).{\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}

بما أن الأعداد الصحيحة modulo p تشكل حقلاً، فلكل a ، يجب أن يكون أحد هذين العاملين صفراً. لذلك،

أص-12≡1(تعديلص){\displaystyle a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}}أو
أص-12≡-1(تعديلص).{\displaystyle a^{\tfrac {p-1}{2}}\equiv {-1}{\pmod {p}}.}

أما إذا كان a هو الباقي التربيعي، فإن a ≡ x² ،

أص-12≡(x2)ص-12≡xص-1≡1(تعديلص).{\displaystyle a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}

لذا فإن كل باقي تربيعي (mod p ) يجعل العامل الأول صفرًا.

بتطبيق نظرية لاغرانج مرة أخرى، نلاحظ أنه لا يمكن أن يكون هناك أكثر من ⁠ p − 1 / 2 ⁠ قيمة لـ a تجعل العامل الأول صفرًا. ولكن كما ذكرنا في البداية، يوجد على الأقل ⁠ p − 1 / 2 ⁠ من البواقي التربيعية المختلفة (mod p ) (باستثناء الصفر). لذلك، فهي تحديدًا فئات البواقي التي تجعل العامل الأول صفرًا. أما فئات البواقي الأخرى البالغ عددها ⁠ p − 1 / 2 ⁠ ، أي غير البواقي، فيجب أن تجعل العامل الثاني صفرًا، وإلا فلن تحقق نظرية فيرما الصغرى. وهذا هو معيار أويلر.

دليل بديل

يعتمد هذا البرهان فقط على حقيقة أن أي تطابقكx≡ل(تعديلص){\displaystyle kx\equiv l\!\!\!{\pmod {p}}}له قيمة فريدة (باقي القسمة)ص{\displaystyle p}) حلx{\displaystyle x}متاحص{\displaystyle p}لم ينقسمك{\displaystyle k}(هذا صحيح لأنه كماx{\displaystyle x}يتم تطبيق العملية على جميع البواقي غير الصفرية moduloص{\displaystyle p}بدون تكرار، كذلك يفعلكx{\displaystyle kx}إذا كان لديناكx1≡كx2(تعديلص){\displaystyle kx_{1}\equiv kx_{2}{\pmod {p}}}، ثمص|ك(x1-x2){\displaystyle p\mid k(x_{1}-x_{2})}، لذلكص|(x1-x2){\displaystyle p\mid (x_{1}-x_{2})}، لكنx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}ليست متطابقة moduloص{\displaystyle p}.) ويترتب على هذه الحقيقة أن جميع البواقي غير الصفرية moduloص{\displaystyle p}مربعه لا يتطابق معأ{\displaystyle a}يمكن تجميعها في أزواج غير مرتبة(x،y){\displaystyle (x,y)}وفقًا للقاعدة التي تنص على أن حاصل ضرب عناصر كل زوج متطابق معأ{\displaystyle a}moduloص{\displaystyle p}(لأن هذه الحقيقة لكلy{\displaystyle y}يمكننا أن نجد مثل هذاx{\displaystyle x}بشكل فريد، والعكس صحيح، وسيختلفان عن بعضهما البعض إذاy2{\displaystyle y^{2}}لا يتطابق معأ{\displaystyle a}). لوأ{\displaystyle a}ليس هذا باقيًا تربيعيًا، بل هو ببساطة إعادة تجميع لجميعص-1{\displaystyle p-1}البقايا غير الصفرية في(ص-1)/2{\displaystyle (p-1)/2}وبالتالي نستنتج أن1⋅2⋅...⋅(ص-1)≡أص-12(تعديلص){\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}. لوأ{\displaystyle a}إذا كان الباقي تربيعيًا، فإن اثنين من الباقي لم يكونا من بين الباقين المتطابقين.ر{\displaystyle r}و-ر{\displaystyle -r}بحيثر2≡أ(تعديلص){\displaystyle r^{2}\equiv a\!\!\!{\pmod {p}}}إذا جمعنا هذين الباقيين الغائبين معًا، فسيكون ناتجهما هو-أ{\displaystyle -a}بدلاً منأ{\displaystyle a}ومن ثم في هذه الحالة1⋅2⋅...⋅(ص-1)≡-أص-12(تعديلص){\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}باختصار، بالنظر إلى هاتين الحالتين، فقد أثبتنا أنه بالنسبة لـأ≢0(تعديلص){\displaystyle a\not \equiv 0\!\!\!{\pmod {p}}}لدينا1⋅2⋅...⋅(ص-1)≡-(أص)أص-12(تعديلص){\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}يبقى استبدالهاأ=1{\displaystyle a=1}(وهو مربع واضح) في هذه الصيغة للحصول على نظرية ويلسون ، ومعيار أويلر، و(عن طريق تربيع كلا جانبي معيار أويلر) نظرية فيرما الصغرى .

أمثلة

مثال 1: إيجاد الأعداد الأولية التي يكون فيها a باقيًا

لنفترض أن a = 17. ما هي الأعداد الأولية p التي يكون فيها 17 باقي تربيعي؟

يمكننا اختبار الأعداد الأولية p يدويًا باستخدام الصيغة المذكورة أعلاه.

في إحدى الحالات، عند اختبار p = 3، لدينا 17 (3 − 1)/2 = 17 1 ≡ 2 ≡ −1 (mod 3)، وبالتالي فإن 17 ليس باقي تربيعي modulo 3.

في حالة أخرى، عند اختبار p = 13، نحصل على 17 (13 − 1)/2 = 17 6 ​​≡ 1 (mod 13)، وبالتالي فإن 17 هو باقي تربيعي modulo 13. وللتأكيد، لاحظ أن 17 ≡ 4 (mod 13)، و 2 2 = 4.

يمكننا إجراء هذه الحسابات بشكل أسرع باستخدام خصائص الحساب النمطي المختلفة ورموز ليجندر.

إذا واصلنا حساب القيم، فسنجد:

(17/ p ) = +1 لـ p = {13, 19, ...} (17 هو باقي تربيعي modulo هذه القيم)
(17/ p ) = −1 لـ p = {3, 5, 7, 11, 23, ...} (17 ليس باقي تربيعي modulo هذه القيم).

مثال 2: إيجاد البواقي بمعلومية معامل أولي p

ما هي الأعداد التي تمثل مربعات بتردد 17 (البقايا التربيعية بتردد 17)؟

يمكننا حسابها يدوياً على النحو التالي:

1 2 = 1
2 2 = 4
3 2 = 9
4 2 = 16
5 2 = 25 ≡ 8 (mod 17)
6 2 = 36 ≡ 2 (mod 17)
7 2 = 49 ≡ 15 (mod 17)
8 2 = 64 ≡ 13 (mod 17).

إذن، مجموعة البواقي التربيعية بتردد 17 هي {1، 2، 4، 8، 9، 13، 15، 16}. لاحظ أننا لم نكن بحاجة إلى حساب مربعات القيم من 9 إلى 16، لأنها جميعًا سالبة للقيم المربعة السابقة (على سبيل المثال، 9 ≡ −8 (mod 17)، لذا 9² ≡ (−8) ² = 64 ≡ 13 (mod 17)).

يمكننا إيجاد البواقي التربيعية أو التحقق منها باستخدام الصيغة المذكورة أعلاه. لاختبار ما إذا كان العدد 2 باقيًا تربيعيًا بتردد 17، نحسب 2 (17 - 1)/2 = 2، أي أن 8 ≡ 1 (mod 17)، لذا فهو باقي تربيعي. لاختبار ما إذا كان العدد 3 باقيًا تربيعيًا بتردد 17، نحسب 3 (17 - 1)/2 = 3، أي أن 8 ≡ 16 ≡ -1 (mod 17)، لذا فهو ليس باقيًا تربيعيًا.

يرتبط معيار أويلر بقانون التبادل التربيعي .

التطبيقات

من الناحية العملية، من الأفضل استخدام نسخة موسعة من خوارزمية إقليدس لحساب رمز جاكوبي .(أن){\displaystyle \left({\frac {a}{n}}\right)}. لون{\displaystyle n}إذا كان عددًا أوليًا فرديًا، فهذا يساوي رمز ليجندر، ويحدد ما إذا كانأ{\displaystyle a}هو الباقي التربيعي moduloن{\displaystyle n}.

من ناحية أخرى، بما أن تكافؤأن-12{\displaystyle a^{\frac {n-1}{2}}}ينطبق رمز جاكوبي على جميع الأعداد الأولية الفردية، ولكن ليس بالضرورة على الأعداد المركبة. ويمكن استخدام حساب كليهما ومقارنتهما كاختبار أولي، وتحديدًا اختبار سولوفاي-ستراسن الأولي . الأعداد المركبة التي ينطبق عليها التطابق لقيمة معينةأ{\displaystyle a}تُسمى هذه الأعداد بالأعداد الأولية الزائفة لأويلر-جاكوبي بالنسبة للأساسأ{\displaystyle a}.

ملحوظات

  1. ↑ غاوس ، DA، المادة 106
  2. ↑ دينس، جوزيف ب.؛ دينس، توماس ب. (1999). "النظرية 6.4، الفصل 6. البواقي" . عناصر نظرية الأعداد . دار هاركورت الأكاديمية للنشر. ص  197. ISBN 9780122091308.
  3. ↑ ليونارد يوجين ديكسون، "تاريخ نظرية الأعداد"، المجلد 1، صفحة 205، دار نشر تشيلسي 1952
  4. ↑ هاردي ورايت، thm. 83
  5. ↑ يشير ليمرمير، في الصفحة 4، إلى ورقتين بحثيتين، E134 وE262، في أرشيف أويلر.
  6. ^ لام أويلر، Novi commentarii Academiae Scientiarum Imperialis Petropolitanae، 8، 1760-1، 74؛ الشرج Opusc. 1، 1772، 121؛ إتصالات. أريث، 1، 274، 487

مراجع

تُرجمت كتاب "Disquisitiones Arithmeticae" من اللاتينية الشيشرونية لغوس إلى الإنجليزية والألمانية . وتشمل النسخة الألمانية جميع أبحاثه في نظرية الأعداد: جميع براهين التبادلية التربيعية ، وتحديد إشارة مجموع غاوس ، والبحوث المتعلقة بالتبادلية التربيعية الثنائية ، وملاحظات غير منشورة.

  • غاوس، كارل فريدريش (1986)، Disquisitiones Arithemeticae (الطبعة الثانية المصححة) ، ترجمة كلارك، آرثر أ. (الإنجليزية)، نيويورك: سبرينغر ، ISBN 0-387-96254-9
  • Gauss، Carl Friedrich (1965)، Unter suchungen über höhere Arithmetik (Disquisitiones Arithemeticae وأوراق أخرى حول نظرية الأعداد) (الطبعة الثانية) ، ترجمة Maser، H. (ألمانية)، نيويورك: تشيلسي، ISBN 0-8284-0191-8
  • ليميرماير، فرانز (2000)، قوانين المعاملة بالمثل: من أويلر إلى أيزنشتاين ، برلين: سبرينغر ، ISBN 3-540-66957-4