عدد اول

عدد اول ( به انگلیسی: Prime Number ) ، عددی طبیعی بزرگ تر از ۱ است که نتوان آن را به صورت ضرب دو عدد طبیعی کوچک تر نوشت ( یعنی یکی از آن ها نمی تواند با خود عدد برابر باشد ) . به عبارت ساده تر، اعداد اول، مجموعه ای از اعداد طبیعی بزرگ تر از ۱ هستند که فقط بر یک و خود عدد بخش پذیر هستند. عدد طبیعی بزرگ تر از ۱ که اول نباشد را عدد مرکب می گویند. به عنوان مثال، ۷ یک عدد اول است، چون فقط بر یک و ۷ بخش پذیر است و تنها روشی که می توان آن را به صورت ضرب دو عدد طبیعی نوشت به صورت 1 × 7 یا 7 × 1 است که شامل خود ۷ می شود ( دو عددی که در ضرب می آیند باید از خود ۷ کوچک تر باشند ) . اما به عنوان مثال، ۶ یک عدد مرکب است، چرا که می توان آن را به صورت 2 × 3 نوشت که هردوی آن ها از ۶ کوچک ترند. اعداد اول در نظریهٔ اعداد به دلیل قضیهٔ اساسی حساب نقش محوری دارند، این قضیه می گوید: هر عدد طبیعی بزرگ تر از ۱، یا اول است یا اگر اول نباشد، می توان آن را به ضرب اعداد اول تجزیه کرد، که این تجزیه در حد ترتیب یگانه است.
خاصیت اعداد اول را اول بودن می گویند. یک روش کُند برای چک کردن اول بودن یک عدد مثل n ، آزمون تقسیم است. این آزمون بخش پذیر بودن n بر هر عدد صحیح بین ۲ و n را چک می کند. الگوریتم های سریع تری نیز وجود دارند، مثل آزمون اول بودن میلر - رابین که سریع است، اما احتمال رخ دادن درصدی خطا نیز در آن وجود دارد. آزمون دیگر، آزمون اول بودن AKS است، که همیشه جواب صحیح به دست می دهد، اما مرتبه زمانی آن چندجمله ای است و برای کاربردهای عملی بسیار کُند می باشد. روش های بسیار سریعی برای آزمون اول بودن اعداد خاصی مثل اعداد مرسن نیز وجود دارد. تا دسامبر ۲۰۱۸ بزرگ ترین عدد اول شناخته شده در سیستم ده - دهی ۲۴٬۸۶۲٬۰۴۸ رقم دارد. [ ۱]
اقلیدس حدود ۲۵۶ سال قبل از میلاد اثبات کرد که بی نهایت عدد اول وجود دارد. با این حال، توزیع اعداد اول در میان اعداد طبیعی را می توان از نظر آماری مدل سازی کرد. اولین نتیجه ای که در این جهت حاصل شد قضیه اعداد اول بود که در انتهای قرن نوزدهم به دست آمد. این قضیه می گوید که احتمال اول بودن یک عدد طبیعی تصادفی با تعداد ارقام آن ( یعنی لگاریتم آن عدد ) رابطه عکس دارد.
چندین سؤال تاریخی در ارتباط با اعداد اول هنوز لاینحل مانده اند. این سؤالات شامل حدس گلدباخ می شود، این حدس می گوید که هر عدد صحیح زوج بزرگ تر از ۲ را می توان به صورت جمع دو عدد اول بیان کرد. یکی دیگر از این سؤالات حدس اعداد اول دوقلو است، که می گوید تعداد اعداد اولی که تفاضل شان فقط ۲ باشد بی نهایت است. چنین سؤالاتی موجب پیشرفت شاخه های مختلف نظریهٔ اعداد گشتند که در این مسیر بر روی جنبه های تحلیلی و جبری اعداد تمرکز شده است. اعداد اول در چندین مسیر فناوری اطلاعات استفاده شده اند. مثل رمزنگاری کلید عمومی که به سخت بودن تجزیهٔ اعداد بزرگ به عوامل اول شان تکیه می کند. در جبر مجرد، اشیائی وجود دارند که به صورت تعمیم یافته، شبیه اعداد اول عمل می کنند. مثل عناصر اول و ایده آل های اول

عدد اوّل (prime number)
عدد صحیحی که فقط بر ۱ و خودش قابل قسمت باشد. عدد اول عامل دیگری ندارد. بی نهایت عدد اول وجود دارد و نخستین ده عدد اول عبارت اند از ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹، ۲۳، و ۲۹. هر عدد یا اول است یا به صورت حاصل ضرب دو یا چند عدد اول بیان شدنی است.