قضیه اساسی حساب
قضیهٔ اساسی حساب (به انگلیسی: Fundamental theorem of arithmetic)، از قضایای مهم در نظریه اعداد است که نشان می‌دهد اعداد اول چگونه همانند بلوک‌های ساختمانی در ساختن سایر اعداد نقش دارند.
این قضیه به‌طور ساده بیان می‌کند که هر عدد صحیح به‌جز formula_1 و formula_2، به‌صورت حاصل‌ضربی از عوامل اول قابل نمایش است. همچنین این نمایش اعداد به‌صورت حاصل‌ضرب عوامل اول، صرف نظر از ترتیب عوامل یکتا است. به عنوان مثال، عدد ۶۰ را می‌توان به‌صورت formula_3 به حاصل‌ضرب عوامل اول نوشت.
اگر عدد formula_4 را به‌صورت formula_5 به حاصل ضرب عوامل اول بنویسم، این کار را اصطلاحاً تجزیه عدد formula_4 به عوامل اول می‌گوئیم. پس قضیهٔ اساسی حساب بیان می‌کند که هر عدد صحیح بجز formula_1 و formula_2، قابل تجزیه به عوامل اول است و این تجزیه صرف نظر از ترتیب عوامل یکتا است.
باید توجه داشت که از نظر تاریخی این قضیه اساساً توسط اقلیدس به اثبات رسیده‌است، اما اولین اثبات کامل از آن توسط گاوس در کتاب تحقیقات حساب منتشر شده‌است.
همچنین، با گسترش جبرمجرد و نظریه حلقه مفهومی مشابه در نظریه حلقه به عنوان حوزه تجزیه یکتا (UFD) به وجود آمد که در آن‌ها خاصیتی مشابه برقرار است که توسط کومر و زمانی که بروی قضیه آخر فرما کار می‌کرد معرفی شد. این نشان می‌دهد که اگر چه قضیهٔ اساسی حساب در حلقه اعداد صحیح بدیهی جلوه می‌کند، اما چنین چیزی در مورد هر حلقۀ دلخواه بدیهی نیست و ممکن است نادرست باشد. برهان قضیه شامل دو قسمت وجود و یکتایی است. ابتدا نشان می‌دهیم هر عدد را می‌توان به صورت حاصل ضربی از عوامل اول نوشت. این کار را مبتنی بر اصل استقراء روی formula_11 انجام می‌دهیم.
اگر formula_12 چون ۲ خود عددی اول است پس حکم برقرار است. فرض می‌کنیم حکم برای هر عدد طبیعی کوچک‌تر از formula_4 برقرار باشد. نشان می‌دهیم حکم برای formula_4 نیز درست است و بنابر اصل استقراء ریاضی نتیجه می‌گیریم حکم برای هر عدد طبیعی درست است.
اگر formula_4 اول باشد در این صورت چیزی برای اثبات نمی‌ماند و حکم برقرار است. اگر formula_4 اول نباشد در این صورت اعداد صحیح formula_17 وجود دارند که formula_18 و formula_19. چون formula_20 بنابر فرض استقراء formula_17 به حاصل‌ضرب عوامل اول تجزیه می‌شوند. پس formula_22 و formula_23 که در آن formula_24 و formula_25ها اعداد اول و نه لزوماً متمایز هستند؛ بنابراین formula_26 و لذا formula_4 نیز به حاصل‌ضرب عوامل اول تجزیه می‌شود.
حال نشان می‌دهیم این تجزیه صرف نظر از ترتیب عوامل یکتا است. برای اثبات این مطلب فرض می‌کنیم formula_4 عددی طبیعی بزرگ‌تر از یک، دلخواه و از این پس ثابت باشد و formula_29 و formula_30 دو تجزیۀ formula_4 به عوامل اول باشند. نشان می‌دهیم formula_32 و احیاناً با تجدید اندیس‌گذاری داریم formula_33.
اثبات را به استقراء روی formula_34 انجام می‌دهیم. اگر formula_35 به‌وضوح حکم برقرار است. فرض می‌کنیم حکم در مورد هر عدد کوچک‌تر از formula_34 درست باشد و نشان می‌دهیم حکم در مورد formula_34 نیز درست است.
چون formula_38 و formula_30 پس formula_40 حداقل یکی از formula_41ها را عاد می‌کند، بی‌آنکه به کلیت مطلب خللی وارد شود. می‌توان فرض کرد formula_42 (چرا که می‌توان اندیس‌گذاری را تجدید کرد و به‌صورت دلخواه نوشت) اما چون formula_43 اول است و formula_44 (بنابر اول بودن) پس لزوماً باید داشته باشیم formula_45. پس:
و بنابر فرض استقراء، formula_47 و احیاناً با تجدید اندیس‌گذاری:
پس formula_32 و احیاناً با تجدید اندیس‌گذاری:
در ابتدا مفهوم تجزیه به عوامل اول را توضیح دادیم و دیدم که بنابر قضیه اساسی حساب، هر عدد صحیح بجز یک و منفی یک، به حاصل ضرب اعداد اول قابل تجزیه است، اما این عوامل اول ممکن است متمایز نباشند. اگر عدد صحیح formula_4 را به صورت formula_52 بنویسم که در آن formula_24ها اعداد اول متمایز هستند، این تجزیه به عوامل اول را تجزیه استاندارد یا کانونیک formula_4 به عوامل اول می‌گوئیم. به عنوان مثال formula_55.
از قضیه اساسی حساب نشان می‌دهد چگونه اعداد اول مانند بلوک‌های ساختمان در تولید سایر اعداد صحیح نقش دارند. تجزیه یک عدد به عوامل اول می‌تواند اطلاعات زیادی را در مورد مقسوم علیه‌های آن عدد و به‌طور کلی ساختار آن عدد در اختیار ما بگذارد.
فرض کنید formula_4 عددی طبیعی و بزرگ‌تر از یک باشد و formula_52 تجزیه استاندارد formula_4 به عوامل اول باشد. همچنین فرض می‌کنیم formula_59 معرف تعداد مقسوم علیه‌های عدد formula_4 باشد. تجزیۀ formula_4 به عوامل اول نشان می‌دهد که هر مقسوم‌علیه formula_4 باید به صورت formula_63 باشد که formula_64 به وضوح برای هر formula_65، مقدار formula_66 را به formula_67 طریق می‌توان انتخاب کرد (با احتساب مقدار صفر) و در هر حالت یک مقسوم‌علیه formula_4 حاصل می‌شود. این کار بنا بر اصل شمارش به:
طریق امکان‌پذیر است. پس formula_59 (تعداد مقسوم علیه‌های عدد formula_4) برابر است با:
به عنوان مثال formula_73.
تجزیۀ یک عدد به عوامل اول در مطالعۀ توابع حسابی مانند تابع مقسوم علیهی کاربرد فراوان دارد. برای هر عدد طبیعی formula_4، مجموع قوای formula_75-ام مقسوم علیه‌های formula_4 را با formula_77 نشان می‌دهیم که در آن formula_75 عددی حقیقی یا مختلط است. پس:
که مجموع فوق روی مقسوم علیه‌های formula_4 است. حال اگر formula_81، در این صورت عبارت فوق همان تعداد مقسوم علیه‌های formula_4 است که در قسمت قبل آن را بررسی کردیم. در حالت خاص دیگر اگر formula_83، در این صورت:
که همان مجموع مقسوم علیه‌های عدد formula_4 است که اکنون می‌خواهیم آن را بررسی کنیم. ابتدا فرض می‌کنیم formula_4 توانی از عدد اول formula_87 چون formula_88 باشد. در این صورت مقسوم علیه‌های formula_4 عبارت‌اند از:
پس:
حال در حالتی کلی‌تر فرض می‌کنیم formula_52 تجزیه استاندارد formula_4 به عوامل اول باشد. در این صورت هر مقسوم‌علیه formula_4 به‌صورت formula_63 خواهد بود که formula_64. پس:
پس:
در نتیجه:
پس دیدیم که چگونه می‌توان مجموع مقسوم علیه‌های عدد طبیعی formula_4 را محاسبه کرد و البته مطلب فوق از ضربی بودن تابع مقسوم علیهی نیز قابل استنتاج است.
فرض کنید formula_4 عددی طبیعی بزرگ‌تر از یک باشد و
مجموعۀ همۀ مقسوم علیه‌های formula_4 باشد. به‌علاوه، حاصل‌ضرب مقسوم علیه‌های formula_4 را با formula_105 نشان می‌دهیم. در این صورت برای هر formula_106 چون formula_107، پس عددی چون formula_41 وجود دارد که formula_109. اما چون formula_110 پس formula_41ها نیز یک مقسوم علیه‌های formula_4 و لذا اعضای formula_113 می‌باشند. پس:
بنابراین
به این ترتیب حاصل ضرب مقسوم‌علیه‌های formula_4 را نیز محاسبه کردیم. به عنوان مثال formula_117.
روش دیگری به‌جز روش الگوریتم اقلیدس برای تعیین بزرگ‌ترین مقسوم‌علیه مشترک (ب. م. م) و کوچک‌ترین مضرب مشترک (ک. م. م) دو عدد از راه تجزیۀ آن‌ها به عوامل اول وجود دارد که البته از آنجایی که تجزیۀ اعداد بزرگ پیچیده خواهد بود، چندان روشی کارساز نخواهد بود.
فرض کنید formula_17 دو عدد طبیعی بزرگ‌تر از یک باشند و formula_119 و formula_120 تجزیۀ استاندارد formula_17 به عوامل اول باشد. در این صورت اگر ب. م. م formula_17 را با formula_123 نشان دهیم، داریم:
که در آن برای هر formula_65 داریم formula_126.
به عبارت دیگر، ب. م. م دو عدد formula_17 عبارت است از حاصل‌ضرب عوامل اول مشترک آن‌ها با کمترین توان.
همچنین اگر ک. م. م formula_17 را با formula_129 نشان دهیم، داریم:
که در آن برای هر formula_65، داریم formula_132.
به عبارت دیگر، ک. م. م دو عدد formula_17 عبارت است از حاصل‌ضرب عوامل اول مشترک یا غیر مشترک آن‌ها با بزرگ‌ترین توان. برای اثبات قضایای فوق می‌توانید به مقالات بزرگ‌ترین مقسوم‌علیه مشترک و کوچک‌ترین مضرب مشترک مراجعه کنید.