ب.م.م

قضیه اساسی حساب، از قضایای مهم در نظریه اعداد است که نشان می‌دهد اعداد اول چگونه همانند بلوک‌های ساختمانی در ساختن سایر اعداد نقش دارند.

این قضیه به طور ساده بیان می‌کند هر عدد صحیح بجز یک و منفی یک به صورت حاصل ضربی از عوامل اول قابل نمایش هستند. همچنین این نمایش اعداد به صورت حاصل ضرب عوامل اول، صرف نظر از ترتیب عوامل یکتا است. به عنوان مثال عدد ۶۰ را می‌توان به صورت ۶۰ =۲ × ۲× ۳ × ۵ به حاصل ضرب عوامل اول نوشت.

اگر عدد n را به صورت n = p۱p۲p۳...pr به حاصل ضرب عوامل اول بنویسم این کار را اصطلاحاً تجزیه عدد n به عوامل اول می‌گوییم. پس قضیه اساسی حساب بیان می‌کند هر عدد صحیح بجز یک و منفی یک، قابل تجزیه به عوامل اولند و این تجزیه صرف تظر از ترتیب عوامل یکتا است.

فهرست مندرجات [نمایش]

[ویرایش]قضیه اساسی حساب و برهان آن

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

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

قضیه اساسی حساب

هر عدد صحیح n که 1± ≠ n، را می‌توان به صورت حاصل ضرب عوامل اول نوشت. بعلاوه، این نمایش به عوامل اول صرف نظر از ترتیب عوامل یکتا است.

برهان

برای اثبات کافی است قضیه را فقط برای اعداد طبیعی ثابت کنیم.

برهان قضیه شامل دو قسمت وجود و یکتایی است. ابتدا نشان می‌دهیم هر عدد را می‌توان به صورت حاصل ضربی از عوامل اول نوشت. این کار را مبتنی بر اصل استقراء روی  انجام می‌دهیم.

اگر n = 2 چون 2 خود عددی اول است پس حکم برقرار است. فرض می‌کنیم حکم برای هر عدد طبیعی کوچک‌تر از n برقرار باشد. نشان می‌دهیم حکم برای n نیز درست است و بنابر اصل استقراء ریاضی نتیجه می گیریم حکم برای هر عدد طبیعی درست است.

اگر n اول باشد در این صورت چیزی برای اثبات نمی‌ماند و حکم برقرار است. اگر n اول نباشد در این صورت اعداد صحیح a, b وجود دارند که n = ab و . چون a, b < n بنابر فرض استقراء a,b به حاصل ضرب عوامل اول تجزیه می‌شوند. پس a=p1p2p3...pr و b=q1q2q3...qs که در آن pi و qj ها اعداد اول و نه لزوماً متمایز هستند. بنابراین n = ab = p1p2...prq1q2...qs و لذا n نیز به حاصل ضرب عوامل اول تجزیه می‌شود.

حال نشان می‌دهیم این تجریه صرف نظر از ترتیب عوامل یکتا است. برای اثبات این مطلب فرض می‌کنیم n عددی طبیعی بزرگ‌تر از یک، دلخواه و از این پس ثابت باشد و n = p1p2p3...pr و n = q1q2q3...qs دو تجزیه n به عوامل اول باشند. نشان می‌دهیم r = s و احیاناً با تجدید اندیس گذاری داریم p1=q1,p2=q2,...,pr=qs.

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

چون pr | n و n=q1q2q3...qs پس pr حداقل یکی از qiها را عاد می کند، بی‌آنکه به کلیت مطلب خللی وارد شود می‌توان فرض کرد pr|qs(چرا که می‌توان اندیس گذاری را تجدید کرد و به صورت دلخواه نوشت) اما چون qs اول است و 1<pr(بنابر اول بودن) پس لزوماً باید داشته باشیم pr=qs. پس

p1p2p3...pr − 1 = q1q2q3...qs − 1

و بنابر فرض استقراء، r-1=s-1 و احیاناً با تجدید اندیس گذاری:

p1 = q1,p2 = q2,...,pr − 1 = qs − 1

پس r=s و احیاناً با تجدید اندیس گذاری:

p1 = q1,p2 = q2,...,pr − 1 = qs − 1,pr = qs

[ویرایش]تجزیه استاندارد

در ابتدا مفهوم تجزیه به عوال اول را توضیح دادیم و دیدم که بنابر قضیه اساسی حساب هر عدد صحیح بجز یک و منفی یک به حاصل ضرب اعداد اول قابل تجزیه است اما این عوامل اول ممکن است متمایز نباشند. اگر عدد صحیح n را به صورت  بنویسم که در آن piها اعداد اول متمایز هستند، این تجزیه به عوامل اول را تجزیه استاندارد یا کانونیک n به عوامل اول می‌گوییم. به عنوان مثال .

[ویرایش]کاربرد

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

[ویرایش]یافتن تعداد مقسوم علیه‌های یک عدد

فرض کنید n عددی طبیعی و بزرگ‌تر از یک باشد و  تجزیه استاندارد n به عوامل اول باشد. همچنین فرض می‌کنیم (T(n معرف تعداد مقسوم علیه‌های عدد n باشد. تجزیه n به عوامل اول نشان می‌دهد که هر مقسوم علیه n باید به صورت  باشد که  وضوحاً برای هر i، مقدار βi را به αi + 1 طریق می‌توان انتخاب کرد(با احتساب مقدار صفر) و در هر حالت یک مقسوم علیه n حاصل می‌شود. این کار بنا بر اصل شمارش به:

(α1 + 1).(α2 + 1).(α3 + 1)...(αr + 1)

طریق امکان پذیر است. پس (T(n تعداد مقسوم علیه‌های عدد n برابر است با:

T(n) = (α1 + 1).(α2 + 1).(α3 + 1)...(αr + 1)

به عنوان مثال T(1200) = (4 + 1)(1 + 1)(2 + 1) = 30.

[ویرایش]یافتن مجموع مقسوم علیه‌های یک عدد

تجزیه یک عدد به عوامل اول در مطالعه توابع حسابی مانند تابع مقسوم علیهی کاربرد فراوان دارد. برای هر عدد طبیعی n، مجموع قوای αام مقسوم علیه‌های n را با σα(n) نشان می‌دهیم که در آن α عددی حقیقی یا مختلط است. پس:

σα(n) = ∑ dα

d | n

که مجموع فوق روی مقسوم علیه‌های n است. حال اگر 0=α در این صورت عبارت فوق همان تعداد مقسوم علیه‌های n است که در قسمت قبل آن را بررسی کردیم. در حالت خاص دیگر اگر 1=α در این صورت:

σ1(n) = σ(n) = ∑ d

d | n

که همان مجموع مقسوم علیه‌های عدد n است که اکنون می‌خواهیم آن را بررسی کنیم. ابتدا فرض می‌کنیم n توانی از عدد اول p چون n=pa باشد. در این صورت مقسوم علیه‌های n عبارت‌اند از:

1,p,p2,...,pa − 1,pa

پس:

حال در حالتی کلی‌تر فرض می‌کنیم  تجزیه استاندارد n به عوال اول باشد. در این صورت هر مقسوم علیه n به صورت  خواهد بود که  پس:

پس:

در نتیجه:

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

[ویرایش]تعیین حاصل ضرب مقسوم علیه‌های یک عدد

فرض کنید n عددی طبیعی بزرگ‌تر از یک باشد و

D = {d1,d2,...,dT(n)}

مجموعه همه مقسوم علیه‌های n باشد. بعلاوه حاصل ضرب مقسوم علیه‌های n را با (P(n نشان می‌دهیم. در این صورت برای هر di چون di|n پس عددی چون qi وجود دارد که n=diqi. اما چون qi|n پس qiها نیز یک مقسوم علیه‌های n و لذا اعضای D می‌باشند، پس:

پس

به این ترتیب حاصل ضرب مقسوم علیه‌های n را نیز محاسبه کردیم. به عنوان مثال 

[ویرایش]محاسبه ب.م.م و ک.م.م از راه تجزیه به عوامل اول

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

فرض کنید a,b دو عدد طبیعی بزرگ‌تر از یک باشند و  و  تجزیه استاندار a,b به عوامل اول باشد. در این صورت اگر ب.م.م a,b را با (a,b) نشان دهیم داریم:

که در آن برای هر i داریم θi = min{αi,βi}.

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

همچنین اگر ک.م.م a,b را با [a,b] نشان دهیم داریم:

که در آن برای هر i، داریم θi = max{αi,βi}.