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

به عنوان مثال اعداد 2و3و5و7 اول و اعداد 12و18و325 مرکب می باشند.
  • لازم به ذکر است که عدد یک نه اول و نه مرکب است و تنها عدد اول زوج عدد 2 است.
اگر n عددی مرکب باشد می توان گفت:
  • نتیجه: اگر P عددی اول . a و b اعدادی طبیعی باشند، در این صورت:

برهان:
چون P عددی اول است بنابراین تنها دو مقسوم علیه متمایز دارد. از اینکه P=ab و a<b نتیجه می شود 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
تجزیه استاندارد یک عدد:
اگر n>1 عددی طبیعی باشد آنگاه عدد n را می توان به شکل یکتایی به صورت:

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

  • توجه: بزرگترین توان که: را به صورت می دهند.
به عنوان مثال تجزیه استاندارد 12 به عوامل اول به صورت مقابل است: