عدد اول

اعداد اول:

تعریف:
عدد طبیعی P>1 را عدد اول می گویند هرگاه تنها مقسوم علیه های مثبت آن 1 و P باشند. به عبارت دیگر یک عدد طبیعی اول است هرگاه جز یک و خودش بر هیچ عدد دیگری بخش پذیر نباشد.
هر عدد طبیعی مخالف یک که اول نباشد مرکب یا تجزیه پذیر می گوییم.
به عنوان مثال اعداد 2و3و5و7 اول و اعداد 12و18و325 مرکب می باشند.

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

اگر n عددی مرکب باشد می توان گفت:

نتیجه: اگر P عددی اول . a و b اعدادی طبیعی باشند، در این صورت:

برهان:
چون P عددی اول است بنابراین تنها دو مقسوم علیه متمایز دارد. از اینکه P=ab و aنتیجه می شود a , b دو مقسوم علیه متمایز P می باشند چون: a|P ,b|P و بنابر تعریف a=1 , b=P خواهد بود.

حال به بیان چند قضیه مهم در باره اعداد اول می پردازیم:
قضیه 1) هر عدد صحیح بجز یک و منفی یک دارای حداقل یک مقسوم علیه اول است.

برهان:
فرض می کنیم a عددی صحیح باشد که مخالف یک و منفی یک است. اگر a=0 باشد در این صورت تمامی اعداد صحیح از جمله اعداد اول a را می شمارند و حکم برقرار است. حال فرض می کنیم a مخالف صفر باشد و نشان می دهیم a دارای حداقل یک مقسوم علیه اول است. برای این منظور مجموعه مقسوم علیه های مثبت و بزرگتر از یک a را به این صورت تعریف میکنیم:

مجموعه S ناتهی است چرا که:

پس:

. از طرفی دیگر مجموعه S زیرمجموعه اعداد طبیعی است پس بنابر اصل خوشترتیبی S دارای عضو ابتدا(مینیمم) چون P است.

نشان می دهیم که P عددی اول است. برای اثبات ادعا از برهان خلف استفاده می کنیم:
به برهان خلف فرض می کنیم P عددی اول نباشد، پس P عددی مرکب است لذا:

,این نتیجه می دهد:

از طرفی دیگر:

که این نتیجه می دهد:

.
و این با مینیمم بودن P در تناقض است چون:

و لذا فرض خلف باطل و چنین نیست که P اول نباشد پس P اول است. به این ترتیب نشان داده شد عدد a حد اقل یک مقسوم علیه اول دارد.

قضیه 2) بی نهایت عدد اول وجود دارد.

برهان:
برای اثبات این قضیه از برهان خلف استفاده می کنیم. به برهان خلف فرض می کنیم تعداد اعداد اول متناهی باشد و به فرض

تنها اعدد اول موجود باشند. قرار می دهیم:

بوضوح M بزرگتر از یک و طبیعی است پس بر طبق قضیه قبل می توان گفت M دارای حداقل یک مقسوم علیه اول است و چون تعداد اعداد اول موجود محدود است آن مقسوم علیه اول یکی از اعداد

است به فرض عضوی چون:

داریم:

که این با اول بودن

در تناقض است چون

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

لازم به توضیح است که این قضیه نخستین بار توسط اقلیدس در حدود سال 300 قیل از میلاد اثبات گردیده است.
قضیه 3) هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی است.

برهان
چون n مرکب است پس:

حال نشان می دهیم که:

به برهان خلف اگر:

آنگاه

و در نتیجه:

که این تناقض است و لذا فرض خلف باطل و حکم برقرار است یعنی:

حال چون a بزرگتر از یک است پس a دارای حداقل یک مقسوم علیه اول مانند p است. داریم:

و از سوی دیگر:

پس p عددی اول است که در شرایط قضیه صدق می کند و لذا حکم برقرار است.

لازم به توضیح است که قضیه فوق اساس روش غربال اراتستن است.

قضیه4) اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد. (قضیه چپیشف)

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

هر عدد طبیعی بزرگتر از یک را می توان به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت.
به عبارت دیگر اگر n عددی طبیعی و بزرگتر از 1 باشد:

که در آن

ها اعداد اول متمایر می باشند.
این نمایش را تجزیه عدد n به عوامل اول می گوییم.

همچنین اگر n<-1 باشد باز هم می توان n را به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت:

که در آن

ها اعداد اول متمایز می باشند.

توجه: اگر n=1 باشد آنگاه که در ان P هر عدد اولی است.
لازم به توضیح است که ممکن است در تجزیه یک عدد طبیعی به عوامل اول، تعدادی از عوامل یکسان باشند. به عنوان مثال:12=2×2×3