هم‌ نهشتی (تعریف و قضایا)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 03 شهریور 1400
دسته‌بندی: نظریه اعداد
امتیاز:
بازدید: 42 مرتبه

مقدمه‌ای بر هم‌نهشتی

در هندسه دو شکل را هم‌نهشت گویند، هرگاه قابل انطباق باشند.

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

تمرین

باقیمانده تقسیم هر عدد بر 3 یکی از اعداد 2  ,  1  ,  0 می‌باشد.

مجموعه اعدادی که باقیمانده آنها بر 3 مساوی 0 است را بنویسید. 

A0=x|x=3k+0=  ,  3  ,  0  ,  3  ,  6  ,  

مجموعه اعدادی که باقیمانده آنها بر 3 مساوی 1 است را بنویسید. 

A1=x|x=3k+1=,  2  ,  1  ,  4  ,  7  ,

مجموعه اعدادی که باقیمانده آنها بر 3 مساوی 2 است را بنویسید. 

A2=x|x=3k+2=,  1  ,  2  ,  5  ,  8  ,

دو عضو دل‌خواه از مجموعه A1 را در نظر بگیرید، تفاضل این دو عدد مضرب چه عددی است؟

دو عضو دل‌خواه از مجموعه A1 مانند 10 و -5 را در نظر می‌گیریم، تفاضل این دو عدد عبارت است از:

105=15


تفاضل این دو عدد مضربی از 3 است.

دو عضو دل‌خواه دیگر از مجموعه A1 را در نظر بگیرید، تفاضل این دو عدد مضرب چه عددی است؟

دو عضو دل‌خواه از مجموعه A1 مانند 7 و -2 را در نظر می‌گیریم، تفاضل این دو عدد عبارت است از:

72=9


تفاضل این دو عدد مضربی از 3 است.

آیا تفاضل هر دو عضو دل‌خواه از مجموعه A1 مضربی از 3 است؟ 

x=3k+1y=3t+1xy=3kt


ملاحظه می‌شود که تفاضل هر دو عضو مجموعه A1 مضربی از 3 است.  

آیا این امر در مورد مجموعه‌های A0 و A2 صادق است؟ 

بله

تفاضل هر دو عضو دل‌خواه از مجموعه‌های A0 و A2 مضربی از 3 است.

آیا عکس این مطلب درست است؟

بله

اگر x-y مضربی از 3 باشد، x و y هر دو متعلق به‌یکی از مجموعه‌های A0 و A1 و A2 است.    

دو عدد هم‌نهشت به پیمانه 3 به چه معناست؟

دو عددی که تفاضل آنها، مضرب 3 باشد، یعنی دو عددی که هر دو در یکی از مجموعه‌های A0 و A1 و A2 قرار داشته باشند را دو عدد هم‌نهشت به پیمانه 3 می‌گویند.  

تمرین

فرض کنید ظرف A گنجایش 37 لیتر و ظرف B گنجایش 51 لیتر آب داشته باشد و هر دو ظرف پر از آب باشند و بخواهیم با یک پیمانه 7 لیتری، از آنها آب بر‌داریم. 

پس از چند بار استفاده از پیمانه در ظرف A، فقط 2 لیتر آب باقی می‌ماند؟ 

با یک پیمانه 7 لیتری، اگر از ظرف A با گنجایش 37 لیتر، 5 بار آب برداریم، فقط 2 لیتر آب باقی می‌ماند.  

پس از چند بار استفاده از پیمانه در ظرف B، فقط 2 لیتر آب باقی می‌ماند؟ 

با یک پیمانه 7 لیتری، اگر از ظرف B با گنجایش 51 لیتر، 7 بار آب برداریم، فقط 2 لیتر آب باقی می‌ماند.  

آیا دو ظرف A و B به پیمانه 7 هم‌نهشت (هم‌پیمانه) هستند؟ 

بله

مطلب فوق را به‌‌صورت زیر نشان می‌دهیم:

A7B

تعریف هم‌نهشتی

اگر m یک عدد طبیعی باشد، دو عدد صحیح a و b را به پیمانه m هم‌نهشت گویند، هرگاه تفاضل آنها مضرب m باشد:

a,bΖ    ;ambab=mkm|ab

تمرین

معادل هم‌نهشتی‌های زیر را بر اساس تعریف فوق بنویسید.

3724

3724324=21=377|21

