اعداد اول (تعریف)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 27 مرداد 1400
دسته‌بندی: نظریه اعداد
امتیاز:
بازدید: 38 مرتبه

مقدمه‌ای بر اعداد اول

می‌خواهیم درباره دسته‌ای از اعداد طبیعی، مطالبی را بیان کنیم که شاید بحث‌انگیزترین و به‌نوعی جالب‌ترین اعداد طبیعی هستند.

اعدادی که تعدادشان بی‌نهایت است ولی تاکنون هیچ قاعده خاصی برای تولید آنها به‌دست نیامده است و حتی چگونگی توزیع آنها بین اعداد طبیعی، مشخص نشده است.

می‌دانیم هر عدد صحیح a±1 حداقل دارای چهار شمارنده ±1 و ±a است.

برای سهولت بی‌آن‌که به کلیت لطمه‌ای وارد شود، اعداد اول را فقط برای اعداد صحیح مثبت تعریف می‌کنند.

در این‌جا می‌خواهیم تا یکی از اساسی‌ترین قضایای تئوری اعداد یعنی قضیه‌ای به‌نام قضیه بنیادی حساب را ثابت کنیم.

یادآوری

این قضیه بیان‌گر آن است که هر عدد طبیعی بزرگ‌تر از 1 را می‌توان به‌صورت حاصل ضرب اعداد اول نمایش داد.

در واقع برطبق این قضیه، نقش بنیادی اعداد اول آشکار می‌شود، چنان‌چه همه اعداد، از اعداد اول به‌وجود آمده‌اند.

در اصطلاح ریاضیدانان، اعداد اول بلوک‌های ساختمانی اعداد می‌باشند و به همین دلیل این اعداد، آنان را شیفته خود کرده است.

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

عدد طبیعی p>1  را اول گویند، هرگاه شمارنده های مثبت آن 1 و p  باشند.

نکته

1- هر عدد طبیعی بزرگ‌تر از یک را که اول نباشد، تجزیه پذیر یا مرکب می‌گوییم.

به‌عنوان نمونه 11,7,5,3,2 اعداد اول هستند و 50,24,9 اعداد مرکب هستند.


2- عدد 1 نه اول است و نه مرکب. 

بعدها خواهیم دید که پذیرفتن عدد 1 در زمره اعداد اول نه تنها فایده‌ای ندارد حتی اختلالی د‌ر یکتایی تجزیه هر عدد صحیح به عوامل اول هم ایجاد می‌کند.


3- اگر p عدد اول و m>0 و m|p آن‌گاه m=1 یا m=p است.


4- اگر p عدد اول باشد، طبق تعریف فقط تجزیه بدیهی دارد یعنی (p=1×p) و فاقد تجزیه نابدیهی است. 

هر عددی مانند a دارای یک تجزیه بدیهی a×1 می‌باشد.

به‌عنوان نمونه عدد 12 یک تجزیه بدیهی به‌صورت 12×1 دارد و تجزیه های غیر بدیهی و جدی آن عبارتند از :

6×22×63×44×3


5- گزاره زیر را در نظر بگیرید:

if p=aba=1     b=p

این گزاه نشان می‌دهد که عدد اولیه جز تجزیه بدیهی 1×p تجزیه نابدیهی ندارد و این بیان‌گر آن است که اعداد اول، اعدادی ساده و بسیط هستند. 


6- اگر اعداد اولی مانند pk  ,  ...  ,  p2  ,  p1 بتوان یافت به‌طوری‌که n=p1.p2...pk در این‌صورت می‌گویندn به عوامل اول تجزیه شده است.

به‌عنوان نمونه هیچ یک از حاصل ضرب های 12×13×46×2 یک تجزیه عدد 12 به عوامل اول نیست، اما 2×2×3 تجزیه 12 به عوامل اول است.


7-گاهی عددی را عدد اول مطلق گویند وقتی که لازم باشد، آن‌را بین سایر عددهای اول مشخص کنند.

دریافت مثال

قضایای اعداد اول

قضیه

اگر p و q دو عدد اول باشند: 

if  pq    qpp=q

