تاریخچه ی:
نظریه همنهشتی
!مقدمه
((گاوس)) نهاد قابل توجهی را معرفی کرد که بسیاری از مسائل ((بخشپذیری)) اعداد صحیح با آن ساده میشوند. وی با این کار شاخه جدید از نظریه اعداد را ابداع نمود بنام نظریه همنهشتیها، که مبانی آن در این مقاله مورد بحث قرار خواهند گرفت.
!تعریف
فرض کنیم a , b , m اعدادی صحیح باشند و m>0. گوییم a همنهشت b به هنگ m است و مینویسیم:
::{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.
!!یک نکته جالب
گاوس علامت همنهشتی {TEX()} {\equiv} {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}
#{TEX()} {a \alpha \equiv b \beta ( modm )} {TEX}
#به ازای هر عدد صحیح مثبت n ، {TEX()} {a^n \equiv b^n ( 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}
*هرگاه {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} و {TEX()} {0 \le | b-a |
*{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()} {f( x\ right)} {TEX} با ضرایب صحیح میپردازیم؛ در نتیجه ، مقادیر این چندجملهایها در صورت صحیح بودن x صحیح میباشند. عدد صحیح x صادق در همنهشتی چندجملهای:
::{TEX()} {f( x) \equiv 0 ( modm )} {TEX}::
یک جواب همنهشتی نام دارد. البته اگر {TEX()} {x \equiv y ( modm )} {TEX} ، {TEX()} {f( x) \equiv f ( y ) ( modm )} {TEX} ؛ در نتیجه هر همنهشتی جوابدار بینهایت جواب دارد. بنابراین دقت میکنیم تا جوابهای متعلق به یک رده ماندهای متمایز محسوب نشوند. بنابراین همنهشتی چندجملهای به هنگ m حداکثر m جواب خواهد داشت.
!!قضیههای مربوط به همنهشتی خطی
نظریه همنهشتیهای خطی به قضیههایی که ذیلا بیان میشود کاملا توصیف میشوند.
!!قضیه 1
فرض کنیم {TEX()} {( a,m )=1} {TEX} (یعنی m,a نسبت بهم اول باشند یا اصطلاحا متباین باشند). در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دقیقا یک جواب خواهد داشت.
!!قضیه 2
فرض کنیم {TEX()} {( a,m )=d} {TEX} و در اینصورت ، همنهشتی خطی {TEX()} {ax \equiv b ( mod m )} {TEX} دارای جواب است اگر و فقط اگر a|b.
!!قضیه 3
فرض کنیم {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}
که در آنها t جواب (منحصر بفرد به هنگ {TEX()} {\frac{m}{d}} {TEX} ((همنهشتی خطی)) زیر میباشد.
{TEX()} {\frac{a}{d} x \equiv \frac{b}{d} ( mod m )} {TEX}
!!قضیه4
هرگاه {TEX()} {( a,b )=d} {TEX} ، اعداد صحیحی چون y,x وجود دارند بطوری که {TEX()} {ax + by = d} {TEX}.
!دستگاههای ماندهای تحویل یافته و قضیه اویلر- فرما
منظور از یک دستگاه ماندهای تحویل یافته به هنگ 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 )= \sim_{k=1}^m '1} {TEX}::
که در آن علامت ' نشان میدهد که مجموع روی 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,m )=1} {TEX}. در اینصورت ، داریم:
::{TEX()} {a^\phi ( m ) \equiv 1 ( mod m )} {TEX}::
همنهشتیهای چندجملهای به هنگ p. ((قضیه لاگرانژ)).
قضیه اساسی جبر میگوید که ، به ازای هر چندجملهای f از درجه {TEX()} {n \ge 1} {TEX} ، معادله {TEX()} {f( x )=0} {TEX} دارای n جواب در اعداد مختلط دارد. مشابه مستقیم این قضیه برای همنهشتیهای چندجملهای وجود دارد.
!!قضیه لاگرانژ
به ازای عدد اول p ، فرض کنیم:
::{TEX()} {f( x )=C_0+C_1 x+...+C_n x^n} {TEX}::
یک چندجملهای از درجه n با ضرایب صحیح باشد بطوری که {TEX()} {C_n \equiv 0 ( mod p )} {TEX}. در اینصورت همنهشتی چندجملهای:
:: {TEX()} {f( x ) equiv 0 ( mod p } {TEX}::
حداکثر n جواب خواهد داشت.
*__تذکر:__ این نتیجه برای هنگهای مرکب درست نیست. مثلا ، همنهشتی درجه دو {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 بخشپذیر خواهد بود.
#به ازای هر عدد اول 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()}
#((قضیه ولستون)) هولم ، به ازای هر عدد اول {TEX()} {p \ge 5} {TEX} ، داریم: {TEX()} {\sum_{k=1}^p-1 \frac{( p-1 )!}{k} \equiv 0 ( mod p^2 )} {TEX}
!مباحث مرتبط با عنوان
*((بخشپذیری))
*((قضیه ولستون))
*((قضیه ویلسون))
*((قضیه لاگرانژ))
*((معادلات همنهشتی))
*((همنهشتی و نظریه اعداد))
*((همنهشتیهای خطی))
*((همنهشتیهای چندجملهای))