رمز ليجندر

في نظرية الأعداد ، رمز ليجاندر هو دالة لـ${\displaystyle a}$و${\displaystyle p}$يُعرَّف بأنه

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{إذا كان }}a{\text{ باقيًا تربيعيًا modulo }}p{\text{ و }}a\not \equiv 0{\pmod {p}},\\-1&{\text{إذا كان }}a{\text{ ليس باقيًا تربيعيًا modulo }}p,\\0&{\text{إذا كان }}a\equiv 0{\pmod {p}}.\end{cases}}}$

أين${\displaystyle p}$هو عدد أولي فردي و${\displaystyle a}$هو عدد صحيح موجب قد يكون أو لا يكون باقي قسمة تربيعية على p . رمز ليجندر هو دالة ضربية . 

تم تقديم رمز ليجندر بواسطة أدريان ماري ليجندر في عام 1797 أو 1798 ^{[ 1 ]} خلال محاولاته لإثبات قانون التبادل التربيعي . تشمل تعميمات هذا الرمز رمز جاكوبي ورموز ديريشليه من الرتب العليا. وقد ألهمت سهولة استخدام رمز ليجندر في الترميز تقديم العديد من "الرموز" الأخرى المستخدمة في نظرية الأعداد الجبرية ، مثل رمز هيلبرت ورمز آرتين .

كان تعريف ليجاندر الأصلي من خلال الصيغة الصريحة

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ و }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.}$

وفقًا لمعيار أويلر ، الذي اكتُشف سابقًا وكان معروفًا لليجندر، فإن هذين التعريفين متكافئان. ^{[ 2 ]} وبالتالي ، تمثلت مساهمة ليجندر في تقديم رمز مناسب لتسجيل ما إذا كان a باقيًا أو غير باقي modulo p . استخدم رمز جاوس الأصلي R p لـ${\displaystyle ({\tfrac {a}{p}})=1}$و N p لـ​${\displaystyle ({\tfrac {a}{p}})=-1}$لأغراض الطباعة، يُكتب رمز ليجندر أحيانًا على النحو التالي: ( a  | p ) أو ( a / p ). بالنسبة لقيمة p ثابتة ، يكون التسلسل ${\displaystyle ({\tfrac {0}{p}}),({\tfrac {1}{p}}),({\tfrac {2}{p}}),\ldots }$ هي دورية بفترة p وتسمى أحيانًا متتالية ليجندر (انظر الجدول أعلاه).

هناك عدد من الخصائص المفيدة لرمز ليجندر والتي، جنبًا إلى جنب مع قانون التبادل التربيعي ، يمكن استخدامها لحسابه بكفاءة.

• بافتراض وجود مولد${\displaystyle g\in \mathbb {F} _{p}^{*}}$، لو${\displaystyle x=g^{r}}$، ثم${\displaystyle x}$يكون الباقي تربيعيًا إذا وفقط إذا${\displaystyle r}$وهو عدد زوجي. وهذا يدل على أن نصف العناصر في${\displaystyle \mathbb {F} _{p}^{*}}$هي بقايا تربيعية.
• لو${\displaystyle p\equiv 3{\text{ mod }}4}$ثم حقيقة أن

  ${\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {p+1}{2}}={\frac {(p-1)+2}{2}}={\frac {p-1}{2}}+1}$ هذا ما يمنحنا${\displaystyle a=x^{(p+1)/4}}$هو الجذر التربيعي للباقي التربيعي${\displaystyle x}$.

• رمز ليجاندر دوري في وسيطه الأول (أو العلوي): إذا كان a ≡ b (mod p )، فإن

  ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}$

• رمز ليجندر هو دالة ضربية بالكامل لوسيطه العلوي:

  ${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}$

• على وجه الخصوص، فإن حاصل ضرب عددين كلاهما بواقي تربيعية أو بواقي غير تربيعية بتردد p هو باقٍ، بينما حاصل ضرب باقٍ مع باقٍ غير تربيعي هو باقٍ غير تربيعي. وثمة حالة خاصة هي رمز ليجندر للمربع.

  ${\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}}$

• عند النظر إليها كدالة لـ a ، فإن رمز ليجندر${\displaystyle \left({\frac {a}{p}}\right)}$هو الخاصية التربيعية الفريدة (أو من الدرجة 2) لـ Dirichlet modulo p .
• الملحق الأول لقانون التبادل التربيعي:

  ${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ إذا كان }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ إذا كان }}p\equiv 3{\pmod {4}}.\end{cases}}}$