اثبات

p|qp=1p=q   if  p1  p=q

قضیه

لم

اگر p عددی اول و a یک عدد صحیح دل‌خواه باشد، در این‌صورت:

(a,p)=p    (a,p)=1

اثبات

فرض کنیم d=(a,p) بنابراین خواهیم داشت:

d=(a,p)d|pd=1d=p(a,p)=1(a,p)=p

نکته

از قضیه فوق، نتایج زیر حاصل می‌شود:

1- اگر p عددی اول باشد در این‌صورت: 

p1a(p,a)=1

با توجه به لم فوق معلوم است که برای یافتن ب‌م‌م عدد اول p و یک عدد صحیح دل‌خواه مانند a فقط به‌یک بار تقسیم کردن نیاز داریم، اگر باقیمانده تقسیم a بر p مساوی صفر شود، ب‌م‌م همان p است و اگر باقیمانده صفر نشود، ب‌م‌م مساوی 1 است.


2- اگر p عددی اول باشد، هر یک از اعداد p1,.....,3,2,1 و در نتیجه حاصل ضرب آنها یعنی: 

1×2×3×...×(p1)

نسبت به p اول می‌باشد.

p,1=1p,2=1p,3=1     p,p1=1p  ,1×2×3×...×(p1)=1


3- اگر p و q دو عدد اول متمایز باشند، در این‌صورت دو عدد نسبت به هم اولند یعنی:

p,q=1

قضیه

اگر p عددی اول باشد، آن‌گاه:

if  p|ab  p|a    p|b

اثبات

اگر p|a حکم ثابت است در غیر این‌صورت فرض می‌کنیم p|a بنابراین (p,a)=1 لذا بنابر لم اقلیدس:

p|ab  ,  (p,a)=1  p|b

نکته

از قضیه فوق، نتایج زیر حاصل می‌شود:

1- اگر p عددی اول باشد، آن‌گاه:

p|a1a2...anp|a1    p|a2    .....    p|an

دریافت مثال

نکته

2- اگر p عددی اول باشد، آن‌گاه: 

p|anp|a

دریافت مثال

قضیه

هر عدد طبیعی n>1 حداقل دارای یک شمارنده اول است.

اثبات

هر عدد طبیعی n>1 را در نظر می‌گیریم، مجموعه تمام شمارنده های بزرگ‌تر از 1 این عدد را با S نشان می‌دهیم، یعنی:

S=a|   a>1  ,  a|n

چون nZ می‌باشد پس S تهی نیست، در نتیجه بنابر اصل خوش ترتیبی دارای عضو ابتدا است که آن‌را p می‌نامیم و ثابت می‌کنیم p اول است. 

از آن‌جا که هر شمارنده p یک شمارنده n نیز می‌باشد، اگر p اول نباشد در این‌صورت S عضوی کوچک‌تر از p خواهد داشت که این تناقض است، بنابراین p اول است.   

مجددا یادآوری می‌کنیم که اگر p اول باشد، خود p تجزیه عدد اول p به عوامل اول است.

قضیه

قضیه بنیادی حساب

هر عدد طبیعی n>1 را می‌توان به عوامل اول تجزیه کرد و این تجزیه بدون درنظر گرفتن ترتیب قرار گرفتن عوامل، منحصربه‌فرد است. 

اثبات

عدد n یا اول است یا مرکب است.

اگر n اول باشد، چیزی برای اثبات نمی‌ماند.

اگر n مرکب باشد، در این‌صورت بنا به قضیه‌ای که قبلا بیان شده، n حداقل دارای یک شمارنده اول مانند p1 است، بنابراین می‌توان نوشت:

n=p1n1   ;    1<n1<n

به‌همین ترتیب در مورد n2 عمل می‌کنیم.

چون n>n1>n2>...>1 پس این روند نمی‌تواند بی‌نهایت بار تکرار شود و بالاخره یکی از nk ها عدد اولی مانند pk است و لذا خواهیم داشت:

n=p1p2...pk

در این قسمت از اثبات یکتایی تجزیه صرف نظر می‌کنیم.

نکته

