بانك آموزشي درسي و رباتيك

تعریف اعداد اول:

پی یر فرما دانشمند قرن هفدهم اولین کسی بود که در خصوص اعداد اول این چنین نوشت: مقصود از اعداد اول(مثبت) عددی است بزرگتر از واحد که بر هیچ عددی غیر از یک و خودش قابل تقسیم نباشد(مقصود تقسیم بدون باقیمانده است) مثلا اعداد 1،2،3،5،13،17 عدد اول هستند و همچنین اعداد 257،65537. لیکن عدد 4294967297 عدد اول نیست زیرا عدد بر 641 قابل تقسیم است. نکته زیر در زندگی پی یر فرما در تاریخ ریاضیات دارای اهمیت بزرگی است. اگر اعداد 3،5،17،257،65537 را در نظر گیریم، همه این اعداد دارای وجه مشترک خاصی هستند زیرا همگی متعلق هستند به سلسلۀ خاصی از اعداد که طبق قانون ساده ای بوسیلۀ 1،2 ساخته می شوند از این قرار است:

1+2⁴=17          ،          1+2²=5          ،          1+2¹=3

1+2¹⁶=65537         ،          1+2⁸=257

باین طریق هفت عدد از اعداد این سلسله را بعنوان مثال ذکر کردیم و چنانکه دیدیم از این هفت عدد پنج تای اولی از آنها اعداد اول هستند و حال آنکه دو عدد آخری عدد اول نیستند.

تعریف دیگری از اعداد اول: عدد طبیعی p و p>1 را اول نامند به شرطی که تنها مقسوم علیه های مثبت آن 1 و p باشند. اگر عددی طبیعی و بزرگتر از 1 اول نباشد، مرکب است و عدد 1 جزء اعداد استثناء است که نه اول است و نه مرکب. عدد یکان اعداد اول بزرگتر از 10 فقط ممکن است اعداد 1،3،7،9 باشد.

بدون شک علاقه مندی ریمان به اعدا اول باعث انتشار کتابی در این زمینه شد که در آن فرضی دارد به نام "دربارۀ تعداد اعداد اولی که کوچکتر از مقدار معلومی هستند" که این فرضیۀ ریمان در مجلۀ آکادمی برلین شمارۀ ماه نوامبر 1859 به چاپ رسیده است که ریمان این دانشمندی که در قرن هجدهم می زیست در آن زمان سی وسه ساله بود.

همچنین وقتی که لازم باشد آنرا بین سایر اعداد اول مشخص نمایند، به آن عدد، عدد اول مطلق گویند. با شناسائی جدول فیثاغورث می توانیم اعداد اول کوچکتر از 100 را بلافاصله بنویسیم. باید گفت تنها عدد صحیح غیر اولی که عوامل اول آن در نظر اول شناخته نمی شود: 13×7=91 می باشد. تعداد اعداد اول کوچکتر از 100 مساوی 25 است که 15 عدد از این اعداد اول بین 1،50 وتنها 10 عدد آنها بین 51 تا 100 قرار گرفته است. این یک مثال ساده از نزولی بودن تعداد اول در مقیاس اعداد صحیح است. باید گفت بزرگترین عدد اول کشف شده تا به امروز برابر 1-2^32582657 است که این عدد به عدد مرسن مشهور است.

غربال آراتوستن: فرض کنید که بخواهیم اعداد اول کوچکتر از 1000 را معین کنیم. ابتدا اعداد را کنار هم می­گذاریم یعنی از 1 تا 1000 را می نویسیم سپس بعد از این کار مضارب3،2 را از مجموعۀ اعداد حذف می کنیم البته بدون حذف خود دو عدد یعنی 3،2 به این ترتیب اعداد باقیمانده از مجموعۀ اعداد نوشته شده اعداد اول کمتر از 10000 است.

مثال:اعداد اول کمتر از 20 را بدست می آوریم.(به روش غربال اراتوستن)

 10  9   8   7   6   5   4  3   2  1

20  19  18  17  16  15  14  13  12  11

قضایای مربوط به اعداد اول:

قضیه1: بی نهایت عدد اول وجود دارد.( این قضیه مشهور است به حدس اعداد اول مرسن)

برهان: حکم را به روشی که منسوب به اقلیدس است ( برهان خلف) اثبات می کنیم. فرض کنید تعداد متناهی اعداد اول وجود دارد که تعداد آنها nتا می باشد، حال عدد m را که برابر حاصلضرب این اعداد بعلاوۀ 1 را در نظر بگیرید. این عدد مقسوم علیه ای غیر از آن n عدد دارد که با فرض در تناقض است.

            P₁P₂…P_n                           P₁P₂…P_n +1>p_i

P₁P₂...P_n>P_i                               P₁P₂…P_n +1=P_i1...P_ik

                                          P₁P₂…P_n +1=P_i .x

                                          P_i1...P_ik= P_i .x

                                          P₁P₂…P_n +1= y+1

                                          P_i1.y+1= P_i1.x

                                          P_i1.x-P_i1.y=1

                                          P_i1.(x-y)=1

                                          P_i1=1    

که به تناقض رسیدیم پس حکم ثابت است .

اثبات قضیۀ 1 به گونه ای دیگر توسط کومر در سال 1878 میلادی صورت گرفت، این اثبات، اثباتی بسیار زیباست که در عین سادگی نکات جالبی را دربردارد.

اثبات: فرض کنید که همه اعداد اول موجود متناهی و به ترتیب زیر باشند:    P₁₂<…_r  قرار می دهیم، P=P₁P₂…P_r>2 اگر اعداد صحیح P-1 دارای عاما مشترک P_i با P باشد آنگاه P_i عامل P-(P-1)=1 است که ناممکن می باشد لذا P-1 عامل اولی به غیر از آنچه ذکر شد دارد که تناقضی آشکار با اثبات است.

قضیۀ2: قضیۀ اساسی حساب: هر عدد طبیعی بزرگتر از 1 را به شکل حاصلضرب اعدادی اول نوشت.

این قضیه از قضایای مهم نظریه اعداد است که نشان می دهد اعداد اول چگونه همانند بلوک های ساختمانی در ساختن سایر اعداد نقض دارند. این قضیه به طور ساده بیان می کند، هر عدد صحیح بجز 1 و 1- به صورت حاصلضربهایی از عوامل اول قابل نمایش هستند. همچنین این نمایش اعداد به صورت حاصل ضرب عوامل اول، صرف نظر از ترتیب عوامل یکتاست. به عنوان مثال عدد 60 را می توان به صورت 60=2×2×3×5 به حاصل ضرب عوامل اول نوشت. اگر عدد n را به صورت n=P₁P₂…P_r به حاصل ضرب عوامل اول بنویسیم، این کار را اصطلاحا تجزیه عدد n به عوامل اول می گوییم. پس قضیۀ اساسی حساب بیان می کند هر عدد صحیح 1 و 1- قابل تجزیه به عوامل اولند و این تجزیه صرف نظر از ترتیب عوامل اول یکتاست. اصطلاح تجزیه به عوامل اول می تواند اطلاعات زیادی را در مورد مقسوم علیه های آن عدد و به طور کلی ساختار آن عدد در اختیار ما بگذارد. باید توجه داشت که از نظر تاریخی این قضیه اساسا توسط اقلیدس به اثبات رسیده است اما اولین اثبات کامل این قضیه توسط گاوس در کتاب تحقیقات حساب منتشر شده است. همچنین با گسترش جبر مجرد و نظریۀ حلقه مفهومی مشابه در نظریۀ حلقه به عنوان حوزه تجزیه یکتا  (VFD) بوجود آمد که در آنها خاصیتی مشابه برقرار است که توسط کومر و زمانی که به روی قضیۀ آخر فرما کار می کرد معرفی شد. این نشان می دهد که اگرچه قضیۀ اساسی حساب در حلقۀ اعداد صحیح بدیهی جلوه می کند اما چنین چیزی در مورد هر حلقه دلخواه بدیهی نیست و ممکن است نادرست باشد.

قضیه3:

قضیۀچیشف: اگر n عددی طبیعی  بزرگتر از 2 باشد حتما بی n و 2n عدداولی وجود دارد.

قضیه 4:

حدس گلدباخ: هر عدد زوج را میتوان بصورت جمع دو عدد اول نوشت.

قضیه 5:

هر عدد فرد(شامل اعداد اول) را میتوان بصورت جمع 3 عدد اول نوشت.

قضیه6:

هر عدد فرد را میتوان بصورت دو برابریک عدد اول بعلاوه یک عدد اول دیگر نوشت.

خواص اعداد اول: مجذور هر عدد اول برابر است با 24n+1

فرما که در قرن 17 می زیست و پایه گذار حساب احتمالات بود بعد از کشف اعداد اول قضیه ای به نام (آخرین قضیۀ فرما) از او باقی مانده است که تا امروز به طور کل ثابت نشده است. قضیۀ دیگری از فرما که به قضیۀ فرما شهرت یافته است، یکی از خواص اساسی مربوط به اعداد اول را بیان می کند، به صورت زیر است:

A^p-1≡1 (mode p)         →         p│a^p-1-1