قضیه اصلی حساب — به زبان ساده

۹۳۰ بازدید
آخرین به‌روزرسانی: ۱۳ خرداد ۱۴۰۲
زمان مطالعه: ۷ دقیقه
قضیه اصلی حساب — به زبان ساده

یکی از قضیه‌های مهم و اساسی در نظریه اعداد، قضیه اصلی حساب (Fundamental Theorem of Arithmetic) است که گاهی به آن «قضیه تجزیه یکتا» (Unique Factorization Theorem) یا «قضیه تجزیه به عوامل اول یکتا»  (Unique-Prime-Factorization Theorem) نیز می‌گویند. از کاربردهای آن می‌توان به تجزیه اعداد مرکب و پیدا کردن اعداد اول و همچنین محاسبه بزرگترین مقسوم علیه مشترک (ب-م-م) و کوچکترین مضرب مشترک (ک-م-م) اشاره کرد.

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

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

قضیه اساسی حساب، راه را برای تعیین «اعداد مرکب» (Composite Number) و «عدد اول» (Prime Number) باز کرده است. طبق این قضیه، هر عدد صحیح (مخالف ۱) یا یک عدد اول است یا یک عدد مرکب که می‌تواند به شکل منحصر به فردی توسط ضرب اعداد اول بیان شود.

برای مثال عدد ۱۲۰۰ را می‌توان به صورت عامل‌ها یا اعداد اول ۲ و ۳ و ۵ به شکل زیر نوشت:

$$\large 1200 = 2^4 \times  3^1 \times 5^2 = 2 \times 2 \times 2 \times 2 \times 3 \times 5 \times 5 $$

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

برای مثال مشخص است که ۱۲۰۰ را می‌توان فقط براساس عوامل اول ۲ و ۳ و ۵ و توان‌های مختلف آن‌ها نوشت. هر چند ممکن است ترتیب ضرب‌ها متفاوت باشد ولی عوامل و توان‌های آن‌ها همیشه یکسان هستند.

$$\large 1200 = 2^4 \times  3^1 \times 5^2 = 3^1 \times 2^4 \times  5^2=   5^2 \times 3^1 \times 2^4$$

نکته: عوامل یا فاکتورها، در قضیه اصلی حساب باید اعداد اول باشند، در غیر اینصورت دیگر عامل‌ها منحصر به فرد نخواهند بود. برای مثال عدد ۱۲ را می‌توانستیم به صورت‌های مختلفی از عوامل تجزیه کنیم که لزوما اول هم نباشند.

$$\large 24 = 12 \times 2 = 6 \times 4 = 3 \times 8 = 2^3 \times 3$$

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

$$\large 2 = 2 \times 1 = 2 \times 1 \times 1 = 2 \times 1 \times 1 \times ...$$

قبل از هر چیز اصطلاحی را معرفی می‌کنیم که بسیار مرتبط به اعداد صحیح و مبحث تقسیم و تجزیه به عوامل اول است.

بخش‌پذیری یا عاد کردن

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

  • $$a$$، عدد $$b$$ را عاد می‌کند.
  • $$b$$، بر $$a$$ بخش‌پذیر است.
  • $$b$$، مضربی از $$a$$ است.
  • $$a$$، مقسوم علیه $$b$$‌ است.
  • $$a$$، عدد $$b$$‌ را می‌شمارد.

این عبارت‌ها را به بیان و نماد ریاضی به صورت زیر نشان می‌دهیم:

$$\large a|b$$

و می‌خوانیم $$a$$ عدد $$b$$ را عاد می‌کند. قوانین و قضیه‌های مربوط به بخش‌پذیری و عاد کردن را در قواعد بخش پذیری یا عاد کردن --- به زبان ساده مطالعه کنید.

اقلیدس - euclid
اقلیدس؛ پدر هندسه

تاریخچه قضیه اصلی حساب

اولین بار این قضیه (حداقل به عنوان یک قضیه) توسط اقلیدس در کتاب اصول هندسه، جلد هفتم گزاره ۳۰ تا ۳۲ و همچنین جلد نهم در گزاره ۱۴، حدود ۳۰۰ سال قبل از میلاد معرفی شد. او در گزاره ۳۰ چنین گفته است:

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

این موضوع را به زبان امروزی می‌توان به این صورت بیان کرد که اگر عدد اول $$p$$ حاصل‌ضرب $$ab$$ را بشمارد، آنگاه $$p$$ حتما یکی از اعداد $$a$$ یا $$b$$ را عاد خواهد کرد. البته مشخص است که این گزاره فقط در صورتی صحیح است که عددی که تقسیم بر آن صورت می‌گیرد، یک عدد اول باشد، در غیر این صورت، گزاره اشتباه خواهد بود.

