اعداد اول

اعداد اول اعداد بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌کننده ای را در برابر ریاضی دانان مطرح ساخته اند. تعریف این اعداد کاملا ساده است، رفتار آنها در  

 

اعداد اول

اعداد اول اعداد بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌کننده ای را در برابر ریاضی دانان مطرح ساخته اند. تعریف این اعداد کاملا ساده است، رفتار آنها در

اعداد اول

اعداد اول اعداد بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌کننده ای را در برابر ریاضی دانان مطرح ساخته اند. تعریف این اعداد کاملا ساده است، رفتار آنها در سلسله اعداد و نحوه ظاهر شدنشان در آن کاملابی‌نظم و فاقد قاعده به نظر می‌آید و هرچه شمار بیشتری از آنها شکارمی‌شوند، کار شکار عدد بعدی دشوارترمی‌شود طی قرنهای متمادی ریاضی دانان در شرق و غرب عالم به جستجوی راههایی برای دستیابی به اعداد اول برخاسته‌اند و با این همه بهترین روشهایی که تا بحال در این زمینه ابداع شده چنان کند است که حتی پر سرعت‌ترین کامپیوتر های کنونی نیز نمی‌توانند کمک چندانی در شکار این اعداد شگفت انگیز کنند. بطوریکه اگر چندین میلیون بار به سرعت کامپیوتر های کنونی افزوده شود، تنها چند رقم به شماره ارقام بزرگترین عدد اولی که تا به حال شناخته شده افزوده می‌گردد. ریاضی دانان در آرزوی دست یافته به روشی هستند که با استفاده از آن بتوانند با سرعت به یافتن اعداد اول توفیق یابند و یا اگر با عددی هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند که آیا عدد اول است ؟ یک گروه از ریاضی دانان هندی مدعی شده‌اند که در آستانه دستیابی به همان آزمونی هستند که ریاضی دانان قرنها مشتاقانه در آرزویش بوده اند. مانیندرا اگراوال ‪ ,Manindra Agrawalو دانشجویانش نیراج کایال‪Neeraj ‪Kayalو نیتین سکسنا ‪ Nitin Saxenaدر موسسه تکنولوژی کانپور مدعی شده‌اند که در آستانه تکمیل آزمونی هستند که اول بودن یا نبودن هر عدد طبیعی را با سرعت مشخص می‌کند. این آزمون در صورتی که تکمیل شود می‌تواند تبعات و نتایج بسیار گسترده‌ای برای جهان کنونی به بار آورد  در سال ‪ ۲۰۰۱دو تن از دانشجویان او یعنی کایال و سکسنا به یک نکته بسیار حساس و فنی توجه کردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندک اندک برایشان روشن شد که تنها یک مانع در راه تکمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد. مانع از این قرار بود که روش آنان تنها در صورتی کار می‌کرد که عدد اول مورد نظر که با ‪ pنمایش داده می‌شود همواره در محدوده خاصی جای داشته باشد که با اعدادی که در آزمون شرکت داده می‌شوند مرتبط باشد. مشخصه ویژه این مانع آن است که عدد " ‪ p-1 " باید یک مقسوم علیه یا بخشیاب بسیار بزرگ باشد. گروه سه نفر ریاضی دانان هندی برای غلبه بر مشکل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند که در سال ‪ ۱۹۸۵یک ریاضی‌دان فرانسوی به نام اتن فووری از دانشگاه پاریس ‪ ۱۱این نکته را به صورت ریاضی اثبات کرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد. اما این موفقیت "مشروط" بود. به این معنی که این روش برای اعداد اولی که انسان در حال حاضر می‌توان به سراغ آنها برود از کارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات که متناسب با ارقام عدد اول مورد نظر بود، با آهنگ ‪ ۱۰۱۲ازدیاد پیدا می کرد. در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ‪ ۱۰۷.۵کاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود که تعداد ارقام عدد اولی که قصد شکار و یافتن آن را داریم در حدود ‪ ۱۰۱۰۰۰باشد.