31711

317113111=42=677|42

852

85282=10=255|10

1434

1434144=18=633|18

تمرین

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

a=3k+1

a=3k+1a1=3ka31

a=6k4

a=6k4a+4=6ka64

a=13k

a=13ka0=13ka130

دسته هم‌نهشتیrبه پیمانهm

مجموعه همه اعداد صحیح که باقیمانده تقسیم آنها بر عدد طبیعی m برابر r باشند را کلاس یا دسته هم‌نهشتی r به پیمانه m می‌نامیم و با نمادrm نمایش می‌دهیم:

Ar=xx=mk+r=xxmr=rm

به‌عنوان نمونه با توجه به این‌که باقیمانده تقسیم هر عدد بر 3 یکی از اعداد 2  ,  1  ,  0 می‌باشد، بنابراین سه مجموعه به‌صورت زیر خواهیم  داشت:

A0=x|x=3k+0=...,3,0,3,6,...=03

A1=x|x=3k+1=...,2,1,4,7,...=13

A2=x|x=3k+2=...,1,2,5,8,...=23

نکته

1- در حالتی‌که a-b بر m بخش پذیر نباشد، گوییم a هم‌نهشت b هم‌پیمانه m نیست و می‌نویسیم:  

amb


2-
 گزاره (a و b به پیمانه m هم‌نهشت است) را با نماد‌های زیر نشان می‌دهیم:  

amb

(پیمانه m)ab

(هنگ m)ab

ab  mod  m


3- با توجه به این‌که هر عددی بر 1 بخش پذیر است، بنابراین هر دو عدد صحیح به پیمانه 1 هم‌نهشت‌اند، از این روست که در عمل، پیمانه غیر از مورد نظر ما است. 


4- هر عدد مانند m هم‌نهشت با صفر است به پیمانه m 

mm0a=mk+0a0=mkam0


5- می‌دانیم اگر 0r<m باشد، در این‌صورت باقیمانده r بر m خود r است.

به‌عنوان نمونه:

باقیمانده 2 بر 5 خود 2 است یعنی 252.

به‌همین ترتیب باقیمانده 4,3,2,1,0 بر 5 خود این اعداد هستند.

به‌طور کلی اگر amr به‌طوری‌که 0r<m باشد، در این‌صورت باقیمانده a بر m مساوی r است.

   a   m         q           a=mq+rar=mqamr    r¯

با توجه به این نکته در می‌یابیم که برای به‌دست آوردن عددی که با a به پیمانه m هم‌نهشت باشد، کافی است که باقیمانده تقسیم عدد a بر m را به‌دست آوریم. 

به‌عبارتی برای به‌دست آوردن طرف دوم هم‌نهشتی باید باقیمانده تقسیم طرف اول بر پیمانه را به‌دست آوریم.

به‌عنوان نمونه داریم:

2734?    ;    273=468+127341810?         ;    8=100+88108


6- در هم‌نهشتی am? تا زمانی که 0a<m باشد، حاصل طرف دوم، خود a خواهد بود یعنی:

ama0a<m

قضایای هم‌نهشتی

قضیه

رابطه هم‌نهشتی به پیمانه m روی  یک رابطه هم‌ارزی است.

اثبات

باید ثابت کنیم رابطه m دارای سه خاصیت بازتابی، تقارنی، تعدی است:

a  maaΖ    ;    aa=0aa=m×0a  ma

رابطه فوق دارای خاصیت بازتابی ست.

a,bΖ    ;    ambbmaa,bΖ    ;    ambm|abm|abm|baba=mkbma

رابطه فوق دارای خاصیت تقارنی است.

a,b,cΖ     ;    amb  ,  bmcamc  ambab=mkm|ab  bmcbc=mk'm|bcm|ab+b-cm|acamc

رابطه فوق دارای خاصیت تعدی است.

قضیه

اگر عدد a را بر m تقسیم کنیم و باقیمانده r شود، آن‌گاه a هم‌نهشت است با r به پیمانه m

اثبات

   a   m          q          a=mq+rar=mqamr    r  ¯

نکته

نتایج حاصل از قضیه فوق عبارتند از:

1- با استفاده از این قضیه، اگر بخواهیم محاسبه کنیم که عدد a به پیمانه m با چه عددی هم‌نهشت است، کافی است باقیمانده تقسیم a را بر m به‌دست آوریم.

به‌عنوان نمونه داریم:

4489?     ;     448=499+7448  97


2- هر مضرب m به پیمانه m هم‌نهشت با صفر است: 

a=mka   m0

قضیه

به دو طرف یک رابطه هم نهشتی، هر مضربی صحیح از پیمانه m را می‌توان اضافه کرد:

amb  t  ,  kΖ    ;    a+mt  mb+mk

اثبات

a  mbab=mk1ab+mtmk=mk1+mtmka+mtb+mk=mk1+mtk     ;    tk=k2a+mtb+mk=mk1+k2    ;    q=k1+k2a+mtb+mk=mqa+mtmb+mk

نکته

نتایج حاصل از قضیه فوق عبارتند از:

1- در حالتی‌که t=0 باشد، داریم:

amb+mk

به‌عنوان نمونه داریم:

a74a74+71a73a8117a8117+15883a83a1319a1319+213137a137a121a121+1211211a1211a867a864+3886+383a83


2- برای به‌دست آوردن هم‌نهشتی اعداد منفی باید مضربی از پیمانه را به آن اضافه کنیم تا عدد مثبت شود وفرمول مطرح شده این امکان را به ما می‌دهد.

به‌عنوان نمونه داریم:

1147?    ;    1147114+7177114+11975114751913?      ;    191319+1321319+267719137

قوانین هم‌نهشتی

در تمام ویژگی‌های ذکر شده در زیر a و b و c و d اعداد صحیح و m عدد طبیعی است.

amba±cmb±c

اثبات

ambab=mkab+cc=mka+cb+c=mka+cmb+c

برای حالت منفی هم به‌همین صورت اثبات می‌شود.

ambacmbc

اثبات

ambab=mkmabmabcmacbcacbc=mk'acmbc

عکس قانون فوق همواره برقرا نمی‌باشد و قانون حذف برای رابطه هم‌نهشتی در حالت کلی برقرا نیست.

ambcmda±cmb±d

اثبات

ambab=mkmabcmdcd=mk'mcdma±cb±da±cmb±d

حالت اخیر قابل تعمیم برای n رابطه هم‌نهشتی می‌باشد.

دوطرف n رابطه هم‌نهشتی که پیمانه همگی m باشند، می توانند با هم جمع شوند و عکس مطلب فوق در حالت کلی صادق نیست.   

ambcmdacmbd

اثبات

ambab=mkmabmacbccmdcd=mk'mcdmbcbd


macbc+bcbdmacbdacbd=mk''acmbd

این رابطه قابل تعمیم است.

ambanmbn

اثبات

ambab=mkmabmaban1+an2.b++bn1manbnanbn=mk'anmbn

ambbncam,nc

اثبات

if   d=m,ndm,      dnambab=mkmab  ,  dmdabbncbc=nk'nbc  ,   dndbc


dab+bcdacac=dk''adcam,nc

ambanbam,nb

اثبات

ambab=mkmabanbab=nk'nabm,nabam,nb

نکته

نتیجه حاصل از قانون فوق عبارت است از:

if    amb   ,  anb  ,  m,n=1m,n=mnam,nbamnb

amba,m=b,m

اثبات

فرض می‌کنیم a,m=d1b,m=d2 باشد، ثابت می‌کنیم d1=d2.

ambab=mkamk=b

a,m=d1d1ad1md1mkd1amkd1bd1bd1md1b,md1d2d1d2

به‌همین ترتیب ثابت می‌شود که d2d1 و در کل نتیجه می‌شود d1=d2 .  

عکس خاصیت فوق همواره صحیح است.

acmbcm,c=da mdb

اثبات

acmbcacbc=mkcab=mkcdab=mdkmdcdab     ;     md,cd=1

بر طبق لم اقلیدس داریم:

md|abab=mdk'a mdb

نکته

نتایج حاصل از قانون فوق عبارتند از:

if   acmbc  ,  m,c=1amb    

بنابراین اگر عددی را که بخواهیم حذف کنیم که نسبت به پیمانه، اول باشد، قاعده حذف بر قرار بوده و پیمانه تغییر نمی‌کند.

if   acpbc  ,  p|c  apb

amba=mq1+rb=mq2+r

دو عدد صحیح a و b به پیمانه m هم‌نهشت‌اند، اگر و تنها اگر باقیمانده a بر m مساوی باقیمانده b بر m باشد.

