نظرية ويلسون

في الجبر ونظرية الأعداد ، تنص نظرية ويلسون على أن العدد الطبيعي n > 1 هو عدد أولي إذا وفقط إذا كان حاصل ضرب جميع الأعداد الصحيحة الموجبة الأقل من n أقل بمقدار واحد من مضاعف n . أي (باستخدام تدوينات الحساب النمطي )، فإن العامل يفي بالشرط ${\displaystyle (n-1)!=1\times 2\times 3\times \cdots \times (n-1)}$

${\displaystyle (n-1)!\ \equiv \;-1{\pmod {n}}}$

بالضبط عندما يكون n عددًا أوليًا. بعبارة أخرى، أي عدد صحيح n > 1 يكون عددًا أوليًا إذا، وفقط إذا، ( n  − 1)! + 1 قابل للقسمة على n . ^[1]

تم طرح النظرية لأول مرة من قبل ابن الهيثم حوالي عام  1000 م . ^{[2] أعلن} إدوارد وارنج عن النظرية في عام 1770 دون إثباتها، ونسب الفضل في اكتشافها إلى تلميذه جون ويلسون . ^{[3] قدم} لاجرانج أول دليل في عام 1771. ^[4] هناك أدلة على أن لايبنتز كان على علم بالنتيجة أيضًا قبل قرن من الزمان، لكنه لم ينشرها أبدًا. ^[5]

بالنسبة لكل من قيم n من 2 إلى 30، يوضح الجدول التالي العدد ( n  − 1)! والباقي عند  قسمة ( n − 1)! على n . (في تدوين الحساب النمطي ، يُكتب الباقي عند قسمة m على n على هيئة m mod n .) لون الخلفية هو الأزرق للقيم الأولية لـ n ، والذهبي للقيم المركبة .

جدول العامل والباقي منه modulo n

${\displaystyle n}$	${\displaystyle (n-1)!}$ (التسلسل A000142 في OEIS )	${\displaystyle (n-1)!\ {\bmod {\ }}n}$ (التسلسل A061006 في OEIS )
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

باعتبارها عبارة ثنائية الشرط (إذا وفقط إذا)، فإن الإثبات يتكون من نصفين: لإظهار أن المساواة لا تتحقق عندما يكون مركبًا، ولإظهار أنها تتحقق عندما يكون أوليًا. ${\displaystyle n}$${\displaystyle n}$

