قضیه کوچک فرما

از ویکی‌پدیا، دانشنامهٔ آزاد.

قضیه کوچک فرما که برای تمایز آن با قضیه آخر فرما به این نام موسوم است بیان می کند اگر یک عدد p اول و a عددی صحیح باشد که p\not |a دراین صورت a^{p-1}\equiv 1 \pmod{p}.

این قضیه،اساسی برای آزمون اول بودن فرما است. از این قضیه می توان در یافت مرتبه هر عدد متباین با p به هنگ p برابراست با یک. بیانی دیگر از قضیه کوچک فرما نیز وجود دارد که بیان می کند اگر p عددی اول و a عددی صحیح باشد آنگاه a^p\equiv a \pmod{p}.

فهرست مندرجات

[ویرایش] تاریخچه

پیر دو فرما اولین بار این قضیه را در 18 اکتبر سال 1640 با دوست و محرم اسرار خود فرانکل بسی (Frénicle de Bessy) مطرح ساخت و بیان کرد:

«وقتی که p عدد اول است و a نسبت به p متباین ap-1 بر p بخشپذیر است. »

طبق معمول فرما این ادعا را اثبات نکرد و تنها بیان کرد این گزاره درست است. نخست اویلر در سال 1736 اثباتی برای این قضیه را در مقاله ای با عنوان "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio", منتشر ساخت اما مشخص شد لایب نیتز اثباتی مشابه را در یک دست نوشته منتشر نشده از قبل در حدود سال 1683 انجام داده است.

اصطلاح قضیه کوچک فرما (Fermat's little theorem) اولین بار در سال 1913 توسط کورت هنسل (Kurt Hensel) استفاده شد. او بیان کرد:

« یک قضیه اساسی وجود دارد که در هر گروه متناهی برقرار است که معمولاً قضیه کوچک فرما گفته می شود چرا که فرما اولین فردی بوده است که بخش خاصی از آن را اثبات کرده است.»

این عبارت اولین بار در انگلیس در مقاله اروین کاپلانسکی با عنوان «تست لوکاس برای اعداد مرسن» بیان شد.

همچنین ریاضیدانان چینی نیز به طور مستقل فرضیه هایی شبیه قضیه کوچک فرما را بیان کرده اند که معمولاً تحت عنوان فرضیه های چینی شناخته می شوند.

این فرضیه بیان می کند p اول است اگر و فقط اگر 2^p\equiv 2 \pmod{p}.

وضوحاً اگر p اول باشد 2^p\equiv 2 \pmod{p} که این حالتی خاصی از قضیه فرما است اما عکس مطلب یعنی اینکه « اگر 2^p\equiv 2 \pmod{p} آنگاه p اول است » نادرست است ولذا کل مطلب نادرست است.

این مطلب حدود 2000 سال قبل از آنکه فرما قضیه خود را مطرح کند بیان شده است.

[ویرایش] برهان

همانطور که گفته شد فرما در ابتدا قضیه را بدون اثبات ذکر کرده است و اولین اثبات قضیه را گودفرد ویلهلم لایب نیتز در یک دست نویس بدون تاریخ ارایه داده است. او نوشته است که اثبات قضیه را قبل از سال 1683 می دانسته است.

البته قضیه شکل خاصی از قضیه کلیتری موسوم به قضیه اویلر است که با اثبات آن در اصل اثبات قضیه فرما نیز انجام شده است اما در این قسمت برهان را مخصوص همین قضیه ارائه می دهیم.

مجموعه A = {1,2,3,...,p − 1} را در نظر می گیریم و فرض می کنیم a\in \mathbb{Z} چنان باشد که p\not |a .

چون مجموعه A یک دستگاه مخخف مانده ها به هنگ p است و a نسبت به p اول است مجموعه

B = {a,2a,3a,...,(p − 1)a}

نیز یک دستگاه مخفف مانده ها به هنگ p است و لذا بنابر تعریف:

1.2.3...(p-1)\equiv a.2a.3a...(p-1)a \pmod{p}

پس:

1.2.3...(p-1)\equiv [1.2.3...(p-1)]a^{p-1} \pmod{p}

لذا داریم:

a^{p-1}\equiv 1 \pmod{\frac{p}{(1.2.3...(p-1),p)}}

اما چون هر یک از اعداد موجود در A نسبت به p اولند پس حاصل ضربشان نیز نسبت به p اول است و لذا (1.2.3...(p − 1),p) = 1 پس:

a^{p-1}\equiv 1 \pmod{p}

و برهان حکم کامل است.

[ویرایش] تعميم قضيه فرما-قضيه اويلر

قضیه کوچک فرما حالتی خاص از قضیه اویلر است که بیان می کند اگر a عددی صحیح و m عددی طبیعی باشد که a,m)=1) آنگاه:

a^{\phi (m)}\equiv 1 \pmod{m}

به آسانی اگر قرار دهید m=p-1 قضیه فرما بدست می آید. بعلاوه این قضیه به این صورت نیز قابل تعمیم است که p عددی اول باشد و n,m اعدادی طبیعی باشند که m\equiv n \pmod{p-1} آنگاه a^m\equiv a^n \pmod{p} . این قضیه در تعریف اعداد RSA و رمز گذاری کاربرد فراوان دارد.

قضیه کوچک فرما در مطالعه اعداد RSA، رمزنگاری، آزمون های اول بودن و حل معادلات همنهشتی کاربرد فراوان دارند.

[ویرایش] همچنین ببینید

  • همنهشتی
  • معادلات همنهشتی
  • قضیه اویلر
  • قضیه ویلسون
  • قضیه هوستن هولم


[ویرایش] منابع

  • ویلیام دبلیو.آدامز-لری جوئل گولدشتین. آشنایی با نظریه اعداد. ترجمهٔ دکتر آدینه محمد نارنجانی. تهران: مرکز نشر دانشگاهی، 1384، ISBN 964-01-0070-6. ‏


  • مشارکت‌کنندگان ویکی‌پدیا، «Fermat's little theorem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد. (بازیابی در 24 آگوست 2007).
زبان‌های دیگر