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

این قضیه ایده شهودی کم شدن چگالی اعداد اول در اعداد صحیح بزرگ را به‌صورت صوری و دقیق‌تر بیان می‌کند. قضیه اعداد اول به‌صورت مستقل و جداگانه توسط ژاک آدامار و چارلز پوسین در ۱۸۹۶ با استفاده از ایده‌های معرفی‌شده از سوی برنارد ریمان (به‌خصوص تابع زتای ریمان) اثبات شد.

اولین توزیع این‌چنینی که پیدا شد ${\displaystyle \pi (N)\sim {\frac {N}{log(N)}}}$ بود که در آن ${\displaystyle \pi (N)}$ تابع شمارنده تعداد اعداد اول و ${\displaystyle \mathrm {log(N)} }$ لگاریتم طبیعی عدد ${\displaystyle \mathrm {N} }$ است. بدین‌معنی که با بزرگ شدن ${\displaystyle \mathrm {N} }$ به‌میزان کافی، احتمال این که یک عدد صحیح تصادفی کوچک‌تر مساوی ${\displaystyle \mathrm {N} }$ اول باشد بسیار به ${\displaystyle {\frac {1}{log(N)}}}$ نزدیک است. بنابراین، احتمال اول بودن یک عدد صحیح با حداکثر ${\displaystyle \mathrm {2n} }$ رقم (برای ${\displaystyle \mathrm {n} }$های به اندازه کافی بزرگ) حدوداً نصف عدد صحیح تصادفی با حداکثر ${\displaystyle \mathrm {n} }$رقم است. به‌عنوان مثال، در میان اعداد صحیح مثبت با حداکثر ۱۰۰۰ رقم، حدود یک عدد از هر ۲۳۰۰ تا اول است (${\displaystyle log(10^{1000})\approx 2302.6}$)، درحالی‌که در میان اعداد صحیح با حداکثر ۲۰۰۰ رقم، حدود یکی از هر ۴۶۰۰ تا اول هستند (${\displaystyle log(10^{2000})\approx 4605.2}$). به بیان دیگر، میانگین شکاف بین اعداد اول پشت سر هم در میان ${\displaystyle \mathrm {N} }$عدد صحیح (از یک تا ${\displaystyle \mathrm {N} }$) حدود ${\displaystyle \mathrm {log(N)} }$ است.

اگر${\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)}}}$	${\displaystyle {\frac {x}{\pi (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}$