درحال حاضر بسیاری از معاملات تجاری و نقل و انتقالات مالی و نیز مبادله اطلاعات محرمانه از طریق شبکه های مخابراتی مانند اینترنت و با بهره گیری از رمز کردن پیامها به انجام می‌رسد. اعداد اول در تنظیم این قبیل رمزها نقشی اساسی بر عهده دارند و از همین رو دستیابی به اعداد اول جدید که دیگران از آن بی‌خبر باشند برای سازندگان این رمزها و نیز مشتریان آنان از اهمیت زیاد برخوردار است. اما اگر روش این محققان هندی تکمیل شود در آن صورت امنیت این قبیل نقل و انتقالات در معرض خطر جدی قرار خواهد گرفت. سابقه قرار گرفتن ریاضی دانان تحت جاذبه اعداد اول به قرنها پیش باز می گردد. در سال ‪ ۱۸۰۱کارل گائوس از بزرگترین ریاضی دانان اعلام کرد که مساله تشخیص اعداد اول از اعداد غیر اول یکی از مهمترین مسائل حساب به شمار می‌آید. اعداد اول به یک معنا همان نقشی را در سلسله اعداد بازی می‌کنند که اتمها در ساختار بنای کیهان دارند- این اعداد سنگ بنای ناپیدای دیگر اعداد محسوب می‌شوند. یکی از عادی‌ترین راههای شناسایی اعداد اول تقسیم آن به دیگر اعداد است. از طرف دیگر با اندکی تامل روشن می‌شود که اعداد زوج عدد اول نیستند زیرا همگی بر ‪ ۲قابل قسمتند. اعدادی که بتوان جذر آنها را به دست آورد نیز اول نیستند. اما این روشها برای شناسایی اعداد اول بزرگ به کلی بی‌فایده‌اند. به عنوان مثال اگر عدد اولی دارای ‪ ۱۰۰رقم باشد در آن صورت کل عمر باقیمانده از کیهان بر اساس نظریه های جدید کیهانشناسی نیز برای مشخص کردن اول بودن یا نبودن این عدد با این شیوه های متعارف کفایت نمی‌کند. بنابراین ریاضی دانان به سراغ روشهای دیگر رفته‌اند. مهمترین سوال در مورد همه این روشها آن است که با چه سرعتی می‌توانند یک عدد اول را مشخص کنند و با ازدیاد ارقام عدد اول زمان لازم برای محاسبه چه اندازه طولانی تر می شود. اگر به عنوان مثال زمان محاسبه به توان ثابتی از شمار ارقام عدد ازدیاد یابد در آن صورت این روش روش قابل قبولی به شمار آورده می‌شود . به این نوع روشها که زمان به صورت توانی در آنها افزوده می‌شود "روشهای توانی" می‌گویندروشهای دیگر که زمان در آنها با سرعت بیشتری افزایش می‌یابد روشهای غیرتوانی نام دارند. به عنوان مثال روش تقسیم معمولی یک روش غیرتوانی برای یافتن اعداد اول است. در این روش زمان لازم برای تعیین اول بودن یک عدد با ‪ dرقم، برابر با ‪ /۱۰d/2این نوع روشها بسیار نامناسبند.   اعداد اول یکی از اساسی ترین چیز ها در ریاضیات هستند. آنها پس از قرن ها مطالعه هنوز دارای رموز بسیاری اند. ساختار مجموعه اعداد اول هنوز به درستی شناخته شده نیست. توضیح چگونگی توزیع آنها در قلب ریاضیات قرار دارد و نقش های مهمی برای مثال در زمینه رمز گشایی دارند. برای مطالعه در مورد اعداد اول محققین چیزی که به نام لنز ریاضیاتی معروف است را توسعه داده اند که به آنها اجازه می دهد تا در منظره های خاصی از اعداد اول فوکوس کنند.      به تازگی دو ریاضیدان به نام های جان فریدلندر از دانشگاه تورونتو و هنریک ایوانیچ از دانشگاه روتگرز نیوجرسی دنیای ریاضیات را با خبر ساختن لنز جدیدی برای پالودن هرچه بیشتر اعداد اول متحیر ساختند. کار آنها مخصوصا از این لحاظ شگفت انگیز است که مسئله مهمی در ریاضیات که پیشرفتی در آن در صد سال اخیر رخ نداده را حل می کند.

     اهمیت کار فریدلندر و ایوانیچ را در تاریخچه آن می توان دید. اقلیدس اولین کسی بود که نشان داد بینهایت عدد اول در بین اعداد صحیح وجود دارد. مدت ها بعد در سال 1837 گوستاو لجن دیریکله نشان داد که اگر aو dنسبت به هم اول باشند در تصاعد حسابی a, a+d, a+2d, a+3d,…بی نهایت عدد اول وجود دارد.

با توجه به کارهای دیریکله دو سؤال به ذهن می رسد:

"در چه دنباله های دیگری از اعداد می توان بی نهایت عدد اول یافت؟" کسی می تواند چند وقت به چند وقت ظاهر شدن  اعداد اول در این دنباله ها را تعیین کند؟"      تکنیک هایی که در دهه 1890 اختراع شد به ریاضیدانان اجازه می داد تا تقریب خوبی در مورد چند وقت به چند وقت ظاهر شدن اعداد اول در اعداد صحیح و همچنین دنباله هایی که دیریکله بررسی نمود بدست آورند. اعداد طبیعی به چند عدد نخست مجموعه اعداد اول

• بخش‌پذیری بر 2: شرط لازم برای آن که یک عدد بر 2 بخش‌پذیر باشد، آن است که رقم یکان آن زوج باشد مانند 30 ، 1996 ، 204.
• بخش‌پذیری بر 3: شرط لازم برای آن که عددی بر 3 بخش‌پذیر باشد آن است که مجموع ارقام آن عدد بر 3 بخش پذیر باشد. مانند 192 (زیرا مجموع ارقام آنها برابر 12 می‌باشد).
• بخش‌پذیری بر 5: شرط لازم برای آن که یک عدد بر 5 بخش‌پذیر باشد آن است که رقم یکان آن صفر یا 5 باشد، مانند 205 ، 410.
• بخش‌پذیری بر 7: عددی بر 7 بخش‌پذیر است که اگر رقم اول سمت چپ آن را در 3 ضرب کرده و با رقم دوم سمت چپ جمع کنیم وحاصل را بر 7 تقسیم کنیم، سپس باقیمانده تقسیم را دوباره در 2 ضرب کرده و با رقم سوم از سمت چپ جمع و حاصل را بر 7 تقسیم کنیم و همین عملها را تا آخرین رقم ادامه دهیم، در پایان باقیمانده بر 7 تقسیم بر 7 برابر با صفر باشد.
• بخش‌پذیری بر 11: عددی بر 11 بخش‌پذیر است که اختلاف مجموع ارقام مرتبه زوج (یکان ، صدگان ، ده هزارگان و ... ) با مجموع ارقام مرتبه فرد (دهگان ، هزارگان ، صدگان و ...) بر 11 بخش‌پذیر باشد.

در حالت m

عددی مانند m اول است اگر و تنها اگر m بر هیچ کدام از اعداد اول تابیشتر از جذر m بخش‌پذیر نباشد. برای تجزیه یک عدد به حاصلضرب عاملهای اول ، آن را به کوچکترین عدد اولی که بر آن بخش‌پذیر باشد تقسیم می‌کنیم و خارج قسمت را نیز بر کوچکترین عدد اولی که بر آن بخش پذیر باشد تقسیم می‌کنیم و این کار را تاجایی ادامه می‌دهیم که خارج قسمت یک باشد. در این صورت حاصلضرب مقسوم علیه‌ها ، حاصلضرب عاملهای اول عدد مورد نظر خواهد بود. مانند 45 = 2² + 3²

کوچکترین مضرب مشترک دو عدد

کوچکترین مضرب مشترک دو عدد a و b عبارت است از کوچکترین عددی که بر هم بر a و هم بر b بخش‌پذیر باشد. برای پیدا کردن کوچکترین مضرب مشترک دو عدد b,a (ک.م.م) که آن را به صورت a,b نمایش می‌دهیم، ابتدا دو عدد a و b را به حاصلضرب عاملهای اول تجزیه می‌کنیم. سپس کوچکترین مضرب مشترک دو عدد عبارت است از حاصلضرب عاملهای مشترک و غیر مشترک با توان بیشتر که در تجزیه دو عدد موجود است. به عنوان مثال ک.م.م دو عدد 36 و45 برابر است با 2²X3²X5 یعنی 180 خواهد بود.

بزرگترین مقسوم علیه مشترک دو عدد

بزرگترین مقسوم علیه مشترک دو عدد a و b عبارت است از بزرگترین عددی که هم a و هم b بر آن بخش‌پذیر باشد. برای پیدا کردن بزرگترین مقسوم علیه مشترک دو عدد b,a را به حاصلضرب (ب.م.م) که آن را به صورت (a,b) نمایش می‌دهیم؛ ابتدا دو عدد a و b را به حاصلضرب عاملهای اول تجزیه می‌کنیم، سپس بزرگترین مقسوم علیه مشترک دو عدد عبارت است از حاصلضرب عاملهای مشترک دو عدد a و b با توان بیشتر که در تجزیه دو عدد موجود است. به عنوان مثال ب.م.م دو عدد 45 و 36 برابر با 3² یعنی 9 می‌باشد.

دو عدد متباین

دو عدد را نسبت به هم اول یا متباین گویند هر گاه ب.م.م آن دو عدد برابر با 1 باشد. برای مثال دو عدد 8 و 9 نسبت به هم اول هستند، زیرا 1=(9 و 8). بزرگترین مقسوم علیه مشترک n عدد نیز به همین صورت تعریف می‌شود. باید توجه داشت که در این حالت منظور از عاملهای مشترک ، اعداد اولی هستند که در تجزیه تمامی n عدد مشترک می‌باشد. برای هر دو عدد طبیعی a,b تساوی (a ,b).a,b=ab برقرار می‌باشد.

تعداد مقسوم علیه های مثبت یک عدد

در حالت کلی اگر عدد تجزیه به عوامل a به صورت P₂^α₂X P_n^α_nXP₁^α₁ باشد، که در آن P₁ ، P_n ، ... ، P₂ اعداد اول متمایز می باشند، برای نوشتن یک مقسوم علیه از a می‌توانیم از عاملهای P₁ به تعداد 0 و1 و......و α₁ و از عاملهای P₂ به تعداد 0 و 1و......و α₂ و.... و بالاخره از عاملهای P₁ به تعداد 0 و 1 و ... α_n انتخاب کنیم که طبق اصل ضرب این عدد به تعداد (α₁+1)X(α₂+1)….(α_n+1) مقسوم علیه خواهد داشت.