تاریخچه ی:
قضیه اساسی حساب
تفاوت با نگارش: 1
| + | V{maketoc} |
| + | ^@#16: |
| !قضیه | | !قضیه |
- | هر عدد صحیح n>1 را میتوان (صرفنظر از ترتیب عوامل) فقط به یک طریق بصورت حاصل ضربی از عوامل اول نمایش داد. برای اثبات صحت ادعای فوق از ((استقرای ریاضی|استقرا)) روی n استفاده میکنیم. قضیه برای n=2 درست است. پس فرض کنیم برای هر عدد صحیح بزرگتر از 1 و کوچکتر از n درست باشد. ثابت می کنیم قضیه برای n نیز درست است اگر n اول باشد، چیزی برای اثبات وجود ندارد. پس فرض کنیم n مرکب بوده و n دو تجزیه ، مثلا (*) {TEX()} {n=p_1 p_2... p_5=q_1 q_2...q_t} {TEX} داشته باشد، میخواهیم نشان دهیم S=t و هر p مساوی qای است.
چون {TEX()} {p_1} {TEX} حاصلضرب {TEX()} {q_1 q_2 ...q_t} {TEX} را عاد میکند. باید دست کم یکی از عاملها را عاد کند. {TEX()} {q_1 q_2 ...q_t} {TEX} را طوری اندیسگذاری میکنیم که {TEX()} {p_1|q_1} {TEX}. در اینصورت {TEX()} {p_1=q_1} {TEX} ، زیرا {TEX()} {p_1} {TEX} و {TEX()} {q_1} {TEX} هر دو اولند. در عبارت (*) میتوان با حذف {TEX()} {p_1} {TEX} از طرفین بدست آورد. {TEX()} {\frac{n}{p_1}=p_2... p_5=q_2...q_t} {TEX} هرگاه S>1 یا t>1 ، آنگاه {TEX()} {1< \frac{n}{p_1}((قضیه اساسی حساب)) به پایان میرسد. |
+ | هر عدد صحیح n>1 را میتوان (صرفنظر از ترتیب عوامل) فقط به یک طریق بصورت حاصل ضربی از عوامل اول نمایش داد. برای اثبات صحت ادعای فوق از ((استقرای ریاضی|استقرا)) روی n استفاده میکنیم. قضیه برای n=2 درست است. پس فرض کنیم برای هر عدد صحیح بزرگتر از 1 و کوچکتر از n درست باشد. ثابت می کنیم قضیه برای n نیز درست است اگر n اول باشد، چیزی برای اثبات وجود ندارد. پس فرض کنیم n مرکب بوده و n دو تجزیه ، مثلا (*) {TEX()} {n=p_1 p_2... p_5=q_1 q_2...q_t} {TEX} داشته باشد، میخواهیم نشان دهیم S=t و هر p مساوی qای است.
چون {TEX()} {p_1} {TEX} حاصلضرب {TEX()} {q_1q_2...q_t} {TEX} را عاد میکند. باید دست کم یکی از عاملها را عاد کند. {TEX()} {q_1 q_2...q_t} {TEX} را طوری اندیسگذاری میکنیم که {TEX()} {p_1|q_1} {TEX}. در اینصورت {TEX()} {p_{1}=q_{1}} {TEX} ، زیرا {TEX()} {p_{1},q_{1}} {TEX} هر دو اولند. در عبارت (*) میتوان با حذف {TEX()} {p_{1}} {TEX} از طرفین بدست آورد. {TEX()} {\frac{n}{p_{1}}=p_{2}... p_{5}=q_{2}...q_{t}} {TEX} هرگاه S>1 یا t>1 ، آنگاه {TEX()} {1<\frac{n}{p_{1}}{1}}} {TEX} ، صرفنظر از ترتیب عوامل ، باید یکی باشند. بنابراین ، S=t و تجزیههای (*) نیز صرفنظر از ترتیب ، یکی میباشند و بدین ترتیب اثبات قضیه اساسی حساب به پایان میرسد. |
| !!تذکر | | !!تذکر |
- | در تجزیه عدد صحیح n ، عدد اول خاصی p ممکن است بیش از یک بار بیاید هرگاه عوامل اول متمایز n ، {TEX()} {p_1 ,...,p_r} {TEX} بوده و {TEX()} {p_i} {TEX} به عنوان یک عامل ، {TEX()} {a_i} {TEX} بار بیاید. میتوانی بنویسیم:
{TEX()} {n=p_1 ^a_1 ... p_r ^a_r} {TEX} یا مختصرتر {TEX()} {n=\prod_{i=1}^r p_i ^a_i} {TEX}. این تجزیه n به ((عوامل اول)) مینامند. همچنین ، میتوان 1 را با اختصار هر نمای {TEX()} {a_i} {TEX} مساوی 0 به اینصورت بیان کرد: |
+ | در تجزیه عدد صحیح n ، عدد اول خاصی p ممکن است بیش از یک بار بیاید هرگاه عوامل اول متمایز n ، {TEX()} {p_{1},...,p_{r}} {TEX} بوده و {TEX()} {p_i} {TEX} به عنوان یک عامل ، {TEX()} {a_i} {TEX} بار بیاید. میتوانی بنویسیم:
{TEX()} {n=p_1^a_1 ... p_r^a_r} {TEX} یا مختصرتر {TEX()} {n=\prod_{i=1}^r p_i^a_i} {TEX}. این تجزیه n به ((عوامل اول)) مینامند. همچنین ، میتوان 1 را با اختصار هر نمای {TEX()} {a_i} {TEX} مساوی 0 به اینصورت بیان کرد: |
| !!قضیه | | !!قضیه |
- | هرگاه {TEX()} {n=\prod_{i=1}^r p_i ^a_i} {TEX} ، که در آن به ازای i=1,2,...,r ، {TEX()} {0 \le c_i \le a_i} {TEX}
*هرگاه دو عدد صحیح و مثبت b,a دارای تجزیههای {TEX()} {b=\prod_{i=1}^\infty p_i ^b_i} {TEX} {TEX()} {a=\prod_{i=1}^\infty p_i ^a_i} {TEX} باشند، آنگاه بمعم آنها تجزیه{TEX()} {(a,b)=\prod_{i=1}^\infty p_i ^c_i} {TEX} را دارد که در آن هر {TEX()} {c_i} {TEX} مساوی {TEX()} {min { a_i,b_i }} {TEX} ، یعنی کوچکترین {TEX()} {b_i , a_i} {TEX} است. |
+ | هرگاه {TEX()} {n=\prod_{i=1}^r p_i^a_i} {TEX} ، که در آن به ازای i=1,2,...,r ، {TEX()} {0\le c_i\le a_i} {TEX} *هرگاه دو عدد صحیح و مثبت b,a دارای تجزیههای {TEX()} {b=\prod_{i=1}^\infty p_i^b_i} {TEX} {TEX()} و {a=\prod_{i=1}^\infty p_i^a_i} {TEX} باشند، آنگاه بمعم آنها تجزیه {TEX()} {(a,b)=\prod_{i=1}^\infty p_i^c_i} {TEX} را دارد که در آن هر {TEX()} {c_i} {TEX} مساوی {TEX()} {min {a_i,b_i}} {TEX} ، یعنی کوچکترین {TEX()} {b_i,a_i} {TEX} است. |
| !الگوریتم اقلیدس | | !الگوریتم اقلیدس |
| طبق نکته فوق اگر تجزیه به عوامل اول b,a معلوم باشند. یک روش عملی برای محاسبه {TEX()} {(a,b)} {TEX} بمعم بدست میدهد. اما ممکن است در تجزیه به عوامل اول محاسبات زیادی لازم باشد. فرآیند مفیدی وجود دارد بنام ((الگوریتم اقلیدس)) ، که محتاج به تجزیه b,a نیست. این فرآیند بر تقسیمات متوالی استوار است و در آن از مطلب زیر استفاده میشود: | | طبق نکته فوق اگر تجزیه به عوامل اول b,a معلوم باشند. یک روش عملی برای محاسبه {TEX()} {(a,b)} {TEX} بمعم بدست میدهد. اما ممکن است در تجزیه به عوامل اول محاسبات زیادی لازم باشد. فرآیند مفیدی وجود دارد بنام ((الگوریتم اقلیدس)) ، که محتاج به تجزیه b,a نیست. این فرآیند بر تقسیمات متوالی استوار است و در آن از مطلب زیر استفاده میشود: |
| !!الگوریتم تقسیم | | !!الگوریتم تقسیم |
- | به ازای اعداد صحیح b,a که b>0 جفت منحصر به فردی از اعداد صحیح مانند r,q وجود دارد که بطوری که a=bq+r که در آن {TEX()} {0 \le r \le b} {TEX} بعلاوه r=0 اگر و فقط اگر b|a. |
+ | به ازای اعداد صحیح b,a که b>0 جفت منحصر به فردی از اعداد صحیح مانند r,q وجود دارد که بطوری که a=bq+r که در آن {TEX()} {0\le r\le b} {TEX} بعلاوه r=0 اگر و فقط اگر b|a. |
| !!تذکر | | !!تذکر |
| میگوئیم q خارح قسمت و r باقیمانده در تقسیم a به b میباشند. | | میگوئیم q خارح قسمت و r باقیمانده در تقسیم a به b میباشند. |
| !!الگوریتم اقلیدسی | | !!الگوریتم اقلیدسی |
- | فرض کنیم اعداد صحیح و مثبت b,a داده شده باشند که b عاد نمیکند a را. همچنین {TEX()} {r_1=b} {TEX} {TEX()} {r_0=a} {TEX} ، و الگوریتم تقسیم را متوالیا بکار بریم تا مجموعه باقماندههای {TEX()} {r_2,r_3,...,r_n,r_n+1} {TEX} بدست آید که بترتیب با روابط زیر تعریف میشوند:
|
+ | فرض کنیم اعداد صحیح و مثبت {TEX()} {b,a} {TEX} داده شده باشند که {TEX()} {b} {TEX} عاد نمیکند {TEX()} {a} {TEX} را. همچنین {TEX()} {r_{1}=b} {TEX} {TEX()} {r_{0}=a} {TEX} ، و الگوریتم تقسیم را متوالیا بکار بریم تا مجموعه باقیماندههای {TEX()} {r_2,r_3,...,r_n,r_{n+1}} {TEX} بدست آید که بترتیب با روابط زیر تعریف میشوند: |
- | ::{TEX()} {r_0 = r_1 q_1 + r_2 0:: ::{TEX()} {r_1 = r_2 q_2 + r_3 0:: ::...:: ::...:: ::...:: ::{TEX()} {r_n-2 = r_n-1 q_n-1 + r_n 0:: ::{TEX()} {r_n - 1 = r_n q_n + r_n+1 r_n + 1=0} {TEX}:: |
+ | {TEX()} {r_0 = r_1 q_1 + r_2 , 0{TEX()} {r_1 = r_2 q_2 + r_3 , 0... ... ... {TEX()} {r_{n-2} = r_{n-1} q_{n-1} + r_n , 0{n-1}} {TEX} {TEX()} {r_{n - 1} = r_n q_n + r_{n+1} , r_{n + 1}=0} {TEX} |
- | در اینصورت ، آخرین باقیمانده ناصفر در این فرآیند {TEX()} {( a,b )} {TEX} است یعنی b,a. |
+ | در اینصورت ، آخرین باقیمانده ناصفر در این فرآیند {TEX()} {(a,b)} {TEX} است یعنی {TEX()} {b,a} {TEX}. |
| !مباحث مرتبط با عنوان | | !مباحث مرتبط با عنوان |
| *((اعداد اول)) | | *((اعداد اول)) |
| *((استقرای ریاضی)) | | *((استقرای ریاضی)) |
| *((الگوریتم اقلیدس)) | | *((الگوریتم اقلیدس)) |
| *((الگوریتم تقسیم)) | | *((الگوریتم تقسیم)) |
| *((قضایای نظریه اعداد)) | | *((قضایای نظریه اعداد)) |
| *((نظریه اعداد)) | | *((نظریه اعداد)) |
- | *((نظریه همنهشتی)) |
+ | *((نظریه همنهشتی))#@^
مطلب از: آیدا سلیم نژاد |