نمایش مبدأ برای قضیه اساسی حساب

{{اشتباه نشود|قضیهٔ اساسی حسابان}}
'''قضیهٔ اساسی حساب''' {{به انگلیسی|Fundamental theorem of arithmetic}} از قضایای مهم در [[نظریه اعداد|نظریۀ اعداد]] است که نشان می‌دهد [[عدد اول|اعداد اول]] چگونه همانند بلوک‌های ساختمانی در ساختن سایر اعداد نقش دارند.

این قضیه به‌طور ساده بیان می‌کند که هر [[عدد صحیح]] به‌جز <math>1</math> و <math>-1</math>، به‌صورت حاصل‌ضربی از عوامل اول قابل نمایش است. همچنین این نمایش اعداد به‌صورت [[حاصل ضرب|حاصل‌ضرب]] عوامل اول، صرف نظر از ترتیب عوامل یکتا است. به عنوان مثال، عدد ۶۰ را می‌توان به‌صورت <math>2 \cdot 2 \cdot 3 \cdot 5 = 60</math> به حاصل‌ضرب عوامل اول نوشت.<ref>{{Cite journal|last=Colilli|first=Paul|date=January 1981|title=Bernardo, Aldo S. and Rigo Mignani. Ritratto Dell’Italia. 2nd Ed. Lexington, Massachusetts and Toronto: D.C. Heath and Company, 1978Bernardo, Aldo S. and Rigo Mignani. Ritratto Dell’Italia. 2nd Ed. Lexington, Massachusetts and Toronto: D.C. Heath and Company, 1978. Pp. IX, 317.|url=http://dx.doi.org/10.3138/cmlr.37.2.351|journal=Canadian Modern Language Review|volume=37|issue=2|pages=351–352|doi=10.3138/cmlr.37.2.351|issn=0008-4506}}</ref>

اگر عدد <math>n</math> را به‌صورت <math>n=p_1p_2p_3\cdots p_r</math> به حاصل ضرب عوامل اول بنویسم، این کار را اصطلاحاً تجزیه عدد <math>n</math> به عوامل اول می‌گوئیم. پس قضیهٔ اساسی حساب بیان می‌کند که هر عدد صحیح به‌جز <math>1</math> و <math>-1</math>، قابل تجزیه به عوامل اول است و این تجزیه صرف نظر از ترتیب عوامل یکتا است.<ref>{{Cite journal|last=J. H. P.|date=June 1970|title=Rei Río, Amelia Agostini de. Flores del romancero. Englewood Cliffs, New Jersey, Prentice-Hall, 1970Rei Río, Amelia Agostini de. Flores del romancero. Englewood Cliffs, New Jersey, Prentice-Hall, 1970. 276 pp. $3.95 U.S.|url=http://dx.doi.org/10.3138/cmlr.26.4.77b|journal=Canadian Modern Language Review|volume=26|issue=4|pages=77–77|doi=10.3138/cmlr.26.4.77b|issn=0008-4506}}</ref>

== قضیۀ اساسی حساب و برهان آن ==
باید توجه داشت که از نظر تاریخی این قضیه اساساً توسط [[اقلیدس]] به اثبات رسیده‌است، اما اولین اثبات کامل از آن توسط [[گاوس]] در کتاب تحقیقات حساب منتشر شده‌است.

همچنین، با گسترش [[جبرمجرد]] و [[نظریه حلقه|نظریۀ حلقه]]، مفهومی مشابه در [[نظریه حلقه|نظریۀ حلقه]] به عنوان [[حوزه تجزیه یکتا|حوزۀ تجزیۀ یکتا]] ('''UFD''') به‌وجود آمد که در آن‌ها خاصیتی مشابه برقرار است که توسط [[کومر]] و زمانی که بروی [[قضیه آخر فرما]] کار می‌کرد، معرفی شد. این نشان می‌دهد که اگر چه قضیهٔ اساسی حساب در حلقۀ اعداد صحیح بدیهی جلوه می‌کند، اما چنین چیزی در مورد هر حلقۀ دلخواه بدیهی نیست و ممکن است نادرست باشد.

;قضیۀ اساسی حساب: هر عدد صحیح <math>n</math> که <math>n\not=\pm1</math> است را می‌توان به‌صورت حاصل‌ضرب عوامل اول نوشت. به‌علاوه، این نمایش به عوامل اول صرف نظر از ترتیب عوامل یکتا است.<ref>{{یادکرد||کتاب=آشنایی با نظریه اعداد|نویسنده=ویلیام دبلیو. ادامز، لری جوئل گولدشتین|ترجمه=دکتر آدینه محمد نارنجانی|ناشر=مرکز نشر دانشگاهی|شهر=تهران|سال=۱۳۸۴|شابک=964-01-0070-6}}</ref>

;اثبات:<ref>{{یادکرد|||کتاب=نظریه تحلیلی اعداد (۱)|نویسنده=تام آپوستل|ترجمه=دکتر [[علی‌اکبر عالم‌زاده]]-علی‌اکبر رحیم‌زاده|ناشر=نشر منصوری|شهر=تهران|سال=۱۳۷۶|شابک=964-6166-06-7}}</ref> برای اثبات کافی است قضیه را فقط برای [[اعداد طبیعی]] ثابت کنیم.

برهان [[قضیه]] شامل دو قسمت وجود و یکتایی است. ابتدا نشان می‌دهیم هر عدد را می‌توان به صورت [[حاصل ضرب|حاصل‌ضربی]] از عوامل اول نوشت. این کار را مبتنی بر اصل [[استقراء ریاضی|استقراء]] روی <math>n \!</math> انجام می‌دهیم.

اگر <math>n=2</math>، چون ۲ خود عددی اول است، پس حکم برقرار است. فرض می‌کنیم حکم برای هر [[عدد طبیعی]] کوچک‌تر از <math>n = k</math> برقرار باشد. نشان می‌دهیم که حکم برای <math>n = k</math> نیز برقرار است و بنابر اصل [[استقراء ریاضی]] نتیجه می‌گیریم که حکم برای هر عدد طبیعی‌ای درست است.

اگر <math>k</math> اول باشد در این صورت چیزی برای اثبات نمی‌ماند و حکم برقرار است. اگر <math>k</math> اول نباشد در این صورت اعداد صحیح <math>a,b</math> وجود دارند که <math>k = ab</math> و <math>1 < a \le b < k </math>. چون <math>a,b < k</math>، پس بنابر فرض استقراء <math>a</math> و <math>b</math> به حاصل‌ضرب عوامل اول تجزیه می‌شوند. پس <math>a = p_1p_2p_3\cdots p_r</math> و <math>b = q_1q_2q_3\cdots q_s</math> که در آن <math>p_i</math> و <math>q_j</math>-ها اعداد اول و نه لزوماً متمایز هستند؛ بنابراین <math>k = ab = p_1p_2\cdots p_rq_1q_2\cdots q_s</math> و لذا <math>k</math> نیز به حاصل‌ضرب عوامل اول تجزیه می‌شود.

حال نشان می‌دهیم این تجزیه صرف نظر از ترتیب عوامل یکتا است. برای اثبات این مطلب فرض می‌کنیم <math>n</math> عددی طبیعی بزرگ‌تر از یک، دلخواه و از این پس ثابت باشد و <math>n = p_1p_2p_3\cdots p_r</math> و <math>n = q_1q_2q_3\cdots q_s</math> دو تجزیۀ <math>n</math> به عوامل اول باشند. نشان می‌دهیم <math>r = s</math> و احیاناً با تجدید اندیس‌گذاری داریم <math>p_1=q_1,p_2=q_2,... ,p_r=q_s</math>.

اثبات را به استقراء روی <math>r</math> انجام می‌دهیم. اگر <math>r=1</math> به‌وضوح حکم برقرار است. فرض می‌کنیم حکم در مورد هر عدد کوچک‌تر از <math>r</math> درست باشد و نشان می‌دهیم حکم در مورد <math>r</math> نیز درست است.

چون <math>p_r \mid n</math> و <math>n = q_1q_2q_3\cdots q_s</math>، پس <math>p_r</math> حداقل یکی از <math>q_i</math>-ها را عاد می‌کند. بی‌آنکه به کلیت مطلب خللی وارد شود، می‌توان فرض کرد <math>p_r \mid q_s</math> (چرا که می‌توان اندیس‌گذاری را تجدید کرد و به‌صورت دلخواه نوشت)، اما چون <math>q_s</math> اول است و <math>p_r >1</math> (بنابر اول بودن)، پس لزوماً باید داشته باشیم <math>p_r=q_s</math>. پس:
{{وسط‌چین}}
:<math>p_1p_2p_3\cdots p_{r-1}=q_1q_2q_3\cdots q_{s-1}</math>
{{پایان وسط‌چین}}
و بنابر فرض استقراء، <math>r-1=s-1</math> و احیاناً با تجدید اندیس‌گذاری:
{{وسط‌چین}}
:<math>p_1=q_1,p_2=q_2,\cdots ,p_{r-1}=q_{s-1}</math>
{{پایان وسط‌چین}}
پس <math>r = s</math> و احیاناً با تجدید اندیس‌گذاری:
{{وسط‌چین}}
:<math>p_1=q_1,p_2=q_2,\cdots ,p_{r-1}=q_{s-1},p_r=q_s</math>
{{پایان وسط‌چین}}

=== تجزیه استاندارد ===
در ابتدا مفهوم تجزیه به عوامل اول را توضیح دادیم و دیدم که بنابر قضیۀ اساسی حساب، هر عدد صحیح به‌جز یک و منفی یک، به حاصل‌ضرب اعداد اول قابل تجزیه است، اما این عوامل اول ممکن است متمایز نباشند. اگر عدد صحیح <math>n</math> را به‌صورت <math>n=p_1^{\alpha_1}.p_2^{\alpha_2}\cdots p_r^{\alpha_r}</math> بنویسم که در آن <math>p_i</math>-ها اعداد اول متمایز هستند، این تجزیه به عوامل اول را تجزیه استاندارد یا کانونیک <math>n</math> به عوامل اول می‌گوئیم. به عنوان مثال: <math>1200=2^4\cdot 3\cdot 5^2</math>.

== کاربرد ==
قضیۀ اساسی حساب نشان می‌دهد چگونه اعداد اول مانند بلوک‌های ساختمان در تولید سایر اعداد صحیح نقش دارند. تجزیۀ یک عدد به عوامل اول می‌تواند اطلاعات زیادی را در مورد مقسوم علیه‌های آن عدد و به‌طور کلی ساختار آن عدد در اختیار ما بگذارد.

=== یافتن تعداد مقسوم علیه‌های یک عدد ===
فرض کنید <math>n</math> عددی طبیعی و بزرگ‌تر از یک باشد و <math>n=p_1^{\alpha_1}.p_2^{\alpha_2}...p_r^{\alpha_r}</math> تجزیه استاندارد <math>n</math> به عوامل اول باشد. همچنین فرض می‌کنیم <math>T(n)</math> معرف تعداد مقسوم علیه‌های عدد <math>n</math> باشد. تجزیۀ <math>n</math> به عوامل اول نشان می‌دهد که هر [[مقسوم علیه|مقسوم‌علیه]] <math>n</math> باید به صورت <math>n=p_1^{\beta_1}.p_2^{\beta_2}...p_r^{\beta_r}</math> باشد که <math>0\le \beta_i \le \alpha_i,\mbox{ } 1\le i \le r</math>
به وضوح برای هر <math>i</math>، مقدار <math>\beta_i</math> را به <math>\alpha_i+1</math> طریق می‌توان انتخاب کرد (با احتساب مقدار صفر) و در هر حالت یک مقسوم‌علیه <math>n</math> حاصل می‌شود. این کار بنا بر اصل شمارش به:
{{وسط‌چین}}
:<math>(\alpha_1+1).(\alpha_2+1).(\alpha_3+1)...(\alpha_r+1)</math>
{{پایان وسط‌چین}}
طریق امکان‌پذیر است. پس <math>T(n)</math> (تعداد مقسوم علیه‌های عدد <math>n</math>) برابر است با:
{{وسط‌چین}}
:<math>T(n)=(\alpha_1+1)\cdot (\alpha_2+1)\cdot (\alpha_3+1)\cdots (\alpha_r+1)</math>
{{پایان وسط‌چین}}
به عنوان مثال <math>T(1200)=(4+1)(1+1)(2+1)=30</math>.

=== یافتن مجموع مقسوم علیه‌های یک عدد ===
تجزیۀ یک عدد به عوامل اول در مطالعۀ توابع حسابی مانند تابع مقسوم علیهی کاربرد فراوان دارد. برای هر عدد طبیعی <math>n</math>، مجموع قوای
<math>\alpha</math>-اُم مقسوم علیه‌های <math>n</math> را با <math>\sigma_{\alpha}(n)</math> نشان می‌دهیم که در آن <math>\alpha</math> [[عدد حقیقی|عددی حقیقی]] یا مختلط است. پس:
{{وسط‌چین}}
:<math>\sigma_{\alpha}(n)=\sum_{d|n}d^{\alpha}</math>
{{پایان وسط‌چین}}
که مجموع فوق روی مقسوم علیه‌های <math>n</math> است. حال اگر <math>\alpha = 0</math>، در این صورت عبارت فوق همان تعداد مقسوم علیه‌های <math>n</math> است که در قسمت قبل آن را بررسی کردیم. در حالت خاص دیگر اگر <math>\alpha = 1</math>، در این صورت:
{{وسط‌چین}}
:<math>\sigma_1 (n)=\sigma (n)=\sum_{d|n}d</math>
{{پایان وسط‌چین}}
که همان مجموع مقسوم علیه‌های عدد <math>n</math> است که اکنون می‌خواهیم آن را بررسی کنیم. ابتدا فرض می‌کنیم <math>n</math> توانی از عدد اول <math>p</math> چون <math>n = p^a</math> باشد. در این صورت مقسوم علیه‌های <math>n</math> عبارت‌اند از:
{{وسط‌چین}}
:<math>1,p,p^2,...,p^{a-1},p^a</math>
{{پایان وسط‌چین}}
پس:
{{وسط‌چین}}
:<math>\sigma (n)=\sigma (p^a)=1+p+p^2+...+p^a=\frac{p^{a+1}-1}{p-1}</math>
{{پایان وسط‌چین}}
حال در حالتی کلی‌تر فرض می‌کنیم <math>n=p_1^{\alpha_1}.p_2^{\alpha_2}...p_r^{\alpha_r}</math> تجزیه استاندارد <math>n</math> به عوامل اول باشد. در این صورت هر مقسوم‌علیه <math>n</math> به‌صورت <math>n=p_1^{\beta_1}.p_2^{\beta_2}...p_r^{\beta_r}</math> خواهد بود که <math>0\le \beta_i \le \alpha_i,\mbox{ } 1\le i \le r</math>. پس:
{{وسط‌چین}}
:<math>\sigma(n)=\sum_{\beta_1=0}^{\alpha_1}\sum_{\beta_2=0}^{\alpha_2}...\sum_{\beta_r=0}^{\alpha_r}(p_1^{\beta_1}p_2^{\beta_2}...p_r^{\beta_r})</math>
{{پایان وسط‌چین}}
پس:
{{وسط‌چین}}
:<math>\sigma(n)=\sum_{\beta_1=0}^{\alpha_1}p_1^{}\times \sum_{\beta_2=0}^{\alpha_2}p_2^{\beta_2}\times ... \times
\sum_{\beta_r=0}^{\alpha_r}p_r^{\beta_r}</math>
{{پایان وسط‌چین}}
در نتیجه:
{{وسط‌چین}}
:<math>\sigma (n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\times
\frac{p_2^{\alpha_2+1}-1}{p_2-1}\times ... \times \frac{p_r^{\alpha_r+1}-1}{p_r-1}</math>
{{پایان وسط‌چین}}
پس دیدیم که چگونه می‌توان مجموع مقسوم علیه‌های عدد طبیعی <math>n</math> را محاسبه کرد و البته مطلب فوق از [[تابع ضربی|ضربی بودن]] تابع مقسوم علیهی نیز قابل استنتاج است.

=== تعیین حاصل‌ضرب مقسوم علیه‌های یک عدد ===
فرض کنید <math>n</math> عددی طبیعی بزرگ‌تر از یک باشد و
{{وسط‌چین}}
:<math>D=\{d_1,d_2,...,d_{T(n)}\}</math>
{{پایان وسط‌چین}}
مجموعۀ همۀ مقسوم علیه‌های <math>n</math> باشد. به‌علاوه، حاصل‌ضرب مقسوم علیه‌های <math>n</math> را با <math>P(n)</math> نشان می‌دهیم. در این صورت برای هر <math>d_i</math> چون <math>d_i \mid n</math>، پس عددی چون <math>q_i</math> وجود دارد که <math>n=d_i\cdot q_i</math>. اما چون <math>q_i \mid n</math> پس <math>q_i</math>-ها نیز یک مقسوم علیه‌های <math>n</math> و لذا اعضای <math>D</math> می‌باشند. پس:
{{وسط‌چین}}
:<math>P(n)=d_1.d_2...d_{T(n)}=\sqrt{d_1q_1.d_2q_2...d_{T(n)}q_{T(n)}}</math>
{{پایان وسط‌چین}}
بنابراین:
{{وسط‌چین}}
:<math>P(n)=\sqrt{n^{T(n)}}</math>
{{پایان وسط‌چین}}
به این ترتیب حاصل‌ضرب مقسوم‌علیه‌های <math>n</math> را نیز محاسبه کردیم. به عنوان مثال: <math>P(1200)=\sqrt{1200^{T(1200)}}=\sqrt{1200^30}=1200^{15}</math>.

=== محاسبۀ ب. م. م. و ک. م. م. از راه تجزیه به عوامل اول ===
روش دیگری به‌جز روش [[الگوریتم اقلیدس]] برای تعیین بزرگ‌ترین مقسوم‌علیه مشترک (ب. م. م.) و کوچک‌ترین مضرب مشترک (ک. م. م.) دو عدد از راه تجزیۀ آن‌ها به عوامل اول وجود دارد که البته از آنجایی که تجزیۀ اعداد بزرگ پیچیده خواهد بود، چندان روشی کارساز نخواهد بود.

فرض کنید <math>a,b</math> دو عدد طبیعی بزرگ‌تر از یک باشند و
<math>a=p_1^{\alpha_1}.p_2^{\alpha_2}...p_r^{\alpha_r}</math> و <math>b=p_1^{\beta_1}.p_2^{\beta_2}...p_r^{\beta_r}</math> تجزیۀ استاندارد <math>a,b</math> به عوامل اول باشد. در این صورت اگر ب. م. م. <math>a,b</math> را با <math>(a,b)</math> نشان دهیم، داریم:
{{وسط‌چین}}
:<math>(a,b)=p_1^{\theta_1}.p_2^{\theta_2}...p_r^{\theta_r}</math>
{{پایان وسط‌چین}}
که در آن برای هر <math>i</math> داریم <math>\theta_i=\mbox{min} \{\alpha_i,\beta_i\}</math>.

به عبارت دیگر، ب. م. م. دو عدد <math>a,b</math> عبارت است از حاصل‌ضرب عوامل اول مشترک آن‌ها با کمترین توان.

همچنین اگر ک. م. م. <math>a,b</math> را با <math>[a,b]</math> نشان دهیم، داریم:
{{وسط‌چین}}
:<math>[a,b]=p_1^{\theta_1}.p_2^{\theta_2}...p_r^{\theta_r}</math>
{{پایان وسط‌چین}}
که در آن برای هر <math>i</math>، داریم <math>\theta_i=\mbox{max} \{\alpha_i,\beta_i\}</math>.

به عبارت دیگر، ک. م. م. دو عدد <math>a,b</math> عبارت است از حاصل‌ضرب عوامل اول مشترک یا غیر مشترک آن‌ها با بزرگ‌ترین توان. برای اثبات قضایای فوق می‌توانید به مقالات [[بزرگ‌ترین مقسوم علیه مشترک|بزرگ‌ترین مقسوم‌علیه مشترک]] و [[کوچک‌ترین مضرب مشترک]] مراجعه کنید.

== جستارهای وابسته ==
* [[نظریه اعداد]]
* [[عدد اول]]
* [[بزرگترین مقسوم علیه مشترک|بزرگترین مقسوم‌علیه مشترک]]
* [[کوچک‌ترین مضرب مشترک]]
* [[اصل استقرای ریاضی]]

== منابع ==
{{پانویس}}{{کلاس‌های مقسوم‌علیه}}
{{قضیه‌های اساسی}}
[[رده:قضیه‌ها درباره اعداد اول]]
[[رده:قضیه‌های ریاضی]]
[[رده:نظریه اعداد]]