عدد اول

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از اعداد اول)
پرش به: ناوبری، جستجو
غربال اراتوستنس الگوریتمی ساده و قدیمی برای یافتن همهٔ اعداد اول تا عدد صحیح برگزیده است. این الگوریتم پیش از غربال آتکین، که سریع‌تر و پیچیده‌تر بود، مورد استفاده قرار می‌گرفت. غربال اراتوستنس را اراتوستنس، ریاضیدان یونان باستان در قرن سوم پیش از میلاد ابداع کرد.

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

رقم یکان اعداد اول بزرگ‌تر از ۱۰ فقط ممکن است ارقام ۱، ۳، ۷، و ۹ باشد.

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

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

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

قضیه‌ها[ویرایش]

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

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

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

P_1,P_2,P_3, ... ,P_n

ضرب اعداد از P_i بزرگ‌تراست.

P_1 \times P_2 \times P_3 \times ... \times P_n> P_i

P_1 \times P_2 \times P_3 \times ... \times P_n + 1> P_i

P_1 \times P_2 \times P_3 \times ... \times P_n + 1 = P_{i_1} ... P_{i_k}

P_1 \times P_2 \times P_3 \times ... \times P_n + 1 = P_i \times X

P_{i_1} \times ... \times P_{i_k} = P_i \times X

P_1 \times P_2 \times P_3 \times ... \times P_n +1 = Y+1

P_{i_1} \times Y + 1 = P_{i_1} \times X

P_{i_1} \times X - P_{i_1} \times Y = 1

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

P_{i_1} = 1

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

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

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

قضایای اعداد اول[ویرایش]

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

2k=p_n+p_m

مثال:

 4= 2+ 2

 6= 3+ 3

 8= 5+ 3

10= 5+ 5

12= 7+ 5

14= 7+ 7

16=11+ 5

18=11+ 7

20=13+ 7

22=11+11

24=13+11

26=19+ 7

تابع شمارش اعداد اول[ویرایش]

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

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

 \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 ≥ ۳۵۵۹۹۱:

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

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

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

قضیه اعداد اول (prime number theorem)[ویرایش]

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

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

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

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

 \lim_{x \to \infty} \frac{p(x)}{x \ln(x)} = 1

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

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

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

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

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

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

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

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

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

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

\frac{x_1}{\ln x}=x_2

{x_1}=x_2 \ln(x)

p(x)=x \ln(x)

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

p(x)\sim\ x \ln(x)

در نتیجه:

 \lim_{x \to \infty} \frac{p(x)}{x \ln(x)} = 1

قضیه ویلسون راهی برای تشخیص اعداد اول[ویرایش]

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

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

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

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

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

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


\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}

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

کشف و محاسبه[ویرایش]

بزرگ‌ترین عدد اول کشف شده برابر دو به توان ۵۷میلیون و ۸۸۵هزار و ۱۶۱منهای یک است. این عدد یک عدد مرسن است. عدد مرسن عددی است که برابر ۲ به توان n منهای یک است.

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

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

الگوهای توزیع اعداد اول[ویرایش]

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

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

جستارهای وابسته[ویرایش]

پانویس[ویرایش]

  1. (دنبالهٔ A000040 در OEIS)
  2. ماهنامه علمی-فنی دانشمند، شماره ۵۳۷، ص ۱۷

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Prime_number»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد.
  • محسنیان، محمد. «کندوکاو مسئله‌ای دیرینه در زمینه اعداد اول». ماهنامه علمی-فنی دانشمند، تیر ۱۳۸۷، شماره پیاپی ۵۳۷، ص ۱۷.