اعداد اول اعدادی طبیعی هستند که بر هیچ عددی بجز خودشان و عدد ۱ بخش‌پذیر نباشند. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگرعددی طبیعی وبزرگ‌تر از ۱ اول نباشد مرکب است.
عدد یکان اعداد اول بزرگتر از ۱۰ فقط ممکن است اعداد ۱، ۳، ۷، ۹ باشد.
پیدا کردن ضابطه ای جبری برای اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها به دست نیاورده است.
دنبالهٔ اعداد اول به این صورت شروع می‌شود: ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹ ...
قضیه ۱: تعداد اعداد اول بی‌نهایت است.
برهان: حکم را به روشی که منسوب به اقلیدس است اثبات می‌کنیم: فرض کنید تعداد اعداد اول متناهی و تعداد آنها n تا باشد. حال عدد M را که برابر حاصلضرب این اعداد به علاوه ۱ را در نظر بگیرید. این عدد مقسوم‌علیهی غیر از آن n عدد دارد که با فرض در تناقض است.
قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی بزرگتر از ۱ را می توان به شکل حاصلضرب اعدادی اول نوشت.
قضیه ۳ (قضیه چپیشف):اگر n عددی طبیعی و بزرگتر از ۳ باشد، حتما" بین n و ۲n عدد اولی وجود دارد. قضیه ۴ هر عدد زوج را می‌توان بصورت جمع سه عدد اول نوشت.
قضیه ۵ هر عدد فرد (شامل اعداد اول) را می‌توان به صورت جمع سه عدد اول نوشت (اثبات بر پایه قضیه ۴)
قضیه 6-هر عدد فرد را می‌توان به صورت دو برابر یک عدد اول بعلاوه یک عدد اول دیگر نوشت (برهان آن را بنویسد).
خواص اعداد اول:
1- هر عدد اول برابر است با 6n+1 یا 6n-1 که n یک عدد صحیح است.
2-مجذور هر عدد اول برابر است با 24n+1.
3-تفاضل مجذورهای دو عدد اول مضربی از 24 است.
4-حاصلضرب هر دو عدد اول بجز 2و3 مضربی از 6 بعلاوه یا منهای یک است.
توان چهارم هر عدد اول بجز 2و3 مضربی از 240 بعلاوه یک است.
بزرگترین عدد اول کشف شده برابر دو به توان ۳۰میلیون و ۴۰۲هزار و ۴۵۷منهای یک است.این عدد یک عدد مرسن است. عدد مرسن عددی است که برابر 2 به توان n منهای یک است.
لازم به ذکر است که تعداد 3000 عدد اول در سایت مگاسندر www.megasender.org وجود دارد و افرادی که مایل به دریافت بیشتر این اعداد هستند می توانند با سایت مذکور تماس گرفته و تعداد بیشتری از آنها را بر روی لوح فشرده دریافت نمایند و طراحان این سایت خودشان این اعداد را محاسبه نموده اند
تاریخچه اعداد اول
در سال ۲۰۰۱دو تن از دانشجویان او یعنی کایال و سکسنا به یک نکته بسیار حساس و فنی توجه کردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندک اندک برایشان روشن شد که تنها یک مانع در راه تکمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد. مانع از این قرار بود که روش آنان تنها در صورتی کار می‌کرد که عدد اول مورد نظر که با pنمایش داده می‌شود همواره در محدوده خاصی جای داشته باشد که با اعدادی که در آزمون شرکت داده می‌شوند مرتبط باشد. مشخصه ویژه این مانع آن است که عدد " p-1 " باید یک مقسوم علیه یا بخشیاب بسیار بزرگ باشد. گروه سه نفر ریاضی دانان هندی برای غلبه بر مشکل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند که در سال ۱۹۸۵یک ریاضی‌دان فرانسوی به نام اتن فووری از دانشگاه پاریس ۱۱این نکته را به صورت ریاضی اثبات کرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد. اما این موفقیت "مشروط" بود. به این معنی که این روش برای اعداد اولی که انسان در حال حاضر می‌توان به سراغ آنها برود از کارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات که متناسب با ارقام عدد اول مورد نظر بود، با آهنگ ۱۰۱۲ازدیاد پیدا می کرد. در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ۱۰۷.۵کاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود که تعداد ارقام عدد اولی که قصد شکار و یافتن آن را داریم در حدود ۱۰۱۰۰۰باشد. اعدادی تا این اندازه بزرگ در حافظه هیچ کامپیوتر جای نمی‌گیرند و حتی آن را نمی‌توان در کل کیهان جای داد. اما حال که ریاضی دانان توانسته‌اند یک طبقه خاص از آلگوریتمهای توانی را برای شناسایی اعداد اول مشخص کنند، این امکان پدید آمده که به دنبال نمونه‌های بهتر این روش بگردند. پومرانس و هندریک لنسترا از دانشگاه کالیفرنیا در برکلی با تلاش در همین زمینه توانسته‌اند زمان لازم برای محاسبات را از توان ۷.۵به توان ۶کاهش دهند. این دو از همان استراتژی کلی گروه هندی موسسه کانپور استفاده کردند اما تاکتیهای دیگری را به کار گرفتند. اگر فرضیه‌های دیگری که درباره اعداد اول مطرح شده درست از کار درآید آنگاه می‌توان زمان محاسبه را از توان ۶به توان ۳تقلیل داد که در این حد این روش کارآیی عملی پیدا خواهد کرد. در این حالت یافتن اعداد اول با ۱۰۰۰رقم یا بیشتر به بازی کودکان بدل خواهد شد. اما در نظر ریاضی‌دانان مهمترین و جالبترین جنبه کار گروه سه نفره آ ک اس (کانپ.ر) روشی است که آنان به کار گرفته‌اند. اعداد اول برای ریاضیات از اهمیت بنیادین برخوردارند و هر نوع غفلت در فهم ویژگیهای آنها باعث می‌شود خللهای بزرگ در بنای ریاضیات پدیدار شود. روش این سه ریاضی دان هندی هرچند این خللها و نقصها را پر نکرده حداقل به ریاضی دانان گفته است که در کجا به دنبال این خللها بگردند. آلگوریتم پیشنهادی این سه محقق و همه انواع بدیلی که بر اساس آن ساخته شده متکی به وجود اعداد اولی با مشخصه های ویژه هستند. و در اغلب موارد استفاده از این روش مستلزم آن است که ریاضی دانان اطلاعات دقیقی از نحوه توزیع این قبیل اعداد اول خاص در میان دیگر اعداد به دست آورند و به این ترتیب جغرافیای مکانی اعداد اول را مشخص سازند. روش پیشنهادی آ ک اس به ریاضی دانان این نکته را آموخته که ویژگیهای این جغرافیای مکانی حائز اهمیت است و نیز این که هنوز دانش کافی در این زمینه به دست نیامده است. در گذشته و در زمانی که نظریه اعداد تنها مورد توجه یک گروه کوچک از ریاضی دانان بود ، این مساله چندان اهمیتی نداشت. اما در ۲۰سال گذشته اعداد اول موقعیتی استثنایی در عرصه رمز نگاری و دانش طراحی و شکستن رمزها کسب کرده اند. رمزها صرفا از نظر نظامی و جاسوسی حائز اهمیت نیستند بلکه از آنها در عرصه های تجاری و نیز فعالییتهای اینترنتی در مقیاس وسیع استفاده به عمل می‌آید. هیچ کس نمی‌خواهد که راهزنان اینترنتی به اطلاعات شخصی مربوط به حسابهای بانکی یا شماره کارتهای اعتباری آنان دست یابد. هم اکنون دزدی مشخصات شناسنامه ای افراد و جعل هویت آنان به صورت یکی از بزرگترین قلمروهای فعالییت های تبهکارانه در سطح بین‌المللی در آمده است. سازندگان کامپیوترها و ارائه‌دهندگان خدمات اینترنتی با توجه به آنکه در حال حاضر افراد بسیاری از فعالیتهای خود را از طریق اینترنت انجام می دهند، نظیر اینکه پول قبضهای برق و آب و تلفن خود را می‌پردازند یا در کلاسهای مورد نظر ثبت نام می‌کنند، یا بلیت هواپیما و قطار رزرو می‌کنند، در تلاشند تا از خطر دستیابی تبهکاران به اطلاعات شخصی افراد جلوگیری به عمل اورند. یکی از مهمترین سیستمهایی که در این زمینه مورد استفاده صنایع است سیستم آر اس آ نام دارد که متکی به اعداد اول است. اعداد اول مورد استفاده در این سیستم در حدود ۱۰۰رقمی هستند. سیستم آر اس آ در بسیاری از سیستم های کامپیوتری مورد استفاده قرار دارد و در پروتکل اصلی برای ارتباطات امن اینرتنتی نیز گنجانده شده است و بسیاری از دولتها، شرکتهای بزرگ و دانشگاهها از آن استفاده می‌کنند. جواز استفاده از این سیستم برای بیش از ۷۰۰شرکت صادر شده و بیش از نیم میلیون کپی از آن در سطح جهانی مورد استفاده قرار دارد. برای شکستن رمز آر اس آ باید مضراب اعداد ۲۰۰رقمی یا بزرگتر را پیدا کنید. هرچند فاکتور گیری یا عامل مشترک گیری از اعداد سخت تر از آزمودن اول بودن آنهاست اما این دو مساله با یکدیگر ارتباط دارند و ریاضی دانان از یک ابزار برای حل هر دو مساله استفاده می‌کنند. همه این جنبه‌ها بر اهمیت کشف هر روشی برای محاسبه اعداد اول می‌افزاید.