1- هر عدد طبیعی n>1 را به‌طور منحصر به‌فردی می‌توان به‌صورت زیر نمایش داد:

n=p1α1.p2α2...ptαt

که در آن αi ها اعداد طبیعی و pi ها اعداد اول متمایزی می‌باشند به‌طوری‌که p1<p2<...<pt.


2- تجزیه استاندارد یا کانونیک عدد n به‌صورت زیر است:  

n=p1α1.p2α2...ptαt=i=1tpiαi

توجه کنید در تجزیه یک عدد طبیعی به اعداد اول، از هر عدد اولی چون pi به‌صورت pi0 می‌توانیم استفاده کنیم، به‌عنوان نمونه داریم:

18=21×32×50×70×...

ممکن است تعدادی از عوامل اول تجزیه، با هم مساوی باشند، به‌عنوان نمونه داریم:

360=2×2×2×3×3×5=23×32×5

یادآوری

اگر a و b دو عدد طبیعی بوده و پس از تجزیه به عوامل اول به‌صورت تجزیه می‌شود:

a=p1α1×  p2α2  ...×pkαkb=p1β1×p2β2  ...  ×pkβk

حالت اول- ب‌م‌م به‌صورت زیر محاسبه می‌شود: 

d=(a,b)=p1θ1p2θ2...pkθk    ;    θi=minαi,βi

منظور آن است که ب‌م‌م دو عدد همان عامل های مشترک دو عدد با توان کوچک‌تر است.

به‌عنوان نمونه داریم:

36=22×3284=22×3×7(36,84)=22×3=12


حالت دوم- ک‌م‌م به‌صورت زیر محاسبه می‌شود: 

C=[a,b]=p1θ1p2θ2...pkθk    ;    θi=maxαi,βi

منظور آن است که ک‌م‌م دو عدد همان عامل های مشترک دو عدد با توان بزرگ‌تر ضرب در عامل های غیر مشترک می‌باشد.

به‌عنوان نمونه داریم:

36=22×3284=22×3×7[36,84]=22×32×7

دریافت مثال

قضیه

عدد اول زوجی به‌جز عدد 2 وجود ندارد. 

اثبات

اگر n2 عددی زوج باشد، در این‌صورت 2|n در نتیجه عاملی به‌جز 1 و خودش دارد، پس اول نیست.

قضیه

هیچ دو عدد اول و متوالی به‌جز 2 و 3 وجود ندارد.

اثبات

اگر فرض کنیم p عددی اول و p3 باشد، در این‌صورت بنا به قضایای مطرح شده p زوج نیست و فرد می‌باشد در نتیجه p+1 باید زوج باشد، که در این‌صورت اول نیست.

قضیه

اگر p عددی اول باشد و a عددی صحیح به‌طوری‌که p|a که در این‌صورت همواره p,a=1.

به‌عبارت دیگر عدد اول p نسبت به هر عددی که مضرب p نباشد، اول است.  

اثبات

فرض است که:

1|p  ,  p|paz  ,  p|a

فرض کنیم p,a=d پس ثابت می‌کنیم که d=1.  

d=(a,p)    d|pd=1d=pif    d=pd|ap|a

که با فرض p|a تناقض دارد پس d=1 است.  

دریافت مثال

تشخیص اول بودن یک عدد طبیعی

چگونه می‌توان تشخیص داد یک عدد مفروض، اول یا مرکب است؟

اگر مرکب است چگونه می‌توان یک شمارنده غیر بدیهی آن‌را یافت؟

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

اگر چه این روش بسیار ابتدایی و ساده است،اما یک راه حل عملی و مفید نیست زیرا برای اعداد نه‌چندان بزرگ هم مستلزم صرف وقت بسیاری هستیم.

اعداد مرکب دارای خاصیتی هستند که به‌طور محسوسی باعث کاهش محاسبات می‌شود هر چند حتی با این روش، فرآیند تشخیص اول بودن هم چنان خسته‌کننده و طاقت فرساست.

قضیه

اگر n یک عدد طبیعی مرکب باشد، در این‌صورت n شمارنده اولی مانند p دارد به‌طوریه‌که:

