عدد اول
عدد طبیعی بزرگتر از یک، که جز یک و خودش هیچ مقسومعلیه دیگری نداشته باشد / From Wikipedia, the free encyclopedia
عدد اول (به انگلیسی: Prime Number)، عددی طبیعی بزرگتر از ۱ است که نتوان آن را بهصورت ضرب دو عدد طبیعی کوچکتر نوشت (یعنی یکی از آنها نمیتواند با خود عدد برابر باشد). به عبارت سادهتر، اعداد اول، مجموعهای از اعداد طبیعی بزرگتر از ۱ هستند که فقط بر یک و خود عدد بخشپذیر هستند. عدد طبیعی بزرگتر از ۱ که اول نباشد را عدد مرکب میگویند. به عنوان مثال، ۷ یک عدد اول است، چون فقط بر یک و ۷ بخشپذیر است و تنها روشی که میتوان آن را بهصورت ضرب دو عدد طبیعی نوشت بهصورت یا است که شامل خود ۷ میشود (دو عددی که در ضرب میآیند باید از خود ۷ کوچکتر باشند). اما به عنوان مثال، ۶ یک عدد مرکب است، چرا که میتوان آن را بهصورت نوشت که هردوی آنها از ۶ کوچکترند. اعداد اول در نظریهٔ اعداد به دلیل قضیهٔ اساسی حساب نقش محوری دارند، این قضیه میگوید: هر عدد طبیعی بزرگتر از ۱، یا اول است یا اگر اول نباشد، میتوان آن را به ضرب اعداد اول تجزیه کرد، که این تجزیه در حد ترتیب یگانه است.
خاصیت اعداد اول را اول بودن میگویند. یک روش کُند برای چک کردن اول بودن یک عدد مثل ، آزمون تقسیم است. این آزمون بخش پذیر بودن <>math>\mathrm{n}</math بر هر [[عدد صحیح]] بین ۲ و <math>\sqrt{n}</math> را چک میکند. الگوریتمهای سریعتری نیز وجود دارند، مثل آزمون اول بودن میلر-رابین که سریع است، اما احتمال رخ دادن درصدی خطا نیز در آن وجود دارد. آزمون دیگر، آزمون اول بودن AKS است، که همیشه جواب صحیح بهدست میدهد، اما مرتبه زمانی آن چندجملهای است و برای کاربردهای عملی بسیار کُند میباشد. روشهای بسیار سریعی برای آزمون اول بودن اعداد خاصی مثل اعداد مرسن نیز وجود دارد. تا دسامبر ۲۰۱۸ بزرگترین عدد اول شناخته شده در سیستم ده-دهی ۲۴٬۸۶۲٬۰۴۸ رقم دارد.[1]
اقلیدس حدود ۲۵۶ سال قبل از میلاد اثبات کرد که بینهایت عدد اول وجود دارد. با این حال، توزیع اعداد اول در میان اعداد طبیعی را میتوان از نظر آماری مدلسازی کرد. اولین نتیجهای که در این جهت حاصل شد قضیه اعداد اول بود که در انتهای قرن نوزدهم بهدست آمد. این قضیه میگوید که احتمال اول بودن یک عدد طبیعی تصادفی با تعداد ارقام آن (یعنی لگاریتم آن عدد) رابطه عکس دارد.
چندین سؤال تاریخی در ارتباط با اعداد اول هنوزmath>\mathrm{n}</math> لاینحل ماندهاند. این سؤالات شامل حدس گلدباخ میشود، این حدس میگوید که هر عدد صحیح زوج بزرگتر از ۲ را میتوان بهصورت جمع دو عدد اول بیان کرد. یکی دیگر از این سؤالات حدس اعداد اول دوقلو است، که میگوید تعداد اعداد اولی که تفاضلشان فقط ۲ باشد بینهایت است. چنین سؤالاتی موجب پیشرفت شاخههای مختلف نظریهٔ اعداد گشتند که در این مسیر بر روی جنبههای تحلیلی و جبری اعداد تمرکز شدهاست. اعداد اول در چندین مسیر فناوری اطلاعات استفاده شدهاند. مثل رمزنگاری کلید عمومی که به سخت بودن تجزیهٔ اعداد بزرگ به عوامل اولشان تکیه میکند. در جبر مجرد، اشیائی وجود دارند که به صورت تعمیمیافته، شبیه اعداد اول عمل میکنند. مثل عناصر اول و ایدهآلهای اول