اعداد اول

          امیر پارسا سلمان خواه 
            بازدید : 388
          چهارشنبه 06 فروردین 1393
           نظرات (0)
        

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

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

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

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

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

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

، ۱۰۳، ۱۰۷، ۱۰۹، ۱۱۳،۱۲۷، ۱۳۱، ۱۳۷، ۱۳۹

قضیه‌ها

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

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

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

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

$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$

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

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

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