بخشپذیری و اعداد اول
بخشپذیری، بزرگترین مقسومعلیه مشترک، و اعداد اول اساس نظریه اعداد را تشکیل میدهند: هر عدد صحیح به صورت ضربی از اعداد اول ساخته شده است، و نحوه ساخت آن تقریباً بر هر نتیجه بعدی حاکم است.
Definition
یک عدد صحیح a، عدد صحیح b را میشمارد اگر b برابر با a ضربدر یک عدد صحیح باشد؛ عدد اول عددی صحیح بزرگتر از یک است که تنها مقسومعلیههای مثبت آن یک و خودش هستند. بخشپذیری و اعداد اول به تجزیه ضربی اعداد صحیح و بلوکهای سازنده تجزیهناپذیر آن تجزیه مربوط میشوند.
Scope
این موضوع به رابطه بخشپذیری در اعداد صحیح، الگوریتم تقسیم، بزرگترین مقسومعلیههای مشترک و کوچکترین مضربهای مشترک محاسبه شده از طریق الگوریتم اقلیدسی، اتحاد بزو، لم اقلیدس، قضیه اساسی حساب، و نظریه مقدماتی اعداد اول — بینهایت بودن، اکتشافات توزیع، و اول بودن آنها — میپردازد.
Core questions
- چگونه الگوریتم اقلیدسی بزرگترین مقسومعلیههای مشترک را محاسبه میکند و اتحاد بزو را به دست میدهد؟
- چرا لم اقلیدس تجزیه به اعداد اول را منحصر به فرد میسازد؟
- چگونه میتوان اثبات کرد که بینهایت عدد اول وجود دارد، و چنین اثباتهایی چه چیزی را آشکار میکنند؟
- اعداد اول چگونه در میان اعداد صحیح توزیع شدهاند، و اول بودن در عمل چگونه تعیین میشود؟
Key theories
- الگوریتم تقسیم و الگوریتم اقلیدسی
- هر عدد صحیح تقسیم بر یک عدد صحیح مثبت، یک خارج قسمت و باقیمانده منحصر به فرد به جا میگذارد؛ تکرار این فرآیند بزرگترین مقسومعلیه مشترک را میدهد و از طریق جایگزینی معکوس، اعداد صحیحی را که آن را به عنوان یک ترکیب خطی بیان میکنند (اتحاد بزو) به دست میآورد.
- قضیه اساسی حساب
- هر عدد صحیح بزرگتر از یک، حاصلضرب اعداد اولی است که تا ترتیب منحصر به فرد است؛ لم اقلیدس (یک عدد اول که حاصلضرب را میشمارد، یکی از عوامل را نیز میشمارد) گام کلیدی است.
- بینهایت بودن اعداد اول
- استدلال کلاسیک اقلیدس نشان میدهد که هیچ فهرست محدودی از اعداد اول کامل نیست؛ فرمول حاصلضرب اویلر برای تابع زتا یک اثبات تحلیلی ارائه میدهد و چگالی اعداد اول را از طریق واگرایی مجموع معکوسهای اعداد اول کمیسازی میکند.
Clinical relevance
تجزیه سریع و آزمونهای اول بودن برای رمزنگاری اساسی هستند: امنیت RSA بر دشواری تجزیه حاصلضربهای بزرگ دو عدد اول استوار است، در حالی که آزمونهای کارآمد اول بودن (مانند میلر-رابین) تولید کلید را عملی میسازند.
History
عناصر اقلیدس (حدود ۳۰۰ پیش از میلاد) از قبل شامل الگوریتم اقلیدسی، لم اقلیدس، و اثبات بینهایت بودن اعداد اول بود. غربال اراتوستن اولین روش سیستماتیک برای فهرست کردن اعداد اول را ارائه داد، و کارهای قرن هجدهم و نوزدهم توسط اویلر، لژاندر، و گاوس توزیع اعداد اول را به عنوان یک مسئله کمی بازتعریف کردند.
Key figures
- Euclid
- Eratosthenes
- Leonhard Euler
- Etienne Bezout
Related topics
Seminal works
- hardyWright2008
Frequently asked questions
- آیا یک عدد اول است؟
- خیر. یک طبق تعریف مستثنی شده است تا تجزیه به عوامل اول منحصر به فرد باشد؛ اگر یک به عنوان عدد اول محسوب میشد، هر عدد بینهایت تجزیه داشت.
- اتحاد بزو برای چه کاری استفاده میشود؟
- این اتحاد بیان میکند که بزرگترین مقسومعلیه مشترک دو عدد صحیح یک ترکیب خطی صحیح از آنها است، که اساس محاسبه معکوسهای پیمانهای و حل معادلات دیوفانتین خطی است.