تاریخچه ی:
نظریه همنهشتی
تفاوت با نگارش: 3
| ^ | | ^ |
| @#16: | | @#16: |
| !مقدمه | | !مقدمه |
| ((گاوس)) نهاد قابل توجهی را معرفی کرد که بسیاری از مسائل ((بخشپذیری)) اعداد صحیح با آن ساده میشوند. وی با این کار شاخه جدید از نظریه اعداد را ابداع نمود بنام نظریه همنهشتیها، که مبانی آن در این مقاله مورد بحث قرار خواهند گرفت. | | ((گاوس)) نهاد قابل توجهی را معرفی کرد که بسیاری از مسائل ((بخشپذیری)) اعداد صحیح با آن ساده میشوند. وی با این کار شاخه جدید از نظریه اعداد را ابداع نمود بنام نظریه همنهشتیها، که مبانی آن در این مقاله مورد بحث قرار خواهند گرفت. |
| --- | | --- |
| !تعریف | | !تعریف |
| فرض کنیم a , b , m اعدادی صحیح باشند و m>0. گوییم a همنهشت b به هنگ m است و مینویسیم:
| | فرض کنیم a , b , m اعدادی صحیح باشند و m>0. گوییم a همنهشت b به هنگ m است و مینویسیم:
|
| ::{TEX()} {a \equiv b ( mod m )} {TEX}:: | | ::{TEX()} {a \equiv b ( mod m )} {TEX}:: |
| اگر m تفاضل a-b را عاد نماید. عدد m هنگ همنهشتی نامیده میشود. بعبارت دیگر همنهشتی فوق رابطه بخشپذیری {TEX()} {m| ( a-b )} {TEX} است. در حالت خاص، {TEX()} {a \equiv 0 ( modm )} {TEX} اگر و فقط اگر m|a بنابراین ، {TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر {TEX()} {a-b \equiv 0 ( modm )} {TEX}. اگر m عاد نکند a-b را ، مینویسیم {TEX()} {a \noequiv b (modm )} {TEX} و میگوییم b,a ناهمنهشتاند به هنگ m. | | اگر m تفاضل a-b را عاد نماید. عدد m هنگ همنهشتی نامیده میشود. بعبارت دیگر همنهشتی فوق رابطه بخشپذیری {TEX()} {m| ( a-b )} {TEX} است. در حالت خاص، {TEX()} {a \equiv 0 ( modm )} {TEX} اگر و فقط اگر m|a بنابراین ، {TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر {TEX()} {a-b \equiv 0 ( modm )} {TEX}. اگر m عاد نکند a-b را ، مینویسیم {TEX()} {a \noequiv b (modm )} {TEX} و میگوییم b,a ناهمنهشتاند به هنگ m. |
| !!یک نکته جالب | | !!یک نکته جالب |
| گاوس علامت همنهشتی {TEX()} {\equiv} {TEX} را بخاطر تشابهش با علامت تساوی = انتخاب کرد. | | گاوس علامت همنهشتی {TEX()} {\equiv} {TEX} را بخاطر تشابهش با علامت تساوی = انتخاب کرد. |
| --- | | --- |
| !خواص همنهشتیها | | !خواص همنهشتیها |
| *همنهشتی یک رابطه هم ارزی است یعنی دارای انعکاس- تقارن و تعدی میباشد.
| | *همنهشتی یک رابطه هم ارزی است یعنی دارای انعکاس- تقارن و تعدی میباشد.
|
| *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {\alpha \equiv \beta ( modm )} {TEX} آنگاه:
| | *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {\alpha \equiv \beta ( modm )} {TEX} آنگاه:
|
| #به ازای هر دو عدد صحیح x و y ، {TEX()} { a x+\alpha y \equiv bx+\beta y ( modm )} {TEX}
| | #به ازای هر دو عدد صحیح x و y ، {TEX()} { a x+\alpha y \equiv bx+\beta y ( modm )} {TEX}
|
| #{TEX()} {a \alpha \equiv b \beta ( modm )} {TEX}
| | #{TEX()} {a \alpha \equiv b \beta ( modm )} {TEX}
|
| #به ازای هر عدد صحیح مثبت n ، {TEX()} {a^n \equiv b^n ( modm )} {TEX}
| | #به ازای هر عدد صحیح مثبت n ، {TEX()} {a^n \equiv b^n ( modm )} {TEX}
|
| #به ازای هر چندجملهای f با ضرایب صحیح ، {TEX()} {f( a) \equiv f ( b ) ( modm )} {TEX}
| | #به ازای هر چندجملهای f با ضرایب صحیح ، {TEX()} {f( a) \equiv f ( b ) ( modm )} {TEX}
|
| منظور از هر چهار قسمت فوق این است که دو همنهشتی با یک هنگ را میتوان جملهبهجمله بهم افزود، از یکدیگر کم کرد. یا درهم ضرب نمود. بنحوی که گویی تساویاند. این مطلب برای تعدادی متناهی همنهشتی با یک هنگ نیز برقرار است.
| | منظور از هر چهار قسمت فوق این است که دو همنهشتی با یک هنگ را میتوان جملهبهجمله بهم افزود، از یکدیگر کم کرد. یا درهم ضرب نمود. بنحوی که گویی تساویاند. این مطلب برای تعدادی متناهی همنهشتی با یک هنگ نیز برقرار است.
|
| *هرگاه c>0 ، {TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر {TEX()} {ac \equiv bc ( modm )} {TEX}
| | *هرگاه c>0 ، {TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر {TEX()} {ac \equiv bc ( modm )} {TEX}
|
| *هرگاه {TEX()} {ac \equiv bc ( modm )} {TEX} و {TEX()} {d= ( m,c )} {TEX} ، آنگاه {TEX()} {a \equiv b ( modm \frac{m}{d} )} {TEX}
| | *هرگاه {TEX()} {ac \equiv bc ( modm )} {TEX} و {TEX()} {d= ( m,c )} {TEX} ، آنگاه {TEX()} {a \equiv b ( modm \frac{m}{d} )} {TEX}
|
| *فرض کنیم {TEX()} {a \equiv b ( modm )} {TEX} و هرگاه d|m و d|a آنگاه d|b
| | *فرض کنیم {TEX()} {a \equiv b ( modm )} {TEX} و هرگاه d|m و d|a آنگاه d|b
|
| *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {0 \le | b-a |
| | *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {0 \le | b-a |
|
| *{TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر b,a در تقسیم بر m یک باقیمانده داشته باشند.
| | *{TEX()} {a \equiv b ( modm )} {TEX} اگر و فقط اگر b,a در تقسیم بر m یک باقیمانده داشته باشند.
|
| *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {a \equiv b ( modn )} {TEX} که در آنها {TEX()} {( m,n )=1} {TEX} ، آنگاه {TEX()} {a \equiv b ( modmn )} {TEX} | | *هرگاه {TEX()} {a \equiv b ( modm )} {TEX} و {TEX()} {a \equiv b ( modn )} {TEX} که در آنها {TEX()} {( m,n )=1} {TEX} ، آنگاه {TEX()} {a \equiv b ( modmn )} {TEX} |
| --- | | --- |
| !همنهشتیهای خطی | | !همنهشتیهای خطی |
| همنهشتیهای چندجملهای را میتوان تا حدود زیادی مثل معادلات چندجملهای در ((جبر)) مطالعه کرد. با اینحال ، در اینجا به چندجملهایهای {TEX()} {f( x\ right)} {TEX} با ضرایب صحیح میپردازیم؛ در نتیجه ، مقادیر این چندجملهایها در صورت صحیح بودن x صحیح میباشند. عدد صحیح x صادق در همنهشتی چندجملهای:
| | همنهشتیهای چندجملهای را میتوان تا حدود زیادی مثل معادلات چندجملهای در ((جبر)) مطالعه کرد. با اینحال ، در اینجا به چندجملهایهای {TEX()} {f( x\ right)} {TEX} با ضرایب صحیح میپردازیم؛ در نتیجه ، مقادیر این چندجملهایها در صورت صحیح بودن x صحیح میباشند. عدد صحیح x صادق در همنهشتی چندجملهای:
|
- | ::{TEX()} {f( x) \equiv 0 ( modm )} {TEX}:: |
+ | @@{TEX()} {f( x) \equiv 0 ( modm )} {TEX}@@ |
| یک جواب همنهشتی نام دارد. البته اگر {TEX()} {x \equiv y ( modm )} {TEX} ، {TEX()} {f( x) \equiv f ( y ) ( modm )} {TEX} ؛ در نتیجه هر همنهشتی جوابدار بینهایت جواب دارد. بنابراین دقت میکنیم تا جوابهای متعلق به یک رده ماندهای متمایز محسوب نشوند. بنابراین همنهشتی چندجملهای به هنگ m حداکثر m جواب خواهد داشت. | | یک جواب همنهشتی نام دارد. البته اگر {TEX()} {x \equiv y ( modm )} {TEX} ، {TEX()} {f( x) \equiv f ( y ) ( modm )} {TEX} ؛ در نتیجه هر همنهشتی جوابدار بینهایت جواب دارد. بنابراین دقت میکنیم تا جوابهای متعلق به یک رده ماندهای متمایز محسوب نشوند. بنابراین همنهشتی چندجملهای به هنگ m حداکثر m جواب خواهد داشت. |
| !!قضیههای مربوط به همنهشتی خطی | | !!قضیههای مربوط به همنهشتی خطی |
| نظریه همنهشتیهای خطی به قضیههایی که ذیلا بیان میشود کاملا توصیف میشوند. | | نظریه همنهشتیهای خطی به قضیههایی که ذیلا بیان میشود کاملا توصیف میشوند. |
| !!قضیه 1 | | !!قضیه 1 |
| فرض کنیم {TEX()} {( a,m )=1} {TEX} (یعنی m,a نسبت بهم اول باشند یا اصطلاحا متباین باشند). در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دقیقا یک جواب خواهد داشت. | | فرض کنیم {TEX()} {( a,m )=1} {TEX} (یعنی m,a نسبت بهم اول باشند یا اصطلاحا متباین باشند). در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دقیقا یک جواب خواهد داشت. |
| !!قضیه 2 | | !!قضیه 2 |
| فرض کنیم {TEX()} {( a,m )=d} {TEX} و در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دارای جواب است اگر و فقط اگر a|b. | | فرض کنیم {TEX()} {( a,m )=d} {TEX} و در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دارای جواب است اگر و فقط اگر a|b. |
| !!قضیه 3 | | !!قضیه 3 |
| فرض کنیم {TEX()} {( a,m )=d} {TEX} و d|b. در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دقیقا d جواب به هنگ m دارند. این جوابها عبارتند از:
| | فرض کنیم {TEX()} {( a,m )=d} {TEX} و d|b. در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دقیقا d جواب به هنگ m دارند. این جوابها عبارتند از:
|
- | {TEX()} {t , t+ \frac{m}{d} , t+2 \frac{m}{d} ,..., t+ ( d-1 ) \frac{m}{d}} {TEX} |
+ | @@{TEX()} {t , t+ \frac{m}{d} , t+2 \frac{m}{d} ,..., t+ ( d-1 ) \frac{m}{d}} {TEX}@@ |
| که در آنها t جواب (منحصر بفرد به هنگ {TEX()} {\frac{m}{d}} {TEX} ((همنهشتی خطی)) زیر میباشد. | | که در آنها t جواب (منحصر بفرد به هنگ {TEX()} {\frac{m}{d}} {TEX} ((همنهشتی خطی)) زیر میباشد. |
- | {TEX()} {\frac{a}{d} x \equiv \frac{b}{d} ( mod m )} {TEX} |
+ | @@{TEX()} {\frac{a}{d} x \equiv \frac{b}{d} ( mod m )} {TEX} @@ |
| !!قضیه4 | | !!قضیه4 |
| هرگاه {TEX()} {( a,b )=d} {TEX} ، اعداد صحیحی چون y,x وجود دارند بطوری که {TEX()} {ax + by = d} {TEX}. | | هرگاه {TEX()} {( a,b )=d} {TEX} ، اعداد صحیحی چون y,x وجود دارند بطوری که {TEX()} {ax + by = d} {TEX}. |
| --- | | --- |
| !دستگاههای ماندهای تحویل یافته و قضیه اویلر- فرما | | !دستگاههای ماندهای تحویل یافته و قضیه اویلر- فرما |
| منظور از یک دستگاه ماندهای تحویل یافته به هنگ m یعنی مجموعهای مرکب از {TEX()} {\phi ( m )} {TEX} عدد صحیح ناهمنهشت به هنگ m بطوری که هریک از آنها نسبت به m اول باشد.
| | منظور از یک دستگاه ماندهای تحویل یافته به هنگ m یعنی مجموعهای مرکب از {TEX()} {\phi ( m )} {TEX} عدد صحیح ناهمنهشت به هنگ m بطوری که هریک از آنها نسبت به m اول باشد.
|
| __تذکر__: {TEX()} {\phi ( m )} {TEX} کامل ~~green:__اویلر__~~ است یعنی اگر {TEX()} {n \ge 1} {TEX} ، کامل اویلر {TEX()} {\phi ( m )} {TEX} مساوی تعداد اعداد صحیح مثبتی تعریف میشود که از n بیشتر نبوده و نسبت به n اول باشند بنابراین:
| | __تذکر__: {TEX()} {\phi ( m )} {TEX} کامل ~~green:__اویلر__~~ است یعنی اگر {TEX()} {n \ge 1} {TEX} ، کامل اویلر {TEX()} {\phi ( m )} {TEX} مساوی تعداد اعداد صحیح مثبتی تعریف میشود که از n بیشتر نبوده و نسبت به n اول باشند بنابراین:
|
- | ::{TEX()} {\phi ( m )= \sim_{k=1}^m '1} {TEX}:: |
+ | @@{TEX()} {\phi ( m )= \sim_{k=1}^m '1} {TEX}@@ |
| که در آن علامت ' نشان میدهد که مجموع روی k هایی گرفته شده است که نسبت به m اول هستند. | | که در آن علامت ' نشان میدهد که مجموع روی k هایی گرفته شده است که نسبت به m اول هستند. |
| !!قضیه | | !!قضیه |
| هرگاه {TEX()} {\{ a_1,a_2,...,a_\phi ( m ) \}} {TEX} یک دستگاه ماندهای تحویل یافته به هنگ m بوده و {TEX()} {( k,m )=1} {TEX} ، آنگاه {TEX()} {\{ ka_1,ka_2,...,ka_\phi ( m ) \}} {TEX} نیز یک دستگاه ماندهای تحویل یافته به هنگ m است. | | هرگاه {TEX()} {\{ a_1,a_2,...,a_\phi ( m ) \}} {TEX} یک دستگاه ماندهای تحویل یافته به هنگ m بوده و {TEX()} {( k,m )=1} {TEX} ، آنگاه {TEX()} {\{ ka_1,ka_2,...,ka_\phi ( m ) \}} {TEX} نیز یک دستگاه ماندهای تحویل یافته به هنگ m است. |
| !!قضیه اویلر- فرما | | !!قضیه اویلر- فرما |
| فرض کنیم {TEX()} {( a,m )=1} {TEX}. در اینصورت ، داریم:
| | فرض کنیم {TEX()} {( a,m )=1} {TEX}. در اینصورت ، داریم:
|
- | ::{TEX()} {a^\phi ( m ) \equiv 1 ( mod m )} {TEX}:: |
+ | @@{TEX()} {a^\phi ( m ) \equiv 1 ( mod m )} {TEX}@@ |
| همنهشتیهای چندجملهای به هنگ p. ((قضیه لاگرانژ)). | | همنهشتیهای چندجملهای به هنگ p. ((قضیه لاگرانژ)). |
| قضیه اساسی جبر میگوید که ، به ازای هر چندجملهای f از درجه {TEX()} {n \ge 1} {TEX} ، معادله {TEX()} {f( x )=0} {TEX} دارای n جواب در اعداد مختلط دارد. مشابه مستقیم این قضیه برای همنهشتیهای چندجملهای وجود دارد. | | قضیه اساسی جبر میگوید که ، به ازای هر چندجملهای f از درجه {TEX()} {n \ge 1} {TEX} ، معادله {TEX()} {f( x )=0} {TEX} دارای n جواب در اعداد مختلط دارد. مشابه مستقیم این قضیه برای همنهشتیهای چندجملهای وجود دارد. |
| !!قضیه لاگرانژ | | !!قضیه لاگرانژ |
| به ازای عدد اول p ، فرض کنیم:
| | به ازای عدد اول p ، فرض کنیم:
|
- | ::{TEX()} {f( x )=C_0+C_1 x+...+C_n x^n} {TEX}:: |
+ | @@{TEX()} {f( x )=C_0+C_1 x+...+C_n x^n} {TEX}@@ |
| یک چندجملهای از درجه n با ضرایب صحیح باشد بطوری که {TEX()} {C_n \equiv 0 ( mod p )} {TEX}. در اینصورت همنهشتی چندجملهای:
| | یک چندجملهای از درجه n با ضرایب صحیح باشد بطوری که {TEX()} {C_n \equiv 0 ( mod p )} {TEX}. در اینصورت همنهشتی چندجملهای:
|
- | :: {TEX()} {f( x ) equiv 0 ( mod p } {TEX}:: |
+ | @@ {TEX()} {f( x ) equiv 0 ( mod p } {TEX}@@ |
| حداکثر n جواب خواهد داشت. | | حداکثر n جواب خواهد داشت. |
| *__تذکر:__ این نتیجه برای هنگهای مرکب درست نیست. مثلا ، همنهشتی درجه دو {TEX()} {x^2 \equiv 1 ( mod 8 )} {TEX} چهار جواب دارد. | | *__تذکر:__ این نتیجه برای هنگهای مرکب درست نیست. مثلا ، همنهشتی درجه دو {TEX()} {x^2 \equiv 1 ( mod 8 )} {TEX} چهار جواب دارد. |
| !!کاربردهای قضیه لاگرانژ | | !!کاربردهای قضیه لاگرانژ |
| #هرگاه {TEX()} {f( x )=C_0+C_1 x+...+C_n x^n} {TEX} یک چندجملهای از درجه n با ضرایب صحیح بوده و همنهشتی {TEX()} {f( x ) equiv 0 ( mod p } {TEX} بیش از n جواب داشته باشد، که در آن p اول است، آنگاه هر ضریب f بر p بخشپذیر خواهد بود.
| | #هرگاه {TEX()} {f( x )=C_0+C_1 x+...+C_n x^n} {TEX} یک چندجملهای از درجه n با ضرایب صحیح بوده و همنهشتی {TEX()} {f( x ) equiv 0 ( mod p } {TEX} بیش از n جواب داشته باشد، که در آن p اول است، آنگاه هر ضریب f بر p بخشپذیر خواهد بود.
|
| #به ازای هر عدد اول p ، همه ضریبهای چندجملهای {TEX()} {f?( x )=( x-1 ) ( x-2 )... ( x-p+1 )-x^p-1 +1} {TEX} بر p بخشپذیر است.
| | #به ازای هر عدد اول p ، همه ضریبهای چندجملهای {TEX()} {f?( x )=( x-1 ) ( x-2 )... ( x-p+1 )-x^p-1 +1} {TEX} بر p بخشپذیر است.
|
| #((قضیه ویلسون)): به ازای هر عدد اول p ، داریم: {TEX()} {( p-1 )! \equiv -1 ( mod p ){TEX()}
| | #((قضیه ویلسون)): به ازای هر عدد اول p ، داریم: {TEX()} {( p-1 )! \equiv -1 ( mod p ){TEX()}
|
- | #((قضیه ولستون)) هولم ، به ازای هر عدد اول {TEX()} {p \ge 5} {TEX} ، داریم: {TEX()} {\sum_{k=1}^p-1 \frac{( p-1 )!}{k} \equiv 0 ( mod p^2 )} {TEX} |
+ | #((قضیه ولستون)) هولم ، به ازای هر عدد اول {TEX()} {p \ge 5} {TEX} ، داریم: @@{TEX()} {\sum_{k=1}^p-1 \frac{( p-1 )!}{k} \equiv 0 ( mod p^2 )} {TEX}@@ |
| --- | | --- |
| !مباحث مرتبط با عنوان | | !مباحث مرتبط با عنوان |
| *((بخشپذیری)) | | *((بخشپذیری)) |
| *((قضیه ولستون)) | | *((قضیه ولستون)) |
| *((قضیه ویلسون)) | | *((قضیه ویلسون)) |
| *((قضیه لاگرانژ)) | | *((قضیه لاگرانژ)) |
| *((معادلات همنهشتی)) | | *((معادلات همنهشتی)) |
| *((همنهشتی)) | | *((همنهشتی)) |
| *((همنهشتی و نظریه اعداد)) | | *((همنهشتی و نظریه اعداد)) |
| *((همنهشتیهای خطی)) | | *((همنهشتیهای خطی)) |
| *((همنهشتیهای چندجملهای))#@ | | *((همنهشتیهای چندجملهای))#@ |
| + | مطلب از: آیدا سلیم نژاد |
| ^ | | ^ |