pn

اثبات

چون n مرکب است، بنابراین n را می‌توان به‌صورت حاصل ضرب زیر نوشت:

n=bc    ;    1<b<n  ,  1<c<n

if   bcb2bc    ;    bc=nb2nbn

از طرفی b>1 لذا دارای یک شمارنده اول مانند p است، بنابراین:

pbnp|b  ,  b|n  p|n

نکته

برای آزمودن اول بودن یک عدد معین مانند n>1 کافی است n را بر تمام اعداد اول کوچک‌تر یا مساوی n تقسیم کنیم، اگر n بر هیچ یک از این اعداد اول بخش پذیر نبود، n اول است.

دریافت مثال

قضیه

قضیه اقلیدسی

بی‌نهایت عدد اول وجود دارد، به‌عبارت دیگر مجموعه اعداد اول نامتناهی است. 

اثبات

اساس کار در اثبات قضیه این است که هیچ فهرستی متناهی از اعداد اول وجود ندارد

در واقع اگر در مجموعه ...  ,p4=7  ,  p3=5  ,  p2=3  ,   p1=2  یک عنصر انتها مانند pk وجود داشته باشد، عدد زیر را در نظر می‌گیریم:

N=(p1p2...pk)+1

چون N>1 لذا دارای یک شمارنده اول مانند p است.

چون pk  ,  ...   ,  p2  ,  p1 را تمام اعداد اول فرض کرده‌ایم لذا p که از pk هاست، بنابراین: 

p|p1p2...pkp|Np1p2...pkp|1  p=1

که این ناممکن است بنابراین مجموعه اعداد اول نامتناهی است.

دریافت مثال

توزیع اعداد اولی

با این‌که بی‌نهایت عدد اول وجود دارد، توزیع اعداداول در مجموعه اعداد طبیعی پر رمز و راز است.

در مورد توزیع اعداد اول دو واقعیت وجود دارد. 

واقعیت اول- این‌که اعداد اول علیرغم تعریف ساده و نقش خود به‌عنوان مصالح ساختمانی، خودسرترین و بی‌نظم‌ترین مقوله‌هایی هستند که مورد مطالعه ریاضیدانان قرار گرفته‌اند و مانند علف‌های هرز در میان اعداد طبیعی رشد می‌کنند و به نظر می‌رسد از هیچ قاعده‌ای جز قاعده تصادف پیروی نمی‌کنند و هیچ کس نمی‌تواند پیش‌بینی کند عدد اول بعدی در کجا سبز خواهد شد. 

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

تعریف- دو عدد اول را دوقلو گویند هرگاه اختلاف آن دو مساوی 2 باشد.

به‌عنوان نمونه 5,7 و 11,13 نمونه‌هایی از زوج اعداد دوقلو هستند.  

هنوز در مورد نامتناهی یا متناهی بودن زوج‌های اعداد دوقلو به نتیجه‌ای دست نیافته‌اند.

وجود اعداد دوقلو در میان اعداد اول، نشان‌گر آن است که اعداد اول تا چه حد می‌توانند نزدیک هم باشند.

از طرف دیگر در زیر نشان می‌دهیم که در میان اعداد اول شکاف‌های عظیمی وجود دارد.

نکته

شکاف‌هایی به‌اندازه دل‌خواه بزرگ در مجموعه اعداد اول وجود دارد.

به‌عبارت دیگر، برای هر عدد طبیعی n، n عدد متوالی وجود دارند که همگی مرکب هستند.

به‌عنوان نمونه:

n عدد متوالی زیر را در نظر می‌گیریم:

(n+1)!+2  ,  ...   ,  (n+1)!+3  ,  (n+1)!+n

نشان می‌دهیم همه این اعداد مرکب‌اند:

(n+1)!+2=1×2×...×(n+1)+2=2k+2

یعنی (n+1)!+2 بر 2 بخش پذیر است. 

n+1!+3=1×2×3×...×n+1+3=3k+3

یعنی (n+1)!+3 بر 3 بخش پذیر است. 