• الملحق الثاني لقانون التبادل التربيعي:

  ${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ إذا كان }}p\equiv 1{\mbox{ أو }}7{\pmod {8}}\\-1&{\mbox{ إذا كان }}p\equiv 3{\mbox{ أو }}5{\pmod {8}}.\end{cases}}}$

• صيغ خاصة لرمز ليجندر${\displaystyle \left({\frac {a}{p}}\right)}$بالنسبة للقيم الصغيرة لـ a :
  • بالنسبة لعدد أولي فردي p  ≠  3،

    ${\displaystyle \left({\frac {3}{p}}\right)=(-1)^{{\big \lfloor }{\frac {p+1}{6}}{\big \rfloor }}={\begin{cases}1&{\mbox{ إذا كان }}p\equiv 1{\mbox{ أو }}11{\pmod {12}}\\-1&{\mbox{ إذا كان }}p\equiv 5{\mbox{ أو }}7{\pmod {12}}.\end{cases}}}$

  • بالنسبة لعدد أولي فردي p  ≠  5،

    ${\displaystyle \left({\frac {5}{p}}\right)=(-1)^{{\big \lfloor }{\frac {2p+2}{5}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1&{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}.\end{cases}}}$

• تُعرَّف أعداد فيبوناتشي 1، 1، 2، 3، 5، 8، 13، 21، 34، 55، ... بالعلاقة التكرارية _{F₁ = F₂ =} 1 ، _{Fₙ₊₁ =} Fₙ + Fₙ₋₁ . إذا كان _p عددًا أوليًا ، فإن

  ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}$

على سبيل المثال،

${\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}$

• تأتي هذه النتيجة من نظرية متواليات لوكاس ، والتي تُستخدم في اختبار الأعداد الأولية . ^{[ 3 ]} انظر العدد الأولي Wall–Sun–Sun .

مجموع على شكل${\displaystyle \sum \left({\frac {f\left(a\right)}{p}}\right)}$، ويتم عادةً تطبيقها على جميع الأعداد الصحيحة في النطاق${\displaystyle \left[0,p-1\right]}$لبعض الوظائف${\displaystyle f}$، هي حالة خاصة من مجاميع الأحرف . وهي ذات أهمية في توزيع البواقي التربيعية بتردد عدد أولي.

ليكن p و q عددين أوليين فرديين مختلفين. باستخدام رمز ليجندر، يمكن صياغة قانون التبادل التربيعي بإيجاز:

${\displaystyle \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\tfrac {p-1}{2}}\cdot {\tfrac {q-1}{2}}}.}$

تعتمد العديد من براهين التبادلية التربيعية على معيار أويلر.

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}$

بالإضافة إلى ذلك، تم ابتكار العديد من التعبيرات البديلة لرمز ليجندر من أجل إنتاج براهين مختلفة لقانون التبادل التربيعي.

• قدّم غاوس مجموع غاوس التربيعي واستخدم الصيغة

${\displaystyle \sum _{k=0}^{p-1}\zeta ^{ak^{2}}=\left({\frac {a}{p}}\right)\sum _{k=0}^{p-1}\zeta ^{k^{2}},\qquad \zeta =e^{\frac {2\pi i}{p}}}$

في البرهان الرابع ^{[ 4 ]} والسادس ^{[ 5 ]} على التبادلية التربيعية.

• يُثبت برهان كرونكر ^{[ 6 ]} أولاً أن

${\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \left(\prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)\right).}$

وبعكس أدوار p و q ، يحصل على العلاقة بين ( ⁠ p / q ⁠ ) و ( ⁠ q / p ⁠ ).

• تبدأ إحدى براهين أيزنشتاين ^{[ 7 ]} بإثبات أن

${\displaystyle \left({\frac {q}{p}}\right)=\prod _{n=1}^{\frac {p-1}{2}}{\frac {\sin \left({\frac {2\pi qn}{p}}\right)}{\sin \left({\frac {2\pi n}{p}}\right)}}.}$

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

• رمز جاكوبي${\displaystyle \left({\frac {a}{n}}\right)}$يُعدّ هذا تعميمًا لرمز ليجاندر يسمح بوجود وسيط ثانٍ (سفلي) مركب n ، مع ضرورة أن يكون n فرديًا وموجبًا. يوفر هذا التعميم طريقة فعّالة لحساب جميع رموز ليجاندر دون الحاجة إلى إجراء التحليل إلى عوامل.
• وهناك امتداد آخر هو رمز كرونكر ، حيث يمكن أن يكون الوسيط السفلي أي عدد صحيح.
• يعمّم رمز الباقي الأسي ( a / n ) n رمز ليجندر إلى أس أعلى n . ويمثل رمز ليجندر رمز الباقي الأسي _عندما n = 2.  

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

