قضیه ویلسون؛ تشخیص عدد اول با فاکتوریل پیمانهای
آموزش قضیه ویلسون، شرط لازم و کافی اولبودن و محاسبه باقیمانده فاکتوریلها در تست نظریه اعداد.
پاسخ کوتاه
قضیه ویلسون یک معیار لازم و کافی برای اولبودن میدهد: عدد صحیح n>1 اول است اگر و تنها اگر (n-1)! در پیمانه n با منفی یک همنهشت باشد. این قضیه برای اثبات و تستهای پیمانهای مفید است، هرچند برای آزمون عملی اعداد بسیار بزرگ سریع نیست.
بیان قضیه
برای n>1 داریم n اول است اگر و تنها اگر (n-1)!≡-1 mod n. شکل معادل میگوید (n-1)!+1 بر n بخشپذیر است؛ هر دو جهت قضیه اهمیت دارند و امکان اثبات اول یا مرکب بودن را میدهند.
ایده اثبات برای عدد اول
در پیمانه اول p، هر عدد ناصفر وارون ضربی یکتا دارد. عددهایی که با وارون خود متفاوتاند جفت میشوند و حاصل هر جفت یک است؛ فقط 1 و -1 خودواروناند، پس حاصل همه اعداد 1 تا p-1 برابر -1 میشود.
جهت عکس
اگر n مرکب باشد، معمولاً عاملهای غیرtrivial آن در (n-1)! حضور دارند و حاصل فاکتوریل با منفی یک همنهشت نمیشود. استدلال دقیق حالتهای ویژه مانند n=4 را جدا کنترل میکند و در نهایت شرط ویلسون فقط برای اعداد اول برقرار میماند.
محاسبه فاکتوریل بزرگ
به جای ضرب کامل، جملههای نزدیک پیمانه را به اعداد منفی کوچک تبدیل کن. همچنین از ویلسون میتوان برای سادهکردن بخشهایی مانند (p-2)! استفاده کرد؛ چون (p-1)(p-2)!≡-1 و p-1≡-1، نتیجه (p-2)!≡1 است.
مثال حلشده
برای p=7، مقدار 6!=720 در تقسیم بر 7 باقیمانده 6 یعنی -1 دارد و شرط ویلسون برقرار است. برای n=8، مقدار 7! بر 8 بخشپذیر است و باقیمانده صفر، نه 7، پس 8 اول نیست.
دام تستی
قضیه کوچک فرما برای پایههای نسبت اول یک شرط لازم میدهد، اما عکس ساده آن همیشه اولبودن را تضمین نمیکند. ویلسون شرط لازم و کافی است؛ با این حال محاسبه فاکتوریل کامل معمولاً باید با همنهشتی و جفتسازی کوتاه شود.
چکلیست حل تست
- در ویلسون باقیمانده باید n-1 باشد.
- عددهای واروندار را در پیمانه اول جفت کن.
- برای محاسبه، جملههای نزدیک p را منفی بنویس.