افترض أن مركب. وبالتالي، فهو قابل للقسمة على عدد أولي حيث . ولأنه يقسم ، يوجد عدد صحيح بحيث . افترض من أجل التناقض أن متطابق مع modulo . عندئذٍ سيكون أيضًا متطابقًا مع modulo : في الواقع، إذا كان عندئذٍ لعدد صحيح ، وبالتالي يكون أقل بمقدار واحد من مضاعف . من ناحية أخرى، بما أن ، فإن أحد العوامل في حاصل الضرب الموسع هو . وبالتالي . وهذا تناقض؛ وبالتالي فمن غير الممكن أن يكون عندما مركبًا. ${\displaystyle n}$${\displaystyle q}$${\displaystyle 2\leq q<n}$${\displaystyle q}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n=qk}$${\displaystyle (n-1)!}$${\displaystyle -1}$${\displaystyle {n}}$${\displaystyle (n-1)!}$${\displaystyle -1}$${\displaystyle {q}}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$${\displaystyle م}$${\displaystyle (n-1)!}$${\displaystyle q}$${\displaystyle 2\leq q\leq n-1}$${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$${\displaystyle q}$${\displaystyle (n-1)!\equiv 0{\pmod {q}}}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$${\displaystyle n}$

في الواقع، هناك المزيد من ذلك صحيح. باستثناء الحالة الوحيدة ، حيث ، إذا كان مركبًا، فإنه يتطابق مع 0 modulo . يمكن تقسيم الإثبات إلى حالتين: أولاً، يمكن تحليل if إلى عوامل على أنها حاصل ضرب عددين غير متساويين، حيث ، فإن كلاً من و سيظهران كعوامل في حاصل الضرب وبالتالي فهو قابل للقسمة على . إذا لم يكن له مثل هذا التحليل إلى عوامل، فيجب أن يكون مربع بعض الأعداد الأولية الأكبر من 2. ولكن بعد ذلك ، فإن كلاً من و سيكونان عوامل لـ ، وبالتالي يقسم في هذه الحالة أيضًا. ${\displaystyle n=4}$${\displaystyle 3!=6\equiv 2{\pmod {4}}}$${\displaystyle n}$${\displaystyle (n-1)!}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=ab}$${\displaystyle 2\leq a<b<n}$${\displaystyle أ}$${\displaystyle b}$${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$${\displaystyle (n-1)!}$${\displaystyle ab=n}$${\displaystyle n}$${\displaystyle q}$${\displaystyle 2q<q^{2}=n}$${\displaystyle q}$${\displaystyle 2q}$${\displaystyle (n-1)!}$${\displaystyle n}$${\displaystyle (n-1)!}$

يستخدم الدليلان الأوليان أدناه حقيقة أن فئات البقايا modulo a عدد أولي هي مجال منتهٍ - راجع المقال مجال أولي لمزيد من التفاصيل. ^[6]

النتيجة تافهة عندما ، لذا افترض هو عدد أولي فردي، . نظرًا لأن فئات البقايا تشكل modulo حقلًا، فإن كل بقايا غير صفرية لها معكوس مضاعف فريد . تشير مبرهنة إقليدس ^[a] إلى أن القيم الوحيدة لـ والتي هي . لذلك، باستثناء ، يمكن ترتيب العوامل في الشكل الموسع لـ في أزواج منفصلة بحيث يكون حاصل ضرب كل زوج متطابقًا مع 1 modulo . وهذا يثبت نظرية ويلسون. ${\displaystyle p=2}$${\displaystyle p}$${\displaystyle p\geq 3}$${\displaystyle p}$${\displaystyle أ}$${\displaystyle a^{-1}}$${\displaystyle أ}$${\displaystyle a\equiv a^{-1}{\pmod {p}}}$${\displaystyle a\equiv \pm 1{\pmod {p}}}$${\displaystyle \pm 1}$${\displaystyle (p-1)!}$${\displaystyle p}$

على سبيل المثال، بالنسبة لـ ، لدينا ${\displaystyle p=11}$$${\displaystyle 10!=[(1\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.}$$

مرة أخرى، النتيجة تافهة بالنسبة لـ p  = 2، لذا افترض أن p عدد أولي فردي، p ≥ 3. ضع في اعتبارك كثيرة الحدود

${\displaystyle g(x)=(x-1)(x-2)\cdots (x-(p-1)).}$

g لها درجة p − 1 ، والحد الرئيسي x ^{p − 1} ، والحد الثابت ( p − 1)!. وجذورها p − 1 هي 1، 2، ...، p − 1 .

الآن فكر

${\displaystyle h(x)=x^{p-1}-1.}$

h لها أيضًا درجة p − 1 والحد الرئيسي x ^{p − 1.} وفقًا لـ modulo p ، تنص نظرية فيرما الصغيرة على أنها لها أيضًا نفس الجذور p − 1 ، 1، 2، ...، p − 1 .

وأخيرا، ضع في اعتبارك

${\displaystyle f(x)=g(x)-h(x).}$

f لها درجة لا تزيد عن p  − 2 (نظرًا لأن الحدود الرئيسية تلغي بعضها البعض)، وmodulo p لها أيضًا جذور p − 1 1، 2، ...، p − 1. لكن نظرية لاجرانج تقول إنه لا يمكن أن يكون لها أكثر من p  − 2 جذور. لذلك، يجب أن تكون f مساوية للصفر تمامًا (mod p )، لذا فإن حدها الثابت هو ( p − 1)! + 1 ≡ 0 (mod p ) . هذه هي نظرية ويلسون.

من الممكن استنتاج نظرية ويلسون من تطبيق معين لنظريات سيلاو . لنفترض أن p عدد أولي. من السهل استنتاج أن المجموعة المتماثلة تحتوي على عناصر من رتبة p بالضبط ، أي دورات p . من ناحية أخرى، كل مجموعة فرعية p لسيلاو في هي نسخة من . وبالتالي، يتبع ذلك أن عدد مجموعات p الفرعية لسيلاو هو . تشير نظرية سيلاو الثالثة إلى ${\displaystyle S_{p}}$${\displaystyle (p-1)!}$${\displaystyle C_{p}}$${\displaystyle S_{p}}$${\displaystyle C_{p}}$${\displaystyle n_{p}=(p-2)!}$

${\displaystyle (p-2)!\equiv 1{\pmod {p}}.}$

ضرب كلا الطرفين في ( ص − 1) يعطي

${\displaystyle (p-1)!\equiv p-1\equiv -1{\pmod {p}},}$

وهذا هو النتيجة.

في الممارسة العملية، لا فائدة من نظرية ويلسون كاختبار للأعداد الأولية لأن حساب ( n − 1) modulo n لقيمة n كبيرة معقد حسابيًا ، ومن المعروف أن اختبارات الأعداد الأولية أسرع كثيرًا (في الواقع، حتى التقسيم التجريبي أكثر كفاءة إلى حد كبير). ^{[ بحاجة لمصدر ]}

عند استخدامها في الاتجاه الآخر، لتحديد أولوية خلفاء العوامل الكبيرة، فهي في الواقع طريقة سريعة وفعالة للغاية. ومع ذلك، فإن فائدتها محدودة. ^{[ بحاجة لمصدر ]}

باستخدام نظرية ويلسون، لأي عدد أولي فردي p = 2 m + 1 ، يمكننا إعادة ترتيب الجانب الأيسر للحصول على المساواة. هذا يصبح أو يمكننا استخدام هذه الحقيقة لإثبات جزء من نتيجة مشهورة: لأي عدد أولي p بحيث p  ≡ 1 (mod 4) ، العدد (−1) هو مربع ( بقايا تربيعية ) mod p . لهذا، افترض أن p  = 4 k  + 1 لبعض الأعداد الصحيحة k . ثم يمكننا أن نأخذ m  = 2 k أعلاه، ونستنتج أن ( m !) ² متطابق مع (−1) (mod p ). $${\displaystyle 1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}}$$$${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}.}$$$${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}}$$$${\displaystyle (m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.}$$

لقد تم استخدام نظرية ويلسون لبناء صيغ للأعداد الأولية ، ولكنها بطيئة جدًا بحيث لا يكون لها قيمة عملية.

تسمح نظرية ويلسون بتعريف دالة جاما p-adic .

أثبت جاوس ^{[7] [ مصدر غير أساسي مطلوب ]} أن حيث يمثل p عددًا أوليًا فرديًا وعددًا صحيحًا موجبًا. أي أن حاصل ضرب الأعداد الصحيحة الموجبة الأقل من m والأعداد الأولية نسبيًا إلى m يكون أقل بواحد من مضاعفات m عندما يكون m يساوي 4، أو قوة عدد أولي فردي، أو ضعف قوة عدد أولي فردي؛ وإلا فإن الحاصل يكون أكبر بواحد من مضاعفات m . قيم m التي يكون حاصل ضربها −1 هي على وجه التحديد القيم التي يوجد بها جذر بدائي modulo m . $${\displaystyle \prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}}$$${\displaystyle \alpha }$

• ويلسون برايم
• جدول التطابقات
• تخمين أغوه-جيوغا

• "نظرية ويلسون"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]
• وايسشتاين، إريك دبليو. "نظرية ويلسون". MathWorld .
• إثبات نظام الميزار : http://mizar.org/version/current/html/nat_5.html#T22
• أوهانا، أندرو. "تعميم لنظرية ويلسون" (PDF) .