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

با قضیهٔ اساسی حسابان اشتباه نشود.

قضیهٔ اساسی حساب (به انگلیسی: Fundamental theorem of arithmetic) از قضایای مهم در نظریۀ اعداد است که نشان می‌دهد اعداد اول چگونه همانند بلوک‌های ساختمانی در ساختن سایر اعداد نقش دارند.

این قضیه به‌طور ساده بیان می‌کند که هر عدد صحیح به‌جز $1$ و $-1$، به‌صورت حاصل‌ضربی از عوامل اول قابل نمایش است. همچنین این نمایش اعداد به‌صورت حاصل‌ضرب عوامل اول، صرف نظر از ترتیب عوامل یکتا است. به عنوان مثال، عدد ۶۰ را می‌توان به‌صورت $2\cdot 2\cdot 3\cdot 5=60$ به حاصل‌ضرب عوامل اول نوشت.

اگر عدد $n$ را به‌صورت $n=p_{1}p_{2}p_{3}\cdots p_{r}$ به حاصل ضرب عوامل اول بنویسم، این کار را اصطلاحاً تجزیه عدد $n$ به عوامل اول می‌گوئیم. پس قضیهٔ اساسی حساب بیان می‌کند که هر عدد صحیح به‌جز $1$ و $-1$، قابل تجزیه به عوامل اول است و این تجزیه صرف نظر از ترتیب عوامل یکتا است.

قضیۀ اساسی حساب و برهان آن

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

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

قضیۀ اساسی حساب

هر عدد صحیح $n$ که $n\not =\pm 1$ است را می‌توان به‌صورت حاصل‌ضرب عوامل اول نوشت. به‌علاوه، این نمایش به عوامل اول صرف نظر از ترتیب عوامل یکتا است.

اثبات

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

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

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

اگر $k$ اول باشد در این صورت چیزی برای اثبات نمی‌ماند و حکم برقرار است. اگر $k$ اول نباشد در این صورت اعداد صحیح $a,b$ وجود دارند که $k=ab$ و $1<a\leq b<k$. چون $a,b<k$، پس بنابر فرض استقراء $a$ و $b$ به حاصل‌ضرب عوامل اول تجزیه می‌شوند. پس $a=p_{1}p_{2}p_{3}\cdots p_{r}$ و $b=q_{1}q_{2}q_{3}\cdots q_{s}$ که در آن $p_{i}$ و $q_{j}$-ها اعداد اول و نه لزوماً متمایز هستند؛ بنابراین $k=ab=p_{1}p_{2}\cdots p_{r}q_{1}q_{2}\cdots q_{s}$ و لذا $k$ نیز به حاصل‌ضرب عوامل اول تجزیه می‌شود.

حال نشان می‌دهیم این تجزیه صرف نظر از ترتیب عوامل یکتا است. برای اثبات این مطلب فرض می‌کنیم $n$ عددی طبیعی بزرگ‌تر از یک، دلخواه و از این پس ثابت باشد و $n=p_{1}p_{2}p_{3}\cdots p_{r}$ و $n=q_{1}q_{2}q_{3}\cdots q_{s}$ دو تجزیۀ $n$ به عوامل اول باشند. نشان می‌دهیم $r=s$ و احیاناً با تجدید اندیس‌گذاری داریم $p_{1}=q_{1},p_{2}=q_{2},...,p_{r}=q_{s}$.

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

چون $p_{r}\mid n$ و $n=q_{1}q_{2}q_{3}\cdots q_{s}$، پس $p_{r}$ حداقل یکی از $q_{i}$-ها را عاد می‌کند. بی‌آنکه به کلیت مطلب خللی وارد شود، می‌توان فرض کرد $p_{r}\mid q_{s}$ (چرا که می‌توان اندیس‌گذاری را تجدید کرد و به‌صورت دلخواه نوشت)، اما چون $q_{s}$ اول است و $p_{r}>1$ (بنابر اول بودن)، پس لزوماً باید داشته باشیم $p_{r}=q_{s}$. پس:

$p_{1}p_{2}p_{3}\cdots p_{r-1}=q_{1}q_{2}q_{3}\cdots q_{s-1}$

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

$p_{1}=q_{1},p_{2}=q_{2},\cdots ,p_{r-1}=q_{s-1}$

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

$p_{1}=q_{1},p_{2}=q_{2},\cdots ,p_{r-1}=q_{s-1},p_{r}=q_{s}$

تجزیه استاندارد

در ابتدا مفهوم تجزیه به عوامل اول را توضیح دادیم و دیدم که بنابر قضیۀ اساسی حساب، هر عدد صحیح به‌جز یک و منفی یک، به حاصل‌ضرب اعداد اول قابل تجزیه است، اما این عوامل اول ممکن است متمایز نباشند. اگر عدد صحیح $n$ را به‌صورت $n=p_{1}^{\alpha _{1}}.p_{2}^{\alpha _{2}}\cdots p_{r}^{\alpha _{r}}$ بنویسم که در آن $p_{i}$-ها اعداد اول متمایز هستند، این تجزیه به عوامل اول را تجزیه استاندارد یا کانونیک $n$ به عوامل اول می‌گوئیم. به عنوان مثال: $1200=2^{4}\cdot 3\cdot 5^{2}$.

کاربرد

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

یافتن تعداد مقسوم علیه‌های یک عدد

فرض کنید $n$ عددی طبیعی و بزرگ‌تر از یک باشد و $n=p_{1}^{\alpha _{1}}.p_{2}^{\alpha _{2}}...p_{r}^{\alpha _{r}}$ تجزیه استاندارد $n$ به عوامل اول باشد. همچنین فرض می‌کنیم $T(n)$ معرف تعداد مقسوم علیه‌های عدد $n$ باشد. تجزیۀ $n$ به عوامل اول نشان می‌دهد که هر مقسوم‌علیه $n$ باید به صورت $n=p_{1}^{\beta _{1}}.p_{2}^{\beta _{2}}...p_{r}^{\beta _{r}}$ باشد که $0\leq \beta _{i}\leq \alpha _{i},{\mbox{ }}1\leq i\leq r$ به وضوح برای هر $i$، مقدار $\beta _{i}$ را به $\alpha _{i}+1$ طریق می‌توان انتخاب کرد (با احتساب مقدار صفر) و در هر حالت یک مقسوم‌علیه $n$ حاصل می‌شود. این کار بنا بر اصل شمارش به:

$(\alpha _{1}+1).(\alpha _{2}+1).(\alpha _{3}+1)...(\alpha _{r}+1)$

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

$T(n)=(\alpha _{1}+1)\cdot (\alpha _{2}+1)\cdot (\alpha _{3}+1)\cdots (\alpha _{r}+1)$

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

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

تجزیۀ یک عدد به عوامل اول در مطالعۀ توابع حسابی مانند تابع مقسوم علیهی کاربرد فراوان دارد. برای هر عدد طبیعی $n$، مجموع قوای $\alpha$-اُم مقسوم علیه‌های $n$ را با $\sigma _{\alpha }(n)$ نشان می‌دهیم که در آن $\alpha$ عددی حقیقی یا مختلط است. پس:

$\sigma _{\alpha }(n)=\sum _{d|n}d^{\alpha }$

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

$\sigma _{1}(n)=\sigma (n)=\sum _{d|n}d$

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

$1,p,p^{2},...,p^{a-1},p^{a}$

پس:

$\sigma (n)=\sigma (p^{a})=1+p+p^{2}+...+p^{a}={\frac {p^{a+1}-1}{p-1}}$

حال در حالتی کلی‌تر فرض می‌کنیم $n=p_{1}^{\alpha _{1}}.p_{2}^{\alpha _{2}}...p_{r}^{\alpha _{r}}$ تجزیه استاندارد $n$ به عوامل اول باشد. در این صورت هر مقسوم‌علیه $n$ به‌صورت $n=p_{1}^{\beta _{1}}.p_{2}^{\beta _{2}}...p_{r}^{\beta _{r}}$ خواهد بود که $0\leq \beta _{i}\leq \alpha _{i},{\mbox{ }}1\leq i\leq r$. پس:

$\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}})$

پس:

$\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}}$

در نتیجه:

$\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}}$

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

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

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

$D=\{d_{1},d_{2},...,d_{T(n)}\}$

مجموعۀ همۀ مقسوم علیه‌های $n$ باشد. به‌علاوه، حاصل‌ضرب مقسوم علیه‌های $n$ را با $P(n)$ نشان می‌دهیم. در این صورت برای هر $d_{i}$ چون $d_{i}\mid n$، پس عددی چون $q_{i}$ وجود دارد که $n=d_{i}\cdot q_{i}$. اما چون $q_{i}\mid n$ پس $q_{i}$-ها نیز یک مقسوم علیه‌های $n$ و لذا اعضای $D$ می‌باشند. پس:

$P(n)=d_{1}.d_{2}...d_{T(n)}={\sqrt {d_{1}q_{1}.d_{2}q_{2}...d_{T(n)}q_{T(n)}}}$

بنابراین:

$P(n)={\sqrt {n^{T(n)}}}$

به این ترتیب حاصل‌ضرب مقسوم‌علیه‌های $n$ را نیز محاسبه کردیم. به عنوان مثال: $P(1200)={\sqrt {1200^{T(1200)}}}={\sqrt {1200^{3}0}}=1200^{15}$.

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

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

فرض کنید $a,b$ دو عدد طبیعی بزرگ‌تر از یک باشند و $a=p_{1}^{\alpha _{1}}.p_{2}^{\alpha _{2}}...p_{r}^{\alpha _{r}}$ و $b=p_{1}^{\beta _{1}}.p_{2}^{\beta _{2}}...p_{r}^{\beta _{r}}$ تجزیۀ استاندارد $a,b$ به عوامل اول باشد. در این صورت اگر ب. م. م. $a,b$ را با $(a,b)$ نشان دهیم، داریم:

$(a,b)=p_{1}^{\theta _{1}}.p_{2}^{\theta _{2}}...p_{r}^{\theta _{r}}$

که در آن برای هر $i$ داریم $\theta _{i}={\mbox{min}}\{\alpha _{i},\beta _{i}\}$.

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

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

$[a,b]=p_{1}^{\theta _{1}}.p_{2}^{\theta _{2}}...p_{r}^{\theta _{r}}$

که در آن برای هر $i$، داریم $\theta _{i}={\mbox{max}}\{\alpha _{i},\beta _{i}\}$.

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

جستارهای وابسته

• نظریه اعداد
• عدد اول
• بزرگترین مقسوم‌علیه مشترک
• کوچک‌ترین مضرب مشترک
• اصل استقرای ریاضی