${\displaystyle {\begin{aligned}\left({\frac {12345}{331}}\right)&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)\\&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)\\&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)\\&=(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)\\&=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)\\&=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3^{2}}{23}}\right)\\&=-(1)(1)(1)(1)\\&=-1.\end{aligned}}}$

أو باستخدام حساب أكثر كفاءة:

${\displaystyle \left({\frac {12345}{331}}\right)=\left({\frac {98}{331}}\right)=\left({\frac {2\cdot 7^{2}}{331}}\right)=\left({\frac {2}{331}}\right)=(-1)^{\tfrac {331^{2}-1}{8}}=-1.}$

تحتوي مقالة رمز جاكوبي على المزيد من الأمثلة على التلاعب برمز ليجندر.

بما أنه لا توجد خوارزمية تحليل فعّالة معروفة، ولكن توجد خوارزميات أسية معيارية فعّالة ، فمن الأفضل عمومًا استخدام تعريف ليجندر الأصلي، على سبيل المثال

${\displaystyle {\begin{aligned}\left({\frac {98}{331}}\right)&\equiv 98^{\frac {331-1}{2}}&{\pmod {331}}\\&\equiv 98^{165}&{\pmod {331}}\\&\equiv 98\cdot (98^{2})^{82}&{\pmod {331}}\\&\equiv 98\cdot 5^{82}&{\pmod {331}}\\&\equiv 98\cdot 25^{41}&{\pmod {331}}\\&\equiv 133\cdot 25^{40}&{\pmod {331}}\\&\equiv 133\cdot 294^{20}&{\pmod {331}}\\&\equiv 133\cdot 45^{10}&{\pmod {331}}\\&\equiv 133\cdot 39^{5}&{\pmod {331}}\\&\equiv 222\cdot 39^{4}&{\pmod {331}}\\&\equiv 222\cdot 197^{2}&{\pmod {331}}\\&\equiv 222\cdot 82&{\pmod {331}}\\&\equiv -1&{\pmod {331}}\end{aligned}}}$

باستخدام التربيع المتكرر modulo 331، وتقليل كل قيمة باستخدام المعامل بعد كل عملية لتجنب الحساب مع الأعداد الصحيحة الكبيرة.

فيما يلي جدول قيم رمز ليجندر${\displaystyle \left({\frac {a}{p}}\right)}$مع p  ≤  127، a  ≤  30، p عدد أولي فردي.

• غاوس ، كارل فريدريش (1965)، Unter suchungen über höhere Arithmetik (Disquisitiones Arithmeticae & أوراق أخرى حول نظرية الأعداد) ، ترجمة Maser، H. (  الطبعة الثانية)، نيويورك: تشيلسي، ISBN 0-8284-0191-8
• غاوس، كارل فريدريش (1986)، Disquisitiones Arithmeticae ، ترجمة كلارك، آرثر أ. (  الطبعة الثانية المصححة)، نيويورك: سبرينغر ، ISBN 0-387-96254-9
• باخ، إريك؛ شاليت، جيفري (1996)، نظرية الأعداد الخوارزمية ، المجلد  الأول: الخوارزميات الفعالة، كامبريدج: مطبعة معهد ماساتشوستس للتكنولوجيا ، ISBN 0-262-02405-5
• هاردي، جي إتش ؛ رايت، إي إم (1980)، مقدمة في نظرية الأعداد (الطبعة الخامسة) ، أكسفورد: مطبعة جامعة أكسفورد ، رقم ISBN 978-0-19-853171-5
• أيرلندا، كينيث؛ روزن، مايكل (1990)، مقدمة كلاسيكية لنظرية الأعداد الحديثة (  الطبعة الثانية)، نيويورك: سبرينغر ، ISBN 0-387-97329-X
• ليميرماير، فرانز (2000)، قوانين المعاملة بالمثل: من أويلر إلى أيزنشتاين ، برلين: سبرينغر ، ISBN 3-540-66957-4
• ريبنبوم، باولو (1996)، الكتاب الجديد لسجلات الأعداد الأولية ، نيويورك: سبرينغر ، رقم ISBN 0-387-94457-5

• حاسبة رمز جاكوبي