عدد اول کیست؟ توضیح بده.
عدد اول ، عددی طبیعی بزرگ‌تر از ۱ است که نتوان آن را به‌صورت ضرب دو عدد طبیعی کوچک‌تر نوشت (یعنی جز بر خودشان و یک بر عدد دیگری بخش پذیر نیستند). به عبارت ساده‌تر، اعداد اول، مجموعه‌ای از اعداد طبیعی بزرگ‌تر از ۱ هستند که فقط بر یک و خود عدد بخش‌پذیر هستند. عدد طبیعی بزرگ‌تر از ۱ که اول نباشد را عدد مرکب می‌گویند. به عنوان مثال، ۷ یک عدد اول است، چون فقط بر یک و ۷ بخش‌پذیر است و تنها روشی که می‌توان آن را به‌صورت ضرب دو عدد طبیعی نوشت به‌صورت formula_1 یا formula_2 است که شامل خود ۷ می‌شود (دو عددی که در ضرب می‌آیند باید از خود ۷ کوچک‌تر باشند). اما به عنوان مثال، ۶ یک عدد مرکب است، چرا که می‌توان آن را به‌صورت formula_3 نوشت که هردوی آن‌ها از ۶ کوچک‌ترند. اعداد اول در نظریهٔ اعداد به دلیل قضیهٔ اساسی حساب نقش محوری دارند، این قضیه می‌گوید: هر عدد طبیعی بزرگ‌تر از ۱، یا اول است یا اگر اول نباشد، می‌توان آن را به ضرب اعداد اول تجزیه کرد، که این تجزیه در حد ترتیب یگانه است.خاصیت اعداد اول را اول بودن می‌گویند. یک روش کُند برای چک کردن اول بودن یک عدد مثل formula_4، آزمون تقسیم است. این آزمون بخش پذیر بودن &lt;&gt;math&gt;\mathrm{n}&lt;/math بر هر عدد صحیح بین ۲ و formula_5 را چک می‌کند. الگوریتم‌های سریع‌تری نیز وجود دارند، مثل آزمون اول بودن میلر-رابین که سریع است، اما احتمال رخ دادن درصدی خطا نیز در آن وجود دارد. آزمون دیگر، آزمون اول بودن AKS است، که همیشه جواب صحیح به‌دست می‌دهد، اما مرتبه زمانی آن چندجمله‌ای است و برای کاربردهای عملی بسیار کُند می‌باشد. روش‌های بسیار سریعی برای آزمون اول بودن اعداد خاصی مثل اعداد مرسن نیز وجود دارد. تا دسامبر ۲۰۱۸ بزرگ‌ترین عدد اول شناخته شده در سیستم ده-دهی ۲۴٬۸۶۲٬۰۴۸ رقم دارد.اقلیدس حدود ۲۵۶ سال قبل از میلاد اثبات کرد که بی‌نهایت عدد اول وجود دارد. با این حال، توزیع اعداد اول در میان اعداد طبیعی را می‌توان از نظر آماری مدل‌سازی کرد. اولین نتیجه‌ای که در این جهت حاصل شد قضیه اعداد اول بود که در انتهای قرن نوزدهم به‌دست آمد. این قضیه می‌گوید که احتمال اول بودن یک عدد طبیعی تصادفی با تعداد ارقام آن (یعنی لگاریتم آن عدد) رابطه عکس دارد.چندین سؤال تاریخی در ارتباط با اعداد اول هنوزmath&gt;\mathrm{n}&lt;/math&gt; لاینحل مانده‌اند. این سؤالات شامل حدس گلدباخ می‌شود، این حدس می‌گوید که هر عدد صحیح زوج بزرگ‌تر از ۲ را می‌توان به‌صورت جمع دو عدد اول بیان کرد. یکی دیگر از این سؤالات حدس اعداد اول دوقلو است، که می‌گوید تعداد اعداد اولی که تفاضل‌شان فقط ۲ باشد بی‌نهایت است. چنین سؤالاتی موجب پیشرفت شاخه‌های مختلف نظریهٔ اعداد گشتند که در این مسیر بر روی جنبه‌های تحلیلی و جبری اعداد تمرکز شده‌است. اعداد اول در چندین مسیر فناوری اطلاعات استفاده شده‌اند. مثل رمزنگاری کلید عمومی که به سخت بودن تجزیهٔ اعداد بزرگ به عوامل اول‌شان تکیه می‌کند. در جبر مجرد، اشیائی وجود دارند که به صورت تعمیم‌یافته، شبیه اعداد اول عمل می‌کنند. مثل عناصر اول و ایده‌آل‌های اولتعریف و مثال‌ها.عددی طبیعی (۱، ۲، ۳، ...) را «"عدد اول"» (یا "اول") نامند اگر بزرگ‌تر از ۱ بوده و نتوان آن را به‌صورت ضرب دو عدد طبیعی کوچک‌تر نوشت. اعداد بزرگ‌تر از ۱ که اول نباشند را مرکب می‌نامند. به بیان دیگر، formula_6 اول است اگر نتوان آن را به بیش از یک گروه با اندازهٔ مساوی تقسیم‌بندی نمود، یا امکان آرایش formula_6 نقطه به شبکه‌ای از نقاط مستطیل‌گونه که طول و عرضی بزرگ‌تر از یک داشته باشند، امکان‌پذیر نباشد. به عنوان مثال، در میان اعداد ۱ تا ۶، اعداد ۲، ۳ و ۵، اعداد اول می‌باشند، چرا که هیچ عددی آن‌ها را به گونه‌ای تقسیم نمی‌کنند که باقیمانده صفر شود. ۱ اول نیست، چرا که به‌طور ویژه از تعریف مستثنی شده. ۴=۲×۲ و ۶=۲×۳، هردو اعدادی مرکب‌اند.مقسوم‌علیه‌های یک عدد طبیعی چون formula_6، اعداد طبیعی هستند که formula_6 را به بخش‌های مساوی تقسیم می‌کنند. برای هر عدد طبیعی، ۱ و خود عدد همیشه جزو مقسوم‌علیه‌ها می‌باشند. اگر مقسوم‌علیه دیگری وجود داشته باشد، آن عدد اول نخواهد بود. این ایده منجر به تعریف متفاوت ولی معادلی برای اعداد اول می‌گردد: آن‌ها اعدادی هستند که دقیقاً دو مقسوم‌علیه دارند، ۱ و خود عدد. هنوز روش دیگری جهت بیان همین مفهوم وجود دارد، این که عدد formula_6 اول است اگر بزرگ‌تر از یک بوده و بر هیچ‌یک از اعداد formula_11 بخش‌پذیر نباشد.اولین ۲۵ عدد اول (تمام اعداد اول کوچکتر از ۱۰۰) بدین قرار اند:هیچ عدد زوج بزرگ‌تر از ۲ چون formula_6 اول نیست، چرا که دست کم می‌توان آن را به صورت formula_13 بیان نمود. ازین رو، هر عدد اول به غیر از ۲، یک عدد فرد است که به آن "عدد اول فرد" می‌گویند. به‌طور مشابه، هنگامی که تمام اعداد اول بزرگ‌تر از ۵ را در قالب دستگاه اعداد مبنای ده بنویسیم، رقم آخر آن‌ها (رقم یکان) به یکی از ارقام ۱، ۳، ۷ یا ۹ ختم می‌گردد. اعداد بزرگتر از ۵ی که به سایر ارقام ختم شوند، مرکب‌اند، چرا که اعداد ده-دهی که به ۰، ۲، ۴، ۶، یا ۸ ختم شوند زوج بوده و اعداد ده-دهی که به ۰ یا ۵ ختم شوند بر ۵ بخش‌پذیرند.برخی مواقع، مجموعه تمام اعداد اول را با formula_14 (حرف بزرگ درشت‌شده "P") و برخی از مواقع دیگر با formula_15 (حرف "P" بزرگ و درشت تخته‌سیاهی) نمایش می‌دهند.تاریخچه.پاپیروس ریاضی ریند، مربوط به حدود ۱۵۵۰ پیش از میلاد است که در آن کسرهای گسترش‌یافته مختلفی از اعداد اول و مرکب موجود است. با اینحال، قدیمی‌ترین مطالعات صریح برجای مانده که بر روی اعداد اول صورت پذیرفته، مربوط به ریاضیات یونان باستان می‌باشد. "اصول اقلیدس" (حدود ۳۰۰ پیش از میلاد)، بی‌نهایت بودن اعداد اول و قضیه اساسی حساب را اثبات کرده و نشان می‌دهد که چگونه می‌توان از یک عدد اول مرسن، عدد تامی ساخت. غربال اراتوستن، یکی دیگر از اختراعات یونانیان است که هنوز هم جهت ساخت فهرست اعداد اول مورد استفاده قرار می‌گیرد.در حدود ۱۰۰۰ میلادی، ریاضی‌دان جهان اسلام، ابن هیثم (Alhazen)، قضیه ویلسون را یافت، که اعداد اول را به عنوان اعدادی چون formula_6 مشخص می‌کند که formula_17 را می‌شمارند (یعنی formula_6 اول است formula_19 formula_17). همچنین او حدس زد که تمام اعداد تام زوج، از ترسیم اقلیدسی با استفاده از اعداد اول می‌آیند، اما قادر به اثبات آن نبود. یکی دیگر از ریاضیدانان جهان اسلام، به نام ابن بنای مراکشی، مشاهده نمود که غربال اراتوستن را می‌توان تنها با آزمودن مقسوم‌علیه‌های کوچکتر مساوی ریشه دوم (ریشه مربعی) بزرگترین عددی که باید آزموده شود، تسریع نمود. فیبوناچی، نوآوری‌های جهان اسلام را به اروپا بازگرداند. کتاب او با نام "Liber Abaci" (۱۲۰۲ میلادی)، اولین کتابی بود که آزمون تقسیم را با استفاده از مقسوم‌علیه‌های کوچکتر مساوی رادیکال عدد مورد نظر، جهت آزمودن اول بودن یا نبودن یک عدد صحیح معرفی نمود.در ۱۶۴۰ میلادی، پیر دو فرما، قضیه کوچک فرما را بیان نمود (بدون اثبات)، (بعدها لایبنیتس و اویلر اثباتش نمودند). همچنین فرما در مورد اول بودن اعداد فرما formula_21، و مارین مرسن در مورد اعداد اول مرسن، یعنی اعداد اولی به فرم formula_22 که در آن formula_23 اول است، تحقیق نمودند. کریستین گلدباخ، حدس گلدباخ را فرموله کرد، این حدس بیان می‌دارد که هر عدد زوج به صورت جمع دو عدد اول است، او صورت این حدس را در ۱۷۴۲ میلادی در قالب نامه‌ای به اویلر مطرح نمود. اویلر حدس ابن هیثم (Alhazen) (که اکنون به قضیه اقلیدس-اویلر معروف است) را اثبات نمود، این حدس بیان می‌نمود که تمام اعداد تام زوج را می‌توان از اعداد اول مرسن ساخت. او در اثبات‌هایش در ارتباط با بی‌نهایت بودن اعداد اول و همچنین واگرایی جمع معکوس اعداد اول formula_24، روش‌هایی را از آنالیز ریاضی به این حوزه از ریاضیات معرفی نمود. در ابتدای قرن نوزدهم میلادی، لژاندر و گاوس حدس زدند که با میل پیدا کردن formula_25 به سمت بی‌نهایت، تعداد اعداد اول کوچکتر مساوی formula_25، مجانب با formula_27 است که در آن formula_28، لگاریتم طبیعی formula_25 است. پیامد ضعیف تری از این چگالی بالای اعداد اول، اصل برتراند بود که می‌گفت: برای هر formula_30، عدد اولی بین formula_6 و formula_32 وجود دارد، این اصل در ۱۸۵۲ میلادی توسط پافنوتی چبیشف اثبات شد. ایده‌های برنهارت ریمان در مقاله‌اش به سال ۱۸۵۹ میلادی، که در ارتباط با تابع زتا بود، خطوط کلی اثبات حدس لژاندر و گاوس را ترسیم نمود. گرچه که فرضیه ریمان، با وجود ارتباط نزدیک با حدس اخیر، هنوز هم اثبات نشده، ولی خطوط کلی اثبات ریمان در ارتباط با حدس لژاندر و گاوس در ۱۸۹۶ توسط آدامار و دو لا والی پوسین تکمیل شده و نتیجه آن را اکنون به نام قضیه اعداد اول می‌شناسند. یکی دیگر از نتایج مهم قرن نوزدهم میلادی، قضیه دیریکله روی تصاعدهای حسابی بود، این که برخی از تصاعدهای حسابی، بی‌نهایت عدد اول را دربر می‌گیرند.بسیاری از ریاضی‌دانان، برای اعداد بزرگی که اعمال تقسیم معمولی رویشان عملی نباشند (از نظر قدرت محاسبه)، آزمون‌های اول بودن را مورد بررسی قرار داده‌اند. روش‌هایی که به فرم‌های عددی خاصی محدود شده باشند، مثل این موارد: آزمون پپین برای اعداد فرما (۱۸۷۷)، قضیه پروث (حدود ۱۸۷۸ میلادی)، آزمون اول بودن لهمر (نشأت گرفته در ۱۸۵۶ میلادی)، و آزمون اول بودن لوکاس.از ۱۹۵۱میلادی، تمام بزرگترین اعداد اول شناخته شده را با استفاده از این آزمون‌ها، و با کمک کامپیوترها یافته‌اند. جستجو برای اعداد اول بزرگتر، در خارج از دایره ریاضی‌دانان نیز ایجاد علاقه نموده‌است، پروژه‌هایی چون «جستجوی بزرگ اینترنتی اعداد اول مرسن» و سایر پروژه‌هایی که با کمک محاسبات توزیع‌شده صورت می‌پذیرند. این ایده که اعداد اول کاربردهایی نیز خارج از ریاضیات محض دارد در دهه ۱۹۷۰ میلادی، هنگامی که دستگاه‌های رمزنگاری کلید عمومی و RSA ابداع شدند، درهم شکست، چرا که این الگوریتم‌ها، اعداد اول را مبنای خود قرار می‌دادند.اهمیت عملی فزاینده آزمون اول بودن با کمک کامپیوتر، و همچنین فاکتورگیری، منجر به توسعه روش‌های ارتقاء یافته‌ای شد که قادر بودند به کمک آن‌ها، با اعداد بزرگی با فرم غیر مقید و بدون محدودیت نیز کار کنند. همچنین، با کشف قضیه گرین-تائو (۲۰۰۴ میلادی)، مبنی بر این که تصاعدهای حسابی به میزان دلخواه بلندی از اعداد اول وجود دارند، به علاوه اثبات یتان ژانگ در ۲۰۱۳ میلادی مبنی بر این که بی‌نهایت شکاف اعداد اول با اندازه کراندار موجودند، قدم‌های مثبتی در پیش‌برد نظریه ریاضیاتی اعداد اول بوند.اول بودن یک.یونانیان اولیه، ۱ را حتی جزو اعداد هم به‌شمار نمی‌آوردند، پس طبیعتاً آن را اول هم در نظر نمی‌گرفتند. همچنین برخی از ریاضی‌دانان مربوط به این دوره، اعداد اول را به عنوان جزئی از اعداد فرد در نظر می‌گرفتند، بنابراین آن‌ها نیز ۲ را به عنوان عدد اول در نظر نمی‌گرفتند. با این حال، اقلیدس و بخش عمده‌ای از سایر ریاضی‌دانان یونانی، ۲ را به عنوان اول در نظر می‌گرفتند. ریاضی‌دانان جهان اسلام در قرون وسطی، عمدتاً از یونانیان طبعیت کرده و ۱ را عدد در نظر نمی‌گرفتند. در قرون وسطی و رنسانس، ریاضی‌دانان کم‌کم ۱ را به عنوان عدد در نظر گرفتند، و برخی از آن‌ها ۱ را به عنوان اولین عدد اول به حساب آوردند. در اواسط قرن هجدهم میلادی، کریستین گلدباخ، ۱ را در مراودات خود با لئونارد اویلر، به عنوان عدد اول در نظر می‌گرفت؛ با این‌حال، خود اویلر ۱ را اول در نظر نمی‌گرفت. در قرن نوزدهم میلادی، بسیاری از ریاضی‌دانان هنوز هم ۱ را اول می‌دانستند، و فهرست‌های اعداد اولی که شامل ۱ بودند، هنوز هم تا ۱۹۵۶ میلادی منتشر می‌شدند.اگر در تعریف عدد اول تغییر ایجاد شده به گونه‌ای که ۱ نیز عدد اول محسوب شود، بسیاری از گزاره‌ها در مورد اعداد اول نیاز به بازنویسی خام و ناشیانه‌ای خواهند داشت. به عنوان مثال، قضیه بنیادین حساب را باید به گونه‌ای بازنویسی کرد تا فاکتورگیری برحسب اعداد اول بزرگتر از یک صورت گیرند، چرا که با ظهور تعداد متفاوت و تکراری از عدد ۱ در تجزیه اعداد، فاکتورگیری‌های مختلفی برای هر عدد تولید می‌شوند. به‌طور مشابه، اگر ۱ به عنوان عدد اول در نظر گرفته شود، غربال اراتوستن به خوبی کار نمی‌کند، چرا که تمام مضارب ۱ (یعنی تمام اعداد دیگر) حذف شده و خروجی تنها شامل ۱ خواهد بود. برخی از خواص فنی‌تر اعداد اول نیز برای عدد ۱ برقرار نیستند: به عنوان مثال، فرمول‌های تابع فی اویلر، یا تابع جمع مقسوم‌علیه‌ها، برای ۱ ضوابط متفاوتی نسبت به ضابطه‌شان برای اعداد اول دارند. تا اوایل قرن بیستم میلادی، ریاضی‌دانان شروع به توافق بر سر این موضوع کردند که ۱ نباید به عنوان عدد اول فهرست شود، بلکه برایش رده مخصوصی به نام «یکه» (unit، عضو معکوس‌دار در ساختارهای جبری چون حلقه) را تعریف نمودند.قضیه‌ها.به این اثبات دقت کنید که از برهان خلف استفاده می‌کنیم:"فرض خلف :" اعداد اول متناهی است.اعداد اول را در هم ضرب می‌کنیم.formula_33ضرب اعداد از formula_34 بزرگ‌تراست.formula_35formula_36formula_37formula_38formula_39formula_40formula_41formula_42formula_43formula_44که عدد یک جزء اعداد اول نیست پس به تناقض می‌رسیم و فرض خلف باطل است. اعداد اول نامتناهی هستند.k عدد اول وجود دارد.تابع شمارش اعداد اول.ریاضیات تابع شمارش اعداد اول تابعی است که برای بیان تعداد اعداد اول به کار می‌رود و آن را با نماد formula_45 نمایش می‌دهند.ریاضیدان فرانسوی پیر دوسارارت ثابت کرد که برای x ≥ ۵۹۹ رابطه زیر برقرار است:formula_46همچنین ثابت کرد که برای هر x ≥ ۳۵۵۹۹۱:formula_47بعدها ثابت شد که برای هر ε&gt;۰ عددی طبیعی مانند s وجود دارد که برای هر x&gt;s رابطه زیر برقرار است:formula_48قضیه اعداد اول.اگرformula_45 تعداد اعداد اول کمتر از formula_50 باشدآنگاهformula_51با استفاده از قضیه اعداد اول می‌توان اثبات کرد که:formula_52که در آن تابع formula_53، تابع مولد اعداد اول باشد. یعنی x امین عدد اول formula_54اثبات مطلب بالا به شرح زیر است:می‌دانیمformula_51formula_56می‌دانیم توابع formula_53 و formula_58 معکوس هم هستند. یعنی:formula_59در نتیجه می‌توان با حل معادله formula_60 تابع formula_53 را یافت.می‌دانیم formula_56پس با حل معادله formula_63 می‌توان هم‌ارزی برای formula_53 یافت.به روش تکرار ساده معادله را حل می‌کنیم.formula_65formula_66formula_67اما باید توجه داشت چون به جای formula_58 از تابع هم ارز آن استفاده شده پس:formula_69در نتیجه:formula_52قضیه ویلسون.قضیه ویلسون راهی برای تشخیص اعداد اول است.این قضیه بیان می‌کند به ازای هر عدد اول مانند formula_71 داریم formula_72این قضیه دوشرطی است بنابراین راهی برای تشخیص اعداد اول از مرکب است یعنی:برای هر عدد صحیح x اگر رابطه زیر برقرار باشد آنگاه x عددی اول است در غیر این صورت x عددی مرکب است.formula_73 formula_74این قضیه تعمیم‌هایی به شکل زیر دارد:تعمیم گاوس: کارل فریدریش گاوس ریاضیدان آلمانی در سال ۱۸۰۰ میلادی ثابت کرده که برای هر عدد طبیعی m&gt;۲ عدد اول pformula_75در اینجا formula_76 عددی صحیح و مثبت است.بزرگترین عدد اول کشف شده.بزرگ‌ترین عدد اول کشف شده تا (۲۰۱۶) برابر دو به توان ۷۴ میلیون و ۲۰۷ هزار و ۲۸۱ منهای یک است. این عدد ۲۲٬۳۳۸٬۶۱۸ رقم دارد و یک عدد مرسن است. عدد مرسن عددی است که برابر ۲ به توان n منهای یک است.در سال ۲۰۱۸، طولانی‌ترین عدد اول که دارای ۲۳ میلیون رقم است؛ کشف شد. این عدد اول نیز یک عدد مرسن است که در جریان محاسبات در رایانه یک مهندس برق به نام جاناتان پیس در آمریکا در جریان پروژه‌ای برای کشف اعداد اول به نام «تحقیق اینترنتی بزرگ عدد مرسن» (GIMPS) کشف شد. این عدد را به اختصار و به‌طور قراردادی، M77232917 نامیده‌اند. پژوهش‌ها برای یافتن عددهای اول بزرگ دشوار و نیازمند نرم‌افزارهای خاص و همکاری علمی پژوهشگران هستند.الگوهای توزیع اعداد اول.یکی از مسائل مورد توجه ریاضی‌دانان، چگونگی توزیع و ترتیب قرارگرفتن اعداد اول درون رشته اعداد طبیعی است. این چگونگی دارای الگوهایی است که یکی از آنها به «الگوی پیشرفت عددی» معروف است.مثلاً اگر به عدد ۵ که عددی اول است، ۶ واحد اضافه کنیم به ۱۱ و اگر به ۱۱، ۶ واحد اضافه کنیم به ۱۷ و اگر دوباره اضافه کنیم، به ۲۳ و ۲۹ می‌رسیم که همگی اعدادی اولند. اما با اضافه کردن ۶ واحد دیگر به ۳۵ می‌رسیم که عددی اول نیست و الگو متوقف می‌گردد.مسئله مورد توجه اینست که در هر الگوی پیشرفت چند عدد اول پیش از رسیدن به اولین عدد غیر اول، بدست می‌آیند؟ طولانی‌ترین رشته‌ای که تاکنون بدست آمده، ۲۲ عدد اول را شامل است. اولین عدد اول این رشته ۱۱۴۱۰۳۳۷۸۵۰۵۵۳ بوده که اگر عدد ۴۶۰۹۰۹۸۶۹۴۲۰۰ به آن اضافه شود عدد اول بعدی به‌وجود می‌آید و می‌توان ۲۲ بار عدد مذکور را به اعداد اول مرحله قبل افزود و عدد اولی جدید بدست آورد. دو ریاضی‌دان اثبات کرده‌اند برای هر رشته از اعداد اول می‌توان به یک رشته عددی رسید.