به‌همین ترتیب می‌توان نشان داد که عدد زیر بر k بخش پذیر است:

n+1!+k    ;    2kn+1

به‌عنوان نمونه اگر بخواهیم چهار عدد متوالی نشان دهیم که در میان آنها هیچ عدد اولی وجود ندارد، خواهیم داشت:

5!+2=122=2×615!+3=123=3×415!+4=124=4×315!+5=125=5×25

توابع مولد اعداد اول

توابع مولد اعداد اول توابعی هستند که به ازای هر nN عدد اول تولید می‌کند.

تابع زیر را در نظر بگیرید:  

f(n)=n2+n+11

این تابع به‌ازای 9 عدد متوالی، اعداد اول و به ازای n=10 و n=11 عدد مرکب تولید می‌کند، یعنی این تابع، یک تابع مولد اعداد اول نیست.

سال‌های بسیاری در قرون وسطی تصور می‌کردند که که سه‌جمله‌ای درجه دوم f(n)=n2+n+41 فقط عدد اول تولید می‌کند، در صورتی‌که معلوم شد تابع درجه دوم فوق به ازای n=0  ,    ,  39 عدد اول تولید می‌کند اما به‌ازای n=40 اول نیست.

نکته

دانشمندی به‌نام دیریکله ثابت کرد اگر a و b نسبت به‌هم اول باشند، a+kb بی‌نهایت عدد اول تولید می‌کند، با این همه، هیچ عبارتی به‌صورت a+kb وجود ندارد که فقط اعداد اول تولید کند.  

اعداد مرسن 

در ریاضی سنت شده است که اعداد به‌صورت Mn=2n1 را به‌مناسبت نام کشیش فرانسوی مارین مرسن اعداد مرسن نامیده می‌شود، چرا که مرسن در زمینه اول بودن این نوع اعداد اظهار نظری نادرست اما محرک کرده بود.

در سال 1644 مرسن اظهار داشت که Mp=2p1 به‌ازای اعداد زیر اول هستند:

p=2,  3,  5,  7,  13,  17,  19,  31,  67,  127,  257

به‌ازای سایر اعداد p<257 مرکب است.

ریاضیدانان معتقدند که به‌طور قطع مرسن تمامی اعدادی را که اول بودن آنها را ادعا کرده آزمایش نکرده است.

تمرین

اگر 2n-1 اول باشد، نشان ‌دهید که n  اول است.

اثبات با عکس نقیض:


فرض کنید n اول نباشد، بنابراین n دارای تجزیه غیربدیهی n=rs است و S<n و r>1 است، حال می‌توان نوشت:

2n1=2rs1=2rs1=2r12rs1++1


واضح است که هر یک از عوامل فوق از 1 بزرگ‌تر هستند.

یعنی 2r-1 دارای تجزیه غیربدیهی است که این خلاف اول بودن 2n-1 است. 

اعداد فرما 

قرار است یک نوع از اعداد را بررسی کنیم که منبعی غنی از حدس‌ها در ریاضیات است.

این اعداد، حالت خاصی از اعداد به‌صورت 2m+1 می‌باشند.

هر عدد فرما عددی است به‌صورت عدد زیر:

Fn=22n+1    ;    n0

اگر Fn اول باشد، آن را عدد اول فرما گویند.

فرما که اغلب حدس‌هایش برای ریاضیدانان درخور توجه و قابل اعتماد بود، مشاهده کرد که:

F0=220+1=3  F1=221+1=5F2=222+1=17      F3=223+1=257F4=224+1=65/537   

همگی اول هستند، لذا تصور کرد که همه Fn اولند، در نامه‌ای که به مرسن نوشت اعلام کرد من اعدادی به‌صورت 22n+1 یافته‌ام که همیشه اولند و ریاضیدانان سال‌ها بعد درستی آن‌را خواهند فهمید.

اما در سال 1732  اولر نشان داد که:

F5=225+1=4,294,967,297

بر 641 بخش پذیر است، بدین ترتیب خط بطلانی بر ادعای فرما کشید.

مثال‌ها و جواب‌ها

اعداد اول (تعریف)

3,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید