نظرية لوكاس

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

في نظرية الأعداد ، تعبر نظرية لوكاس عن باقي قسمة معامل ذي الحدين(من){\displaystyle {\tbinom {m}{n}}}بواسطة عدد أولي p بدلالة توسعات الأساس p للأعداد الصحيحة m و n .

ظهرت نظرية لوكاس لأول مرة في عام 1878 في أوراق بحثية لإدوارد لوكاس . [ 1 ]

إفادة

بالنسبة للأعداد الصحيحة غير السالبة m و n وعدد أولي p ، تتحقق علاقة التطابق التالية :

(من)≡∏أنا=0ك(مأنانأنا)(تعديلص)،{\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}

أين

م=مكصك+مك-1صك-1+⋯+م1ص+م0،{\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}

و

ن=نكصك+نك-1صك-1+⋯+ن1ص+ن0{\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}

يمثلان التوسعات الأساسية p للعددين m و n على التوالي. ويستخدم هذا الاصطلاح التالي:(من)=0{\displaystyle {\tbinom {m}{n}}=0}إذا كان m  < n . 

البراهين

هناك عدة طرق لإثبات نظرية لوكاس.

برهان توافقي باستخدام فعل المجموعة

لتكن M مجموعةً تحتوي على m عنصرًا، ولنقسمها بشكلٍ عشوائي إلى mᵢ دورة طول كل منها pᵢ ، وذلك لقيم مختلفة لـ i . عندئذٍ، يمكن تدوير كل دورة من هذه الدورات على حدة بواسطة زمرة دورية Cᵢ ، بحيث تؤثر الزمرة G ، وهي حاصل الضرب الديكارتي لجميع هذه الزمر الدورية (واحدة لكل دورة)، على M. وبالتالي، فإنها تؤثر أيضًا على مجموعة المجموعات الجزئية N من M التي تحتوي على n عنصرًا ، وعددها هو(من){\displaystyle {\tbinom {m}{n}}}هذا هو العمل الجماعي الذي سنتناوله في الجزء التالي.

بما أن عدد العناصر في G هو قوة للعدد p ، فإن الأمر نفسه ينطبق على أي من مداراتها ، وفقًا لنظرية المدارات المثبتة . ومن ثم،(من){\displaystyle {\tbinom {m}{n}}}متطابق بتردد p مع عدد المجموعات N التي مدارها بحجم 1، أي مع عدد النقاط الثابتة لفعل المجموعة.

بما أن جميع الدورات قابلة للدوران بشكل مستقل بواسطة مجموعتنا G ، فإن النقاط الثابتة للفعل هي تلك المجموعات الجزئية N التي تمثل اتحادًا لبعض الدورات. هذا يعني أن N يجب أن تتكون من n i دورة بالضبط، حجم كل منها p i لكل i ، وذلك للسبب نفسه الذي يجعل للعدد الصحيح n تمثيلًا فريدًا في النظام العددي ذي الأساس p . وبالتالي، فإن عدد الخيارات لـ N هو بالضبط ∏أنا=0ك(مأنانأنا){\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}}.

برهان قائم على الدوال المولدة

يعود الفضل في هذا الدليل إلى ناثان فاين. [ 2 ]

إذا كان p عددًا أوليًا و n عددًا صحيحًا حيث 1 ≤ n ≤ p − 1، فإن بسط معامل ذات الحدين

(صن)=ص⋅(ص-1)⋯(ص-ن+1)ن⋅(ن-1)⋯1{\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}

يقبل القسمة على p، لكن المقام لا يقبل القسمة عليه. لذا، فإن p يقبل القسمة على p(صن){\displaystyle {\tbinom {p}{n}}}بسبب نظرية ذات الحدين ، هذا يعني أن

(1+X)ص≡1+Xص(تعديلص).{\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}

بالاستمرار بالاستقراء ، لدينا لكل عدد صحيح غير سالب i أن

(1+X)صأنا≡1+Xصأنا(تعديلص).{\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}

ليكن m عددًا صحيحًا غير سالب، وليكن p عددًا أوليًا. اكتب m في النظام العددي ذي الأساس p ، بحيثم=∑أنا=0كمأناصأنا{\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}لبعض الأعداد الصحيحة غير السالبة k والأعداد الصحيحة mᵢ حيث 0 ≤ mᵢ ≤ p − 1. عندئذٍ

∑ن=0م(من)Xن=(1+X)م=∏أنا=0ك((1+X)صأنا)مأنا≡∏أنا=0ك(1+Xصأنا)مأنا=∏أنا=0ك(∑جأنا=0مأنا(مأناجأنا)Xجأناصأنا)=∑ن=0م(∏أنا=0ك(مأنانأنا))Xن(تعديلص).\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}}.\end{aligned}}}

في المساواة الأخيرة ، نستخدم خاصية التوزيع وحقيقة أن تمثيل العدد n في النظام العددي ذي الأساس p فريد ، حيث يمثل nᵢ الرقم i في تمثيل n في النظام العددي ذي الأساس p . وبمقارنة معاملات Xⱼ في المجموع الأول والأخير، نحصل على نظرية لوكاس.

مثلث باسكال، يوضح معاملات ذات الحدين الفردية باللون الأسود.

عواقب

إحدى نتائج نظرية لوكاس هي أن معامل ذي الحدين(من){\displaystyle {\tbinom {m}{n}}}يكون العدد قابلاً للقسمة على العدد الأولي p إذا وفقط إذا كان أحد أرقام تمثيل n ذي الأساس p أكبر من الرقم المقابل في m . على وجه الخصوص،(من){\displaystyle {\tbinom {m}{n}}}يكون العدد فرديًا إذا وفقط إذا كانت مواقع الآحاد في التمثيل الثنائي للعدد n مجموعة جزئية من مواقع الآحاد في التمثيل الثنائي للعدد m . وهذا يؤدي إلى توزيع مميز للأعداد الفردية في مثلث باسكال ، يشبه مثلث سيربينسكي ، الموضح على اليمين.

معاملات غير أولية

يمكن تعميم نظرية لوكاس لإعطاء تعبير عن الباقي عندما(من){\displaystyle {\tbinom {m}{n}}}يقسم على قوة عدد أولي p k . ومع ذلك، تصبح الصيغ أكثر تعقيدًا.

إذا كان المعيار هو مربع عدد أولي p ، فإن علاقة التطابق التالية تنطبق على جميع 0 ≤ s ≤ r ≤ p − 1، a ≥ 0، و b ≥ 0:

(صأ+رصب+s)≡(أب)(رs)(1+صأ(حر-حر-s)+صب(حر-s-حs))(تعديلص2)،{\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{rs})+pb(H_{rs}-H_{s})){\pmod {p^{2}}},}

أينحن=1+12+13+⋯+1ن{\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}}هو العدد التوافقي النوني . [ 3 ] كما قدم ديفيس وويب (1990) [ 4 ] وغرانفيل (1997) تعميمات لنظرية لوكاس لقوى الأعداد الأولية الأعلى p k. [ 5 ]

تنص نظرية كومر على أن أكبر عدد صحيح k بحيث يكون p k يقسم معامل ذات الحدين(من){\displaystyle {\tbinom {m}{n}}}(أو بعبارة أخرى، فإن تقييم معامل ذي الحدين بالنسبة للعدد الأولي p ) يساوي عدد عمليات الحمل التي تحدث عند إضافة n و m  − n في الأساس p . 

معاملات ذات الحدين q

يوجد تعميم لنظرية لوكاس لمعاملات التوزيع الثنائي q . تنص هذه النظرية على أنه إذا كانت a و b و r و s و k أعدادًا صحيحة، حيث 0 ≤ b و s < k ، فإن [كأ+بكر+s]q≡(أر)[بs]qتعديلΦك،{\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}\equiv {\binom {a}{r}}{\begin{bmatrix}b\\s\end{bmatrix}}_{q}\mod {\Phi _{k}},}أين​[كأ+بكر+s]q{\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}}و​​[بs]q{\displaystyle {\begin{bmatrix}b\\s\end{bmatrix}}_{q}}هيمعاملات ذات الحدين q ،(أر){\displaystyle {\binom {a}{r}}}هو معامل ذو حدين عادي، وΦك{\displaystyle \Phi _{k}}⁠ هي متعددة الحدود الدائرية من الرتبة k ( في المتغير q ). [ 6 ]

مراجع

  1. ↑
  2. ↑ فاين، ناثان (1947). "معاملات ذات الحدين بتردد عدد أولي". المجلة الرياضية الأمريكية الشهرية . 54 (10): 589-592 . doi : 10.2307/2304500 . JSTOR 2304500 . 
  3. ↑ رولاند، إريك (2022). "نظرية لوكاس modulo p 2 ". المجلة الرياضية الأمريكية الشهرية . 129 (9): 846-855 . arXiv : 2006.11701v3 . doi : 10.1080/00029890.2022.2038004 .
  4. ↑ كينيث س. ديفيس، ويليام أ. ويب (1990). "نظرية لوكاس للقوى الأولية". المجلة الأوروبية للتوافقية . 11 (3): 229-233 . doi : 10.1016/S0195-6698(13)80122-9 .
  5. ↑ أندرو جرانفيل (1997). "الخواص الحسابية لمعاملات ذات الحدين 1: معاملات ذات الحدين بتردد قوى الأعداد الأولية" (ملف PDF) . وقائع مؤتمر الجمعية الرياضية الكندية . 20 : 253-275 . MR 1483922. مؤرشف من الأصل (ملف PDF) بتاريخ 2017-02-02. 
  6. ^ ديسارمينين، جاك (مارس 1982). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". المجلة الأوروبية للتوافقيات . 3 (1): 19-28 . دوى : 10.1016/S0195-6698(82)80005-X .