این قضیه که کلید اصلی برای اثبات قضیه اصلی حساب است، گاهی «لم اقلیدس» (Euclid's Lemma) نیز نامیده می‌شود.

همچنین گزاره ۳۱ که توسط اقلیدس در اصول هندسه، بیان شده به شکل زیر است: «هر عدد مرکب توسط یک یا چند عدد اول، شمارش (عاد) می‌شود.»

این گزاره را می‌توان به این شکل بیان کرد که هر عدد صحیح بزرگتر از ۱، حتما یک مقسوم علیه اول دارد.

ا زطرفی، گزاره شماره ۳۲ نیز در مورد طبقه‌بندی اعداد صحیح نوشته شده است: «هر عدد، یا اول است یا توسط یک عدد اول شمرده می‌شود.»

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

در انتها نیز گزاره ۱۴ از جلد نهم را می‌آوریم: «اگر یک عدد،‌ کوچکترین عددی باشد که توسط حاصل‌ضرب اعداد اول ساخته شده، آنگاه توسط هیچ عدد اول دیگری شمرده نخواهد شد.»

به بیان ریاضیات مدرن می‌توان این گزاره به این صورت در نظر گرفت که کوچکترین مضرب مشترک چندین عدد اول، مضربی از اعداد اول دیگر نیست. این موضوع ابتدای راه اثبات یکتا بودن تجزیه اعداد مرکب به عوامل اول است.

بعدها، «کارل گاوس» (Johann Carl Friedrich Gauss) در کتاب «پرسش‌های ریاضی» (Disquisitiones Arithmetica) اثبات قضیه اصلی حساب را ارائه کرد و «حساب پیمانه‌ای» (Modular Arithmetic) که پایه محاسبات رایانه‌های امروزی است را بنا نهاد.

کارل گاوس - Carl-friedrich-Gauss
کارل گاوس (Carl-Gauss)، دانشمند و ریاضی‌دان آلمانی

قضیه اصلی حساب و اثبات آن

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

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

نکته: منظور از منحصر به فرد ترتیب ضرب نیست بلکه اعداد اول و توان‌های آن‌ها است.

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

اثبات:

  • فرض کنید $$n=2$$، از آنجایی که ۲ عدد اول است، پس حکم برقرار است.
  • فرض کنید که قضیه برای هر عدد طبیعی $$n$$ برقرار باشد.
  • برای عدد طبیعی $$n+1$$، دو وضعیت در نظر می‌گیریم، اگر اول باشد که خودش برحسب عامل بوده و احتیاج به تجزیه ندارد. ولی اگر $$n+1$$‌ مرکب باشد، اعداد طبیعی دیگری مانند $$a$$ و $$b$$ وجود دارند که:

$$\large n+1=ab,\;\; 1 < a \leq b <n+1$$

پس هم $$a$$ و هم $$b$$ طبق فرض استقرا، قابل تجزیه به عوامل اول هستند، زیرا از $$n+1$$ کوچکتر بوده و حکم استقرا برایشان صادق است. پس می‌توان نوشت:

$$\large a = p_1\,p_2\,p_3\,\ldots p_s, \;\;b = q_1\,q_2\,q_3\,\ldots\,q_r$$

که در آن‌ها $$q_i$$ و $$p_j$$ اعداد اول بوده و لزوما متفاوت نیز نیستند. پس داریم:

$$\large n+1= p_1\,p_2\,p_3\,\ldots\, p_s\,q_1\,q_2\,q_3\,\ldots\,q_r$$

در نتیجه عدد $$n+1$$ نیز به صورت حاصل‌ضرب اعداد اول نوشته شد.

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

$$\large n = p_1\;p_2\;p_3\;\ldots\;p_k\\ \large n = q_1\;q_2\;q_3\;\ldots\;q_l$$

نشان می‌‌دهیم که $$l=k$$ و عوامل $$,p_1\,p_2\,p_3\,\ldots\,p_k$$ و $$\,q_1\,q_2\,\ldots\,q_l$$ بطور متناظر، یکی هستند. استقرا را روی $$k$$ انجام می‌دهیم.

  • فرض کنید $$k=1$$ در نتیجه حکم برقرار است. زیرا $$n$$ عدد اول است.
  • فرض کنید قضیه برای $$k-1$$ برقرار بوده، باید نشان دهیم که برای $$k$$ نیز برقرار است.
  • از آنجایی که $$n =\,p_1\,p_2\,p_3\,\ldots\,p_k$$، پس $$p_k$$، عدد $$n$$ را می‌شمارد و داریم $$p_k|n$$ پس $$p_k\,|\,q_1\,q_2\,\ldots\,q_l$$ در نتیجه حداقل یکی از $$q_j$$ها توسط $$p_k$$ شمرده می‌شوند که خلاف اول بودن آن‌ها است مگر آنکه با هم برابر باشند. در نتیجه $$q_i=p_k$$ هستند.
  • بر این اساس، با تغییر اندیس و استفاده از فرض استقرا، نتیجه می‌گیریم که تجزیه به عوامل اول یکتا است.

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

factorization Theorem

فرم استاندارد یا تجزیه کانونی اعداد مرکب

هر عدد صحیح بزرگتر از ۱ (اعداد طبیعی) را می‌توان به صورت حاصل‌ضرب اعداد اول و توان‌های صحیح نوشت. بنابراین اگر $$n$$ را یک عدد طبیعی یا مرکب با شرایط گفته شده در نظر بگیریم و $$p_1$$ تا $$p_k$$ نیز، $$k$$ عدد اول باشند که $$p_1<p_2<\ldots,p_k$$، آنگاه طبق قضیه اصلی حساب، تجزیه کانونی (Canonical Representation) یا فرم استاندارد (Standard Form) یک عدد مرکب (یا حتی اول) را می‌توان به صورت زیر نمایش داد.

$$\large {\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}}$$

به عنوان مثال

$$\large 999 = 3^3 \times 27, \;\;\; 1000 = 2^3 \times 5^3,\;\;\; 1001 = 7 \times 11 \times 13$$

نکته: اگر $$p^0=1$$‌ در نظر گرفته شود، آنگاه می‌توان هر عدد طبیعی را به صورت حاصل‌ضرب همه اعداد اول (حاصل‌ضرب نامتناهی) نوشت:

$$\large {\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}}}$$

عملگرهای ریاضی

به کمک نمایش کانونی یا فرم استاندارد اعداد طبیعی (صحیح) می‌توان بزرگترین مقسوم علیه مشترک (ب-م-م) که آن را با $$\operatorname{gdc}$$ نشان داده یا کوچکترین مضرب مشترک (ک-م-م) یا $$\operatorname{lcm}$$ دو عدد را به راحتی پیدا کرد.

دو عدد $$a$$ و $$b$$ را در نظر بگیرید. بطوری که

$$\large a=2^{a_1}\times 3^{a_2}\times \ldots,\\ \large b=2^{b_1}\times 3^{b_2}\times \ldots$$

آنگاه

$$\large {\displaystyle {\begin{alignedat}{2}a\cdot b&{}={}2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&{}={}\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b)&{}={}2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{3})}7^{\min(a_{4},b_{4})}\cdots &&{}={}\prod p_{i}^{\min(a_{i},b_{i})},\\\operatorname {lcm} (a,b)&{}={}2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&{}={}\prod p_{i}^{\max(a_{i},b_{i})}.\end{alignedat}}}$$

به این ترتیب، برای مثال بزرگترین مقسوم علیه مشترک بین ۱۲ و ۱۵، برابر با ۳ است، زیرا:

$$\large 15 = 2^0 \times 3^1 \times 5^1$$

$$\large 12 = 2^2 \times 3^1 \times 5^0$$

و

$$\large {\displaystyle 15 \times 12 = 2^{0+2} \times 3^{1+1} \times 5^{1+0} = 4 \times 9 \times 5 = 180}$$

پس

$$\large {\displaystyle \gcd(15,12) =2^{\min(0,2)} \times 3^{\min(1,1)} \times 5^{\min(1,0)}= 2^0\times 3^1 \times 5^0=3}$$

همچنین کوچکترین مضرب مشترک دو عدد ۱۲ و ۱۵ نیز برابر با خواهد بود.

$$\large {\displaystyle \operatorname{lcm}(15,12) =2^{\max(0,2)} \times 3^{\max(1,1)} \times 5^{\max(1,0)}= 2^2\times 3^1 \times 5^1=60}$$

prime numbers

خلاصه و جمع‌بندی

در این نوشتار با قضیه اصلی حساب (Fundamental Theorem of Arithmetic) و تجزیه اعداد به عوامل اول، آشنا شدیم. به این ترتیب توانستیم اعداد مرکب را به شکلی منحصر به فرد و یکتا به صورت حاصل‌ضرب اعداد اول بنویسیم. روش‌های تشخیص عدد مرکب و عدد اول نیز در این نوشتار مرور و مورد بررسی قرار گرفت.

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

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۵ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Wikipediaمجله فرادرس
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *