رتبه برتر کنکور..

کتاب آنلاین کنکور و کنکور ارشد

 
اعداد اول و تابع اویلر
نویسنده : مهندس ضیابری - ساعت ٩:٥٩ ‎ب.ظ روز ۱٧ فروردین ۱۳٩٠
 

چند عدد صحیح مثبت کوچکتر از 301 وجود دارد که نسبت به اعداد 75 و 60 اول باشند؟


ابتدا دو عدد 60 و 75 را تجزیه می کنیم

                                                    60 = 22*3*5  ,  75 = 3*52

از میان این سیصد عدد اعدادی که نباید بر 2 و 3 و 5 قابل قسمت باشند را می یابیم

تعداد اعدادی که بر 2 و 3 و 5 بخش پذیرند :

                          [300/2]=150  ,  [300/3]=100  ,  [300/5]=60

و تعداد اعدادی که بر 6,10,15,30 بخش پذیرند :

         [300/6]=50 , [300/10]=30 , [300/15]=20 , [300/30]=20

کل تعداد اعدادی که بر 2 یا 3 یا 5 بخش پذیرند

                            n' = 150+100+60 - 50 -30 - 20 +20 = 220

و در انتها تعداد اعدادی که نسبت به 75 و 60 اولند برابر است با

                                                              n = 300 - 220 = 80

 راه حل دوم

از آنجاییکه 300 نیز فقط بر اعداد اول 2 و 3 و 5 بخش پذیر است بنابراین طبق تابع حسابی اویلر تعداد اعداد کوچکتر از 300 که نسبت به آن اولند برابر است با

                    n = p(300) = 300(1 - 1/2)(1 - 1/3)(1 - 1/5) = 80