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

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

قضیه اولر

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

این قضیه در واقع حالت کلی قضیه فرما است.

قضیه فرما در مورد پیمانه‌های اول است، در صورتی‌که قضیه اولر در مورد پیمانه‌های دل‌خواه m است.

در سال 1736 اولر اولین بار قضیه فرما را اثبات کرد، اما چندی بعد در سال 1760 موفق شد که صورت کلی قضیه فرما را برای پیمانه‌های عدد طبیعی دل‌خواه m را ثابت کند.

در واقع قضیه اولر به دو سوال زیر در مورد پیمانه‌های دل‌خواه m پاسخ می‌دهد: 

  • آیا توانی از a مانند t وجود دارد به‌طوری‌که atm1؟
  • در صورت وجود چنین tای آیا می‌توان از دستوری t را یافت؟

اولر برای بیان قضیه خود، تابعی را به‌نام تابع فی - اولر معرفی کرد.

تعریف تابع فی - اولر

تابع φ:NN را به‌صورت زیر تعریف می‌کنیم:

تابع φn با شرط n1 عبارت است از تعداد اعداد صحیح مثبت که کوچک‌تر از n بوده و نسبت به n اول هستند.

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

چهار عدد 7,5,3,1 نسبت به 8 اولند:

if  n=8φ8=4

هشت عدد 14,13,11,8,7,4,2,1 نسبت به 15 اولند:

if  n=15φ15=8

تابع φ را به نام ابداع کننده آن، تابع فی –اولر گویند اما نماد φn را اولین بار گاوس مطرح کرد.  

با این شیوه به‌صورت دستی در مورد یافتن φn به‌ازای مقادیر بزرگ n با مشکل روبرو هستیم اما فرمولی ارائه می‌دهیم که توسط آن مقادیر φn را برای هر عدد طبیعی n می‌توان به‌دست آورد.  

قضیه

اگر p اول باشد، در این‌صورت:

φp=p1

اثبات

چون همه اعداد p1,...,3,2,1 نسبت به p اولند، بنابراین:

φp=p1

قضیه

اگر p اول و k یک عدد طبیعی باشد، در این‌صورت:

φpk=pkpk1

اثبات

می‌دانیم:

n,p=1n,pk=1

برای شمردن اعدادی که نسبت به pk اولند، باید از میان اعداد 1 تا pk تعداد اعدادی را یافت که نسبت به p اولند، از طرف دیگر هر عدد نسبت به p دو حالت دارد، یا بر p بخش پذیر است یا نسبت به pاول است.   

اعدادی که بر p بخش پذیرند، عبارتند از:

1p  ,  p  ,  3p  ,  .....  ,  pk1p

یعنی مجموعه 1  ,  2  ,  ...  ,  p شامل pk-1 مضرب p است لذا تعداد اعدادی از این مجموعه که نسبت به p و لذا نسبت به pk اولند، برابر است با:

pkpk1

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

φp=p1φ5=4φ2=1

φpk=pkpk1φ53=5352φ16=φ24=2423

نکته

آن‌چه تاکنون بیان شد، محاسبه φn به‌ازای توان‌های یک عدد اول است، اما برای محاسبه φn به‌ازای هر عدد طبیعی نیاز به فرمولی داریم که در زیر بیان می‌کنیم:  

تابع φn تابعی ضربی است، یعنی داریم: 

m,nN  ,m,n=1φm.n=φm.φn

تمرین

مقادیر زیر را به‌دست آورید:

φ45

=φ32×5    ;    32,5=1=φ32.φ5=3231.4=6×4=24

φ1100

=φ22×52×11=φ22.φ52.φ11=2221.5251.10=2×20×10

قضیه

هرگاه p و q دو عدد اول متمایز باشند، آن‌گاه:

φpα.qβ=φpα.φqβ

اثبات

می‌دانیم مضارب عدد p که کوچک‌تر یا مساوی pα می‌باشند، عبارتند از:

p,2p,3p,......,pα1.p

اکنون اعداد فوق را به‌صورت زیر دسته‌بندی می‌کنیم و در هر دسته تعداد اعدادی که نسبت به p اولند را به‌دست می‌آوریم:

دسته اول:

p  ,  p+1  ,  p+2  ,  .....  ,  p+p2p

در این دسته تعداد اعداد کوچک‌تر و اول نسبت به عدد pα برابر است با p-1

دسته دوم:

2p  ,  2p+1  ,  2p+2  ,  .....  ,  2p+p3p    

در این دسته تعداد اعداد کوچک‌تر و اول نسبت به عدد pα برابر است با p-1

دسته pα11ام:

pα11pα1  ,  .......  ,  pα1.p

در این دسته تعداد اعداد کوچک‌تر و اول نسبت به عدد pα برابر است با p-1

بنابراین تعداد اعداد کوچک‌تر و اول نسبت به pα

φpα=pα1p1=pαpα1

به‌همین نحو می‌توان ثابت کرد که: 

φqβ=qβqβ1

اما می‌دانیم عددی که نسبت به pα.qβ اول نباشد، باید مضربی از p یا مضربی از q یا مضربی از هر دوی آنها باشد.

می‌دانیم تعداد اعدادی که کوچک‌تر از pα و qβ بوده و مضرب p باشند، برابر است با pα1.qβ.

و تعداد اعدادی که کوچک‌تر از pα و qβ بوده و مضرب q باشند، برابر است با pα.qβ-1.

و تعداد اعدادی که کوچک‌تر از pα و qβ بوده و مضرب p و q باشند، برابر است با pα-1.qβ-1.

بنابراین تعداد اعدادی که کوچک‌تر از pα و qβ بوده و نسبت به آن اولند، برابر است با:

φpα×qβ=pα×qβpα1qβ+pαqβ1pα1qβ1=pαpα1qβqβ1=φpαφqB

قضیه

اگر تجزیه استاندارد n با شرط n>1 به‌صورت زیر باشد: 

n=p1α1.p2α2.......pkαk

در این‌صورت داریم:

φn=n11p111p2......11pk

اثبات

φn=φp1α1.p2α2.....pkαk=φp1α1φp2α2.....φpkαk=p1α1p1α11.p2α2p2α21.......pkαkpkαk1

=p1α111p1.p2α211p2.....pkαk11pk=p1α1p2α2.....pkαk11p111p2   ....11pk    ;    n=p1α1.p2α2.......pkαk=n11p111p2.......11pk

به‌طور خلاصه داریم:

φn=φp1α1.....pkαk=n11p111p2.......11pk

تمرین

تعداد اعداد کوچک‌تر از n=360 که نسبت به آن اول می‌باشند را بیابید.

n=360=23×32×5φ360=360112113115=96


96 عدد موجود است که نسبت به n=360 اول است. 

قضیه

قضیه اولر

اگر m یک عدد طبیعی و a عدد صحیح باشد، به‌طوری‌که a,m=1 در این‌صورت:

aφmm1

در قضیه اولر a به‌توان φm با 1 هم‌نهشت است و این مطلب اهمیت و کاربرد این قضیه را افزایش می‌دهد. 

نکته

1- قضیه اولر برای کوچک کردن و کاهش اعداد با توان‌های بزرگ مفید است.

تمرین

ثابت کنید:

3244  10081

3,100=13φ100   100  1φ100=φ2252=100112115=40244=640+4


if   3φ100100134010013406  100  163240×34  100  1×343244  100   81


البته توجه کنید که می‌توانستیم φ100 را به‌روش زیر محاسبه کنیم:

φ100=φ22×52=φ22×φ52=2221525=2×20=40

نکته

2- همان‌طور که در قضیه اولر دیدیم، در صورتی aφmm1 است که a,m=1 لذا اگر a نسبت به m اول نباشد، هیچ توانی از a به پیمانه m هم‌نهشت با 1 و نمی‌توان از قضیه اولر استفاده کرد.  

به‌عنوان نمونه برای محاسبه 2276100? چون 2 و 100 نسبت به هم اول نیستند، نمی‌توان از قضیه اولر استفاده کنیم.


3- توجه کنید اغلب در جستجوی عددی مانند t هستیم به‌طوری‌که atm1

قضیه اولر درحالتی‌که a,m=1 باشد، یکی از این tها را ارائه می‌دهد، اما می‌توان نشان داد بی‌شمار از این tها وجود دارد، در واقع تمام مضارب t هم می‌توانند برای این کار کاندید شوند زیرا:  

atm1aktm1kaktm1

اما سئوالی که در این‌جا می‌خواهیم مطرح کنیم این است که آیا توانی که قضیه اولر به ما ارائه می‌دهد، کوچک‌ترین این tها است؟

به‌عبارت دیگر آیا t=φm کوچک‌ترین عدد طبیعی است که at  m1؟

پاسخ این سئوال منفی است کافی است به تمرین زیر توجه کنیم.

تمرین

نشان دهید:

54131

5213  15413  1


در صورتی‌که بنا به قضیه اولر یافتن کوچک‌ترین عددی مانند k به‌طوری‌که akm1 اهمیت بسیاری دارد، از این رو برای چنین توان‌هایی نامگذاری به‌خصوص داریم، که در مراحل بعد به آن می‌پردازیم.

تذکر

دسته مخفف مانده به پیمانه m

می‌دانیم مجموعه k=0,1,2,....,m1 یک دسته کامل مانده به پیمانه است.

اکنون اگر عناصری از مجموعه k مانند ai را چنان اختیار کنیم که ai,m=1 آن‌گاه مجموعه A=ai:ai,m=1 را دسته مخفف مانده به پیمانه m می‌نامند. 

به‌عنوان نمونه برای m=8 دسته مخفف مانده به پیمانه 8 عبارت است از: 

A=1,3,5,7

قضیه فرما

همان‌طور که قبلا ملاحظه کردید، یکی از مشکلات ما برای یافتن باقیمانده تقسیم اعداد به‌صورت an بر m یافتن عدد طبیعی مانند t است به‌طوری‌که:

atm1

این قضیه:

  • اولا وجود چنین عددی را در مورد پیمانه‌های اول، ثابت می‌کند.
  • ثانیا این توان را مشخص می‌کند. 

اما قبلا لازم است به نکات زیر در مورد عدد اول p توجه کنید.

نکته

1- اگر p یک عدد اول باشد، در این‌صورت داریم:

if   p,a=1p|a


2- اگر p یک عدد اول باشد، به‌طوری‌که a مضرب p باشد، در این‌صورت:

if  ap0nΝ    ;    paanp0


3- عدد اول p با هر یک از اعداد p1  ,.....,2,1 اول است، لذا با حاصل ضربشان نیز اول است.


4- مجموعه A=0,1,....,p1 یک دسته کامل مانده ها به پیمانه عدد اول p است و اگر a عدد صحیحی‌ای باشد، به‌طوری‌که p|a در این‌صورت مجموعه زیر نیز یک دسته کامل مانده‌ها به پیمانه m است. 

0,a,2a,....,ap1

قضیه

قضیه فرما (حالت خاص قضیه اولر)

اگر p عددی اول و a عددی صحیح باشد به‌طوری‌که p,a=1 آن‌گاه: 

ap1p1

اثبات

روش اول-

می‌دانیم مجموعه زیر یک دسته کامل مانده‌ها به پیمانه p است:

A=0,1,2,.....,p1

چون a مضرب p نیست یعنی a,p=1 لذا مجموعه زیر هم یک دسته کامل مانده ها به پیمانه m است. 

B=0,a,2a,.....p1a

اگر صفر را از دو مجموعه کنار بگذاریم، خواهیم داشت:

a.2a....p1.ap1×2×...×p1p1!  ap1pp1!ap1p1


روش دوم- با استفاده از قضیه اولر داریم:

φp=p11pφp=p×p1pφp=p1    ;   φmm1ap1  p  1

نکته

1- اگر p عددی اول باشد و a عددی صحیحی باشد، آن‌گاه app  a.

a,p=1p|aap1p  1ap1×a  p  1×aapp  a


2- قضیه فرما a,p=1ap1p1 به‌صورت زیر بیان می‌شود:

اگر p عدد اول و a مضرب p نباشد، آن‌گاه ap11 بر p بخش پذیر است.

نتیجه قضیه فرما a,p=1app  a به‌صورت زیر بیان می‌شود:

اگر p عدد اول و a مضرب p نباشد، آن‌گاه apa بر p بخش پذیر است.

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

a3-a بر 3 بخش پذبر است اما اگر a مضرب 3 نباشد، a2-1 بر 3 بخش پذبر است.  

a5-a بر 5 بخش پذبر است اما اگر a مضرب 5 نباشد، a4-1 بر 5 بخش پذبر است.  

و نظایر آن.

قضیه ویلسون

ابتدا لازم است وارون یک عضو به پیمانه m را تعریف کنیم.

عدد صحیح b به پیمانه m وارون a است، هرگاه abm1 در این‌صورت a را وارون پذیر گویند و می‌نویسیم:

if  abm1a1mb

اگر پیمانه m معلوم باشد، آن‌گاه a=b-1 یا a-1=b

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

7×213171=2    21=7

تذکر

اگر p اول باشد در این‌صورت هر یک از اعداد p1,......,3,2,1 وارون پذیرند.

تمرین

قبل از اثبات قضیه ویلسون نشان دهید:

12!131

12!=1×2×.....×12=1×2×7.3×9.4×10.5×8.6×11×12


نشان می‌دهیم وارون عناصر مجموعه 2,3,.....,11 عضوی از این مجموعه است، دو عضو 1,12 را در نظر نگرفته‌ایم. 

2×7  13  121=7    ;    71=23×9  13  131=9    ;    91=34×1013141=10    ;    01=45×8    13151=8    ;    5=816×11  13161=11    ;    11=6


اگر اعداد از 1 تا 12 را به‌صورت زیر دسته‌بندی کنیم، خواهیم داشت:

12!=1×2×.....×1212!=1×2×7.3×9.4×10.5×8.6×11×1212!131212!131


روش مشابه مسئله فوق قضیه ویلسون را ثابت می‌کنیم. 

دریافت مثال

قضیه

قضیه ویلسون

اگر p یک عدد اول باشد، آن‌گاه:

p1!p1

اثبات

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

2×3×....×p2

می‌بینیم هر عنصر از مجموعه 1,2,.....,p1 مانند a چون a,p=1 دارای وارون حسابی است یعنی: 

a1,....,p1    a11,...,p1    ;    aa1p1

در حالت خاص که a=a1 خواهیم داشت:

a2p1a21=kppa21pa1a+1pa+1ap1pp1pa1ap1

اکنون اگر عناصر p1,1 را از مجموعه 1,2,....,p1 کنار بگذاریم p-3 عدد به‌صورت 2,3,....p2 باقی ماند که آنها را می‌توان به p-32 زوج عدد دسته‌بندی کرد به‌طوری‌که هر دوتای آنها عکس حسابی یکدیگر باشند. 

بنابراین:

2×3×...p2p11×2×3×.....×p2p1pp1p1p1!p1

نکته

1- دیدیم که به پیمانه p فقط p1,1 با وارونشان مساوی هستند و این مطلب در مورد پیمانه‌های غیر اول ممکن است درست نباشد.

فرض کنید پیمانه m=12 باشد، در این‌صورت فقط اعداد 11,7,5,1 وارون دارند و واضح است که:  

11=1111=11

از طرف دیگر:

5×5=24+15×512151=57×7=48+17×712171=7

ملاحظه می‌کنید که به پیمانه 12 همه عناصری که وارون پذیرند، وارونشان با خودشان مساوی هستند.

بنابراین می‌توان گفت:

به پیمانه عدد اول p تنها اعدادی که وارونشان با خود اعداد مساوی است، عبارتند از p1,1 


2- عکس قضیه ویلسون نیز برقرار است.

اگر رابطه p1!p1 برقرار باشد، آن‌گاه p عدد اول است. 

تمرین

وارون 6,5,4,3,2 را به پیمانه 7 به‌دست ‌‌آورید.

2×47121=4    41=23×57131=5  51=36×67161=6

تمرین

ثابت کنید:

7×22!15231

p1!p122!=231!231  22!  2317×22!231×77×22!15237157×22!1523227×22!152322+237×22!15231

30!×293120

p1!p130!=311!31130!31130!×2311×230!×29312930!×293111+3130!×293120

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

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

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

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