اثبات

ثابت می‌کنیم:

if amba=mq1+rb=mq2+r


ambab=mk     ;   0r<ma=mq1+rmq1+rb=mkb=mq1+rmkb=mq1k+rb=mq2+r    ;    0r<m

به‌عنوان نمونه داریم:

3171831=57+418=27+4


ثابت می‌کنیم:

a=mq1+rb=mq2+ramb

a=mq1+rb=mq2+rab=mq1q2ab=mqamb

به‌عنوان نمونه داریم:

56=79+711=29+756911

نکته

نتیجه حاصل از قانون فوق عبارت است از:

اگر kn عددی توان‌دار باشد و باقیمانده تقسیم آن بر عدد طبیعی m را بخواهیم، کافی است هم‌نهشتی kn را به پیمانه m بیابیم.  

knmt    ;    0t<m

طبق قانون مطرح شده، باقیمانده تقسیم kn بر m برابر است با باقیمانده تقسیم t بر m و چون t<m است پس مساوی با t خواهد بود.   

amb  ,  anb  ,  m,n=1amnb

اثبات

ambab=mk'mabanbab=nk''nabm,n=1mn|abab=mnkamnb

aimbi    ;        1ini=1naimi=1nbi

aimbi    ;       1ini=1naimi=1nbi

یادآوری

در اغلب موارد برای به‌دست آوردن باقیمانده تقسیم اعداد به‌صورت at سعی می‌کنیم با استفاده از خواص هم‌نهشتی، این اعداد را کاهش دهیم یعنی عددی کوچک‌تر بیابیم که با at هم‌نهشت باشد. 

برای این كار دو نوع مسائل را بررسی می‌كنیم:

دسته اول) توانی از a هم‌نهشت با 1 یا -1 است.

دریافت مثال

یادآوری

در دسته اول با دو مشکل مواجه هستیم:
آیا توانی از a مانند at می‌توان یافت که atm1 یا at-m1 باشد؟   
اگر چنین توانی وجود داشته باشد، چگونه می‌توان آن را یافت؟

دسته دوم)
 هیچ توانی از a هم‌نهشت با 1 یا -1 نیست.

دریافت مثال

یادآوری

اگر نتوانستیم tای بیابیم به‌طوری‌که atm1 یا at-m1 باشد در این‌صورت برای محاسبه an باید n را بر t تقسیم کنیم، لذا بنابر الگوریتم تقسیم داریم: 

n=tk+ran=atk+ran=atk.aranmar

ملاحظه می‌کنید که از تقسیم n بر t فقط به باقیمانده آن نیاز داریم.

دریافت مثال

کاربرد هم‌نهشتی در تقویم‌نگاری

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

می‌دانیم هر روز از روزهای هفته، مثلا شنبه، بعد از گذشت 7 روز دوباره تکرار می‌شود.

به‌عنوان نمونه داریم:

اگر 12 فروردین در یک سال یک‌شنبه باشد، در این‌صورت 7+12 یعنی 19 فروردین یک‌شنبه است.

هم‌چنین 7+19 یعنی 26 فروردین نیز یک‌شنبه است. 

در بحث تقویم و روزهای هفته، شش ماه اول سال همگی 31 روزه و شش ماه دوم سال غیر از اسفند که 29 (به‌جز سال کبیسه) همگی 30 روزه هستند.

تمرین

فرض کنید در یک سال 9 دی‌ماه، یکشنبه باشد، در همان سال 28 دی‌ماه چند‌شنبه است؟

با توجه به مطالب گفته شده 7+9 یعنی 16 دی و 7+16 یعنی 23 دی، نیز یک‌شنبه بوده و کافی است از 23 تا 28 دی 5 روز بعد را حساب کنیم که به روز جمعه می‌رسیم.


اگر فاصله 9 دی تا 28 دی را حساب کنیم 28-9=19 مشاهده می‌شود که 19روز فاصله داریم یعنی:

1975


لذا کافی است یک‌شنبه را مطابق جدول زیر مبدا فرض کرده و مشخص کنیم که 5 روز بعد، چه روزی از هفته است یا عدد 5 متناظر با کدام روز است.


 هم‌نهشتی -پیمان گردلو

دریافت مثال

مثال‌ها و جواب‌ها

هم‌نهشتی (تعریف و قضایا)

15,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید