عدد اول

یک عدد اول (به انگلیسی: Prime Number)، عددی طبیعی بزرگتر از ۱ است که نتوان آن را به صورت ضرب دو عدد طبیعی کوچکتر نوشت. (یعنی یکی از آن‌ها نمی‌تواند با خود عدد برابر باشد). عدد طبیعی بزرگتر از ۱ که اول نباشد را عدد مرکب گویند. به عنوان مثال ۵ یک عدد اول است، چون تنها روشی که می‌توان آن را به صورت ضرب دو عدد طبیعی نوشت به صورت {\displaystyle 1\times 5} یا {\displaystyle 5\times 1} است که شامل خود ۵ می‌شود (دو عددی که در ضرب می‌آیند باید از خود ۵ کوچکتر باشند). اما به عنوان مثال ۶ یک عدد مرکب است، چرا که می‌توان آن را به صورت {\displaystyle 2\times 3} نوشت که هردوی آن‌ها از ۶ کوچک‌ترند. اعداد اول در نظریه اعداد به دلیل قضیه اساسی حساب نقش محوری دارند، این قضیه می‌گوید: هر عدد طبیعی بزرگتر از ۱ یا اول است یا می‌توان آن را به ضرب اعداد اول تجزیه کرد، که این تجزیه در حد ترتیب یگانه است.

خاصیت اعداد اول را اول بودن می‌گویند. یک روش کند برای چک کردن اول بودن یک عدد مثل {\displaystyle \mathrm {n} }، آزمون تقسیم است. این آزمون بخش پذیر بودن {\displaystyle \mathrm {n} } بر هر عدد صحیح بین ۲ و {\displaystyle {\sqrt {n}}} را چک می‌کند. الگوریتم‌های سریع تری نیز وجود دارند، مثل آزمون اول بودن میلر-رابین که سریع است اما احتمال رخ دادن درصدی خطا نیز در آن وجود دارد. آزمون دیگر، آزمون اول بودن AKS است، که همیشه جواب صحیح بدست می‌دهد، اما مرتبه زمانی آن چندجمله‌ای است و برای کاربردهای عملی بسیار کند می‌باشد. روش‌های بسیار سریعی برای آزمون اول بودن اعداد خاصی مثل اعداد مرسن نیز وجود دارد. تا دسامبر ۲۰۱۸ بزرگترین عدد اول شناخته شده در سیستم ده-دهی ۲۴٬۸۶۲٬۰۴۸ رقم دارد.[۱]

اقلیدس حدود ۳۰۰ قبل از میلاد اثبات کرد که بی‌نهایت عدد اول وجود دارد. با این حال، توزیع اعداد اول در میان اعداد طبیعی را می‌توان از نظر آماری مدلسازی کرد. اولین نتیجه ای که در این جهت حاصل شد قضیه اعداد اول بود که در انتهای قرن نوزدهم بدست آمد. این قضیه می‌گوید که احتمال اول بودن یک عدد طبیعی تصادفی با تعداد ارقام آن (یعنی لگاریتم آن عدد) رابطه عکس دارد.

چندین سؤال تاریخی در ارتباط با اعداد اول هنوز لاینحل مانده‌اند. این سوالات شامل حدس گلدباخ می‌شود، این حدس می‌گوید که هر عدد صحیح زوج بزرگتر از ۲ را می‌توان به صورت جمع دو عدد اول بیان کرد. یکی دیگر از این سؤالات حدس اعداد اول دوقلو است، که می‌گوید تعداد اعداد اولی که تفاضلشان فقط ۲ باشد بی‌نهایت است. چنین سؤالاتی موجب پیشرفت شاخه‌های مختلف نظریه اعداد گشتند که در این مسیر بر روی جنبه‌های تحلیلی و جبری اعداد تمرکز شده‌است. اعداد اول در چندین مسیر فناوری اطلاعات استفاده شده‌اند مثل رمزنگاری کلید عمومی که به سخت بودن تجزیه اعداد بزرگ به عوامل اولشان تکیه می‌کند. در جبر مجرد، اشیائی وجود دارند که به صورت تعمیم یافته شبیه اعداد اول عمل می‌کنند، مثل عناصر اول و ایده‌آل‌های اول.

تعریف و مثال‌ها

عدد اول عددی طبیعی بزرگ‌تر از ۱ است که بر هیچ عددی به جز خودش و ۱ بخش‌پذیر نباشد.[۲] تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگر عددی طبیعی و بزرگتر از ۱ اول نباشد مرکب است.[۳]

پیدا کردن رابطه‌ای جبری برای اعداد اول جزء یکی از معماهای ریاضی باقی مانده‌است و هنوز کسی به فرمولی برای آنها دست نیافته‌است.

دنبالهٔ اعداد اول به این صورت شروع می‌شود:

۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹، ۲۳، ۲۹، ۳۱، ۳۷، ۴۱، ۴۳، ۴۷، ۵۳، ۵۹، ۶۱، ۶۷، ۷۱، ۷۳، ۷۹، ۸۳، ۸۹، ۹۷، ۱۰۱، ۱۰۳، ۱۰۷، ۱۰۹، ۱۱۳، ۱۲۷، ۱۳۱، ۱۳۷، ۱۳۹، …[۴]

قضیه‌ها

• قضیه ۱: تعداد اعداد اول بی‌نهایت است.

به این اثبات دقت کنید از برهان خلف استفاده می‌کنیم:

فرض خلف : اعداد اول متناهی است.

اعداد اول را در هم ضرب می‌کنیم.

{\displaystyle P_{1},P_{2},P_{3},…,P_{n}}

ضرب اعداد از {\displaystyle P_{i}} بزرگ‌تراست.

{\displaystyle P_{1}\times P_{2}\times P_{3}\times …\times P_{n}>P_{i}}

{\displaystyle P_{1}\times P_{2}\times P_{3}\times …\times P_{n}+1>P_{i}}

{\displaystyle P_{1}\times P_{2}\times P_{3}\times …\times P_{n}+1=P_{i_{1}}…P_{i_{k}}}

{\displaystyle P_{1}\times P_{2}\times P_{3}\times …\times P_{n}+1=P_{i}\times X}

{\displaystyle P_{i_{1}}\times …\times P_{i_{k}}=P_{i}\times X}

{\displaystyle P_{1}\times P_{2}\times P_{3}\times …\times P_{n}+1=Y+1}

{\displaystyle P_{i_{1}}\times Y+1=P_{i_{1}}\times X}

{\displaystyle P_{i_{1}}\times X-P_{i_{1}}\times Y=1}

{\displaystyle P_{i_{1}}\times (X-Y)=1}

{\displaystyle P_{i_{1}}=1}

که عدد یک جزء اعداد اول نیست پس به تناقض می‌رسیم و فرض خلف باطل است. اعداد اول نامتناهی هستند.

• قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی مرکب بزرگ‌تر از ۱ را می‌توان به شکل حاصل‌ضرب اعدادی اول نوشت.
• قضیه ۳ (قضیه چبیشف):اگر n عددی طبیعی و بزرگ‌تر از ۳ باشد، حتماً بین n و ۲n عدد اولی وجود دارد.
• قضیه ۴ (قضیه اردیش (تعمیم قضیه چبیشف)): برای هر عدد طبیعی k، وجود دارد یک عدد طبیعی مثل N، که برای هر n>N، بین n و 2n,

k عدد اول وجود دارد.

• قضیه ۵: تنها زمانی مجموع دو عدد اول عددی فرد می‌شود که یکی از آنها عدد ۲ باشد. زیرا عدد ۲ تنها عدد اول زوج است.
• قضیه ۶: عددی اول است که به اعداد اول کوچکتر یا مساوی با جذر خودش بخش پذیر نباشد.[۵]
• قضیه ۷: رقم یکان اعداد اول بزرگ‌تر از ۱۰ فقط ممکن است ارقام ۱، ۳، ۷، و ۹ باشد.

قضایای اعداد اول

حدس گلدباخ (تاکنون اثبات نشده): هر عدد زوج را می‌توان به شکل جمع دو عدد اول نوشت.

{\displaystyle 2k=p_{n}+p_{m}}

مثال به شرح ذیل می‌باشد:

{\displaystyle 4=2+2}

{\displaystyle 6=3+3}

{\displaystyle 8=5+3}

{\displaystyle 10=5+5}

{\displaystyle 12=7+5}

{\displaystyle 14=7+7}

{\displaystyle 16=11+5}

{\displaystyle 18=11+7}

{\displaystyle 20=13+7}

{\displaystyle 22=11+11}

{\displaystyle 24=13+11}

{\displaystyle 26=19+7}

۲. حدس قوی گلدباخ: هر عدد فرد بزرگتر از ۵ را می‌توان به صورت مجموع ۳ عدد اول نوشت.

تابع شمارش اعداد اول

در ریاضیات تابع شمارش اعداد اول تابعی است که برای بیان تعداد اعداد اول به کار می‌رود و آن را با نماد {\displaystyle \pi (x)} نمایش می‌دهند.

ریاضیدان فرانسوی پیر دوسارارت ثابت کرد که برای x ≥ ۵۹۹ رابطه زیر برقرار است:

{\displaystyle {\frac {x}{\ln x}}\left(1+{\frac {1}{\ln x}}\right)<\pi (x)<{\frac {x}{\ln x}}\left(1+{\frac {1}{\ln x}}+{\frac {2.51}{(\ln x)^{2}}}\right).}

همچنین ثابت کرد که برای هر x ≥ ۳۵۵۹۹۱:

{\displaystyle {\frac {x}{\ln x+2}}<\pi (x)<{\frac {x}{\ln x-4}}}

بعدها ثابت شد که برای هر ε>۰ وجود دارد عددی طبیعی ماننده s که برای هر x>s رابطه زیر برقرار است:

{\displaystyle {\frac {x}{\ln x-(1-\varepsilon )}}<\pi (x)<{\frac {x}{\ln x-(1+\varepsilon )}}.}

قضیه اعداد اول

اگر{\displaystyle \pi (x)} تعداد اعداد اول کمتر از {\displaystyle x} باشد

آنگاه {\displaystyle \lim _{x\to \infty }{\frac {\pi (x)}{x/ln(x)}}=1}

{\displaystyle x}	{\displaystyle \pi (x)}	{\displaystyle {\frac {\pi (x)}{x/ln(x)}}}
۱۰	۴	۰٫۹۲۱
102	۲۵	۱٫۱۵۱
103	۱۶۸	۱٫۱۶۱
104	۱٬۲۲۹	۱٫۱۳۲
105	۹٬۵۹۲	۱٫۱۰۴
106	۷۸٬۴۹۸	۱٫۰۸۴
107	۶۶۴٬۵۷۹	۱٫۰۷۱
108	۵٬۷۶۱٬۴۵۵	۱٫۰۶۱
109	۵۰٬۸۴۷٬۵۳۴	۱٫۰۵۴
1010	۴۵۵٬۰۵۲٬۵۱۱	۱٫۰۴۸
OEIS	A006880	A057835

با استفاده از قضیه اعداد اول می‌توان اثبات کرد که:

{\displaystyle \lim _{x\to \infty }{\frac {p(x)}{x\ln(x)}}=1}

که در آن تابع {\displaystyle p(x)}، تابع مولد اعداد اول باشد. یعنی x امین عدد اول {\displaystyle p(x)=}

اثبات مطلب بالا به شرح زیر است:

می‌دانیم {\displaystyle \lim _{x\to \infty }{\frac {\pi (x)}{x/ln(x)}}=1}

{\displaystyle \pi (x)\sim {\frac {x}{\ln x}}.\!}

می‌دانیم توابع {\displaystyle p(x)} و {\displaystyle \pi (x)} معکوس هم هستند. یعنی:

{\displaystyle p^{-1}\left(\,x\,\right)=\pi (x)}

در نتیجه می‌توان با حل معادله {\displaystyle \pi (x)=x} تابع {\displaystyle p(x)} را یافت.

می‌دانیم {\displaystyle \pi (x)\sim {\frac {x}{\ln x}}.\!}

پس با حل معادله {\displaystyle {\frac {x}{\ln x}}=x} می‌توان هم‌ارزی برای {\displaystyle p(x)} یافت.

به روش تکرار ساده معادله را حل می‌کنیم.

{\displaystyle {\frac {x_{1}}{\ln x}}=x_{2}}

{\displaystyle {x_{1}}=x_{2}\ln(x)}

{\displaystyle p(x)=x\ln(x)}

اما باید توجه داشت چون به جای {\displaystyle \pi (x)} از تابع هم ارز آن استفاده شده پس:

{\displaystyle p(x)\sim \ x\ln(x)}

در نتیجه:

{\displaystyle \lim _{x\to \infty }{\frac {p(x)}{x\ln(x)}}=1}

قضیه ویلسون

قضیه ویلسون راهی برای تشخیص اعداد اول است. این قضیه بیان می‌کند به ازای هر عدد اول مانند {\displaystyle \;p} داریم {\displaystyle \;(p-1)!\equiv -1{\pmod {p}}}

این قضیه دوشرطی است بنابراین راهی برای تشخیص اعداد اول از مرکب است یعنی:

برای هر عدد صحیح x اگر رابطه زیر برقرار باشد آنگاه x عددی اول است در غیر این صورت x عددی مرکب است.

{\displaystyle \;} {\displaystyle \;(x-1)!\equiv -1{\pmod {x}}}

این قضیه تعمیم‌هایی به شکل زیر دارد:

تعمیم گاوس: کارل فریدریش گاوس ریاضیدان آلمانی در سال ۱۸۰۰ میلادی ثابت کرده که برای هر عدد طبیعی m>۲ عدد اول p

{\displaystyle \prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}}

در اینجا {\displaystyle \alpha } عددی صحیح و مثبت است.

بزرگترین عدد اول کشف شده

بزرگ‌ترین عدد اول کشف شده تا (۲۰۱۶) برابر دو به توان ۷۴ میلیون و ۲۰۷ هزار و ۲۸۱ منهای یک است.[۶] این عدد ۲۲٬۳۳۸٬۶۱۸ رقم دارد و یک عدد مرسن است. عدد مرسن عددی است که برابر ۲ به توان n منهای یک است. در سال ۲۰۱۸، طولانی‌ترین عدد اول که دارای ۲۳ میلیون رقم است؛ کشف شد. این عدد اول نیز یک عدد مرسن است که در جریان محاسبات در رایانه یک مهندس برق به نام جاناتان پیس در آمریکا در جریان پروژه‌ای برای کشف اعداد اول به نام «تحقیق اینترنتی بزرگ عدد مرسن» (GIMPS) کشف شد. این عدد را به اختصار و به‌طور قراردادی، M77232917 نامیده‌اند. پژوهش‌ها برای یافتن عددهای اول بزرگ دشوار و نیازمند نرم‌افزارهای خاص و همکاری علمی پژوهشگران هستند.[۷]

جایزه‌ها برای پیدا کردن اعداد اول

مؤسسه Electronic Frontier Foundation جایزه‌ای به مبلغ صدهزار دلار برای اولین کسی که یک عدد اول با حداقل ۱۰ میلیون رقم پیدا کند در نظر گرفته‌است. همچنین مبلغ ۱۵۰ هزار دلار برای کسی که یک عدد اول با ۱۰۰ میلیون رقم و ۲۵۰ هزار دلار برای ۱ میلیارد رقم در نظر گرفته شده‌است. این مؤسسه ممکن است مبلغ ۱۰۰ هزار دلار برای دپارتمان ریاضی دانشگاه UCLA که موفق به کشف یک عدد اول ۱۳ میلیون رقمی شدند پرداخت کند.

الگوهای توزیع اعداد اول

یکی از مسائل مورد توجه ریاضی‌دانان، چگونگی توزیع و ترتیب قرارگرفتن اعداد اول درون رشته اعداد طبیعی است. این چگونگی دارای الگوهایی است که یکی از آنها به «الگوی پیشرفت عددی» معروف است.
مثلاً اگر به عدد ۵ که عددی اول است، ۶ واحد اضافه کنیم به ۱۱ و اگر به ۱۱، ۶ واحد اضافه کنیم به ۱۷ و اگر دوباره اضافه کنیم، به ۲۳ و ۲۹ می‌رسیم که همگی اعدادی اولند. اما با اضافه کردن ۶ واحد دیگر به ۳۵ می‌رسیم که عددی اول نیست و الگو متوقف می‌گردد.

مسئله مورد توجه اینست که در هر الگوی پیشرفت چند عدد اول پیش از رسیدن به اولین عدد غیر اول، بدست می‌آیند؟ طولانی‌ترین رشته‌ای که تاکنون بدست آمده، ۲۲ عدد اول را شامل است. اولین عدد اول این رشته ۱۱۴۱۰۳۳۷۸۵۰۵۵۳ بوده که اگر عدد ۴۶۰۹۰۹۸۶۹۴۲۰۰ به آن اضافه شود عدد اول بعدی به‌وجود می‌آید و می‌توان ۲۲ بار عدد مذکور را به اعداد اول مرحله قبل افزود و عدد اولی جدید بدست آورد. دو ریاضی‌دان اثبات کرده‌اند برای هر رشته از اعداد اول می‌توان به یک رشته عددی رسید.[۸]

 

طبقه‌بندی اعداد مختلط {\displaystyle :\;\mathbb {C} } حقیقی {\displaystyle :\;\mathbb {R} } گویا {\displaystyle :\;\mathbb {Q} } صحیح {\displaystyle :\;\mathbb {Z} } طبیعی {\displaystyle :\;\mathbb {N} } یک: 1 اعداد اول اعداد مرکب صفر: 0 اعداد صحیح منفی کسری مختوم متناوب ساده مرکب گنگ اعداد گنگ جبری متعالی موهومی

منابع