В помощ на участниците в състезания и олимпиади по математика от 2-ри до 7-ми клас - за можещите и за по-малко талантливите, но упоритите .
dauchimmatematika.alle.bg

Сравнения .Малка теорема на Ферма . Задачи решими със сравнения .

1.Определение и свойства


Дефиниция .Нека  a  и b  са цели числа , а m   произволно естествено число . Казваме,че числото  a e  сравнимо с числото  b  по модул   m, ако числото m  дели   разликата a - b .

   Това   записваме така  : a ≡ b ( mod m)

Примери :

  1. 13 7( mod 2) , защото 2 / 13-7
  2.  7 13 ( mod 6) , защото 6/ 7-13 
  3. 231( mod 7) ,защото 7/ 23-1 
  4.  351( mod 11) , защото 11 / 35-1  ,  ( 35-1 =242 =11.22  )


Теорема Ако  a, b  ∈ Z   и  m∈  N    и  a ≡ b ( mod m)  , то   a   и  b имат равни остатъци  при деление с m             

Доказателство :Нека остатъкът при деление на  a  с  m  е   r1а  остатъкът при деление на  b  с  m   е  r2

Тогава са верни  равенствата   a = m.q  + r1    , b = m.s  + r2   и  0<r1 <m , 0<r2 <m  

От a ≡ b ( mod m)  ,следва,че    m  /  (a - b) , така е   m  / m.q  + r1- m.s  - r2  От това следва,че  m  /  r1  - r2  , откъдето следва ,че    r1  =  r2  


От теоремата , следва  че сравненията  притежават  основните свойства на  понятието делимост :                    

1 a   a  ( mod m) 

2.Ако  a b ( mod m)  ,то  и   b a  ( mod m) 

3. Ако  a b ( mod m)  и   b  c( mod m) , то   a c( mod m)                                                   

Пример :52 ≡  9(4)   и   9≡  1(4) , тогава   52 ≡   1(4)


Въвеждането на сравнения ще  ни  даде възможност да  използуваме  алгебрични методи при решаване на задачи от делимост .


Да  разгледаме следната  задача :

Докажете,че  236 – 1  се дели на  9 .

Това можем да докажем  ,като последователно прилагаме  формулите   за съкратено умножение и достигнем до множител кратен на 9  . С познаване на  свойствата на   сравненията , ще можем по-бързо да достигнем до търсеното доказателство  ,като  докажем,че   236    (mod 9) .

 Затова ще  разгледаме основни базови свойства на сравненията произтичащи от самото определение .

      

                                 Основни  свойства  на  сравнения   с  един и същ модул   :


1.Ако    a b ( mod m)      и    c d ( mod m)  ,  то    a + c  b +  c( mod m)  

Сравненията  с един и същ модул могат да се събират или изваждат


Доказателство : От  a b ( mod m)   ,по определение следва ,че   m / a b   .От  c d ( mod m)   , по определение следва ,че   m / c - d  .От свойствата на делимостта следва,че   m дели  сбора и тяхната   разлика .


2.Ако    a +  b c ( mod m)     , то   a  ≡c   b ( mod m)       

Във всяко сравнение  можем да прехвърляме  число   с  противоположен знак


3.Ако    a b ( mod m)      и    c d ( mod m)  ,  то    a . c b .d  ( mod m)  

Сравненията  с един и същ модул могат да се умножават .


Ако приложим това свойство неколкократно ще получим,че ако a b ( mod m)   и  k > 0   , то     

  ak bk  ( mod m) 

Сравненията  с един и същ модул могат да се  степенуват 



4.Ако    a b ( mod m)  и k  е произволно цяло число   ,то  akbk ( mod m)   

Сравненията  с един и същ модул могат да се  умножават с едно и също  число


5.Нека    a .kb. k ( mod m)   и   (k,m)=1  , тогава  a b ( mod m)  

Сравненията  с един и същ модул могат да се  разделят    с  техен общ делител    k , ако  (k,m)=1 

 

6.Нека    a b( mod m)   ,то  тогава  a b+m.t ( mod m)  за всяко t  цяло число .

Ако  a  е  сравнимо  с   b   , то a  е сравнимо със   сбора на b  с  всяко число кратно на  модула  m


7. Aко  ab(mod m) и f(x) е полином с цели коефициенти, то f (a)f (b) (mod m)


                                              Свойства  на  сравнения   с  различни  модули   

1.Ако  a b ( mod m)  и  d е  делител  на  m  , то  a    b ( mod d 

Ако  a е  сравнмо  с   b  по модул m ,то    a  е  сравнмо с   b   по всеки естествен делител d на m


2.Ако   a b ( mod m)        , то   ak  ≡ bk ( mod mk)                                             

 Доказателство:От a b ( mod m)   ,следва,че    m / a b  Тогава съществува  t цяло число ,такова че   a b  = m .t .От това следва ,че  за  всяко k цяло число е изпълнено    ak bk  = m .t.k  ,откъдето  следва ,че   ak  ≡ bk ( mod mk)

                                         

3.Ако    a b ( mod m)      и    d=(  a   ,b  m ) , то    то    a:d    b:d ( mod m:d


4.Ако a b (mod m1) и a b ( mod m2) , то a b ( mod m )

 където m= НОД(m1 m2 )                                         

 Докажете самостоятелно  останалите   свойства   и направете теста по долу .

     

 Тест : Свойства на

сравненията 

 

  Въпрос :

 

Отговор: 

1.Ако 12 b ( mod 3)     

то   48 ? ( mod 3)     

48 4b ( mod 3)     

2. Ако x2 - 1 ( mod 5)     

то  7x2 ?  ( mod 5)     

 7x2 -2  ( mod 5)     

3. Ако 52 -1(mod 13)     

то  ,550 ? ( mod 13)     

550 -1 ( mod 13)     

4. Ако 102 33( mod 23)  

то  34 ? ( mod 23)     

34 11 ( mod 23)     

5. Ако 30 50( mod10.) 

то ,6 10 ( mod? )

6 10 ( mod 2  )

6. Ако a b ( mod 2)  и,     

то , а ? ( mod 2 )

a  1 ( mod 2 )

b 2a+1  ( mod 2

 

 

7. Ако x2 -1 ( mod 5)  и     

то ,x2- 4x +3 ?( mod 5) 

x2- 4x +3 1( mod 5) 

 4x 1  ( mod 5) 

 

 

1
1
1


 Често използвано свойство при решаване на задачи е степенуване на  сравнения .


Пример 1: Да се докаже,че 236  1 (mod 9), така е ,че 9/  236  - 1

Изходно сравнение :   23  ≡  - 1 (mod 9)                                                                           

Тогава при повдигане на   двете страни на степен 12  ,  получаваме   сравнението                                                 

      236  1 (mod 9)                                                                            

Забележка :При  повдигане  на нечетна степен , примерно 11 , то получаваме  сравнението                                        

233  ≡  - 1 (mod 9) , така е 9/  233   1                                                                        


Пример 2. Да се докаже,че 380   1 (mod 10),                                                                

Търсим  подходящо изходно  сравнение , в случая    34  ≡  1 (mod 10)                          

Тогава при повдигане на   двете страни на степен  20 ,получаваме   сравнението   380   1(mod 10) 


 Пример 3 .Намерете последната цифра на числото   380   + 6100                                            

 Знаем ,че  380   1(mod 10)  , така е последната цифра е 1 , остава да определим последната  цифра на  6100   .От това ,че  всяко число което  завършва на 6 ,повдигнато на произволна степен отново завършва на 6 , то следва,че  660 6(mod 10)                                                                                                                          

 От 380   1(mod 10) и  660 6(mod 10) , то   380 + 660   1+6 (mod 10) (от свойството за събиране на сравнения с еднакви модули ) Тогава последната цифра на  380 + 660   е 7  



Пример 4 . Да се докаже,че 2 150 -1  се дели на 341                                               

 От това ,че   341=11.31   и    (11.31)=1, ще докажем,че 2 150 1 ( mod 11) и  2 150 1 ( mod 31)       

От  2   -1 ( mod 11) , то следва ,че    2150    1 ( mod 11)          

От  2   1 ( mod 31) , то следва ,че    2150    1 ( mod 31)  

Следователно        341 /  150 -1                                  

                                          

                                               Основно понятие в сравненията е  понятието модул .

Да разгледаме  множеството на  целите числа  в зависимост  от остатъка им при деление с   естественото число m .

 При деление с m ,множеството на целите числа се разбива  точно на  m  класа ,  това са   остатъците  при деление на всяко цяло число с m  ,  - {0,1,2,3,......, m-1 }  като :

  • ·        всяко цяло число принадлежи на точно един клас по модул  m   
  • ·        различните класове нямат общи елементи;
  • ·        обединението на класовете съвпада със Z.

Казваме,че всички класове образуват пълна система от  остатъци  по  модул  m .



Пример : При  деление на 3 възможните остатъци  са 0 , 1 или 2  Тогава по модул 3 ,целите числа са точно три класа  :3k , 3k+1 , 3k+2 .



Целта на  следващите   задачи е да усвоите  техники за бързо откриване на базови сравнения при степени  ,чрез определяне  на класа  в който попада дадено число  при даден   модул.



Пример :Нека  y е естествено число  .Намерете  възможните остатъци  при деление  на  7y   с  4  . 

За да определим  остатъците , разбиваме всички естествени  числа  y  на   четири непресичащи се класа ,в зависимост от възможните им  остатъци  при деление с 4 , така както е показано в таблицата .                      

  Разгледайте таблицата :

Базово сравнение

7 1( mod 4) 

Изходно  сравнение 

Делимост     

Ако  y=4k

  74k 1( mod 4) 

4/ 74k – 1

Ако  y=4k+1

  74k+1 7( mod 4) ≡3( mod 4) 

4/ 74k+1 – 3

Ако  y=4k+2

  74k+2 72( mod 4) 1( mod 4) 

4/ 74k+2 – 1

Ако  y=4k+3

74k+3 73( mod 4) ≡3( mod 4) 

4/ 74k+3 – 3

 

               Изводи:

 

 

 

 

 

 

 

1.Всички естествени числа   ,които  са  степени  на 7  при деление с 4  се разделят на два класа :

1.1  Ако   y=4k  или    y=4k+2 , то остатъкът при деление на степента  с 4 е 1

1.2  Ако   y=4k+1  или    y=4k+3  , то остатъкът при деление на степента  с 4 е 3



Задача Намерете всички числа  s за  които  4 / 7s   - 3  



Задача Докажете,че  77002  - 1   се дели на 4

Решение От това,че  7002 =175.4 +2 , то следва,че  77002 72( mod 4) ≡1( mod 4) , така , 4/ 77002 – 1




Задача  :Нека  y е  естествено число  .Намерете  възможните остатъци  при деление  на  3y   с  5  .
Отговор : -1,1,2 или 3






2.Задачи решими с основните свойства на сравненията



Задача Намерете остатъка от деленето:  23100  със  12                                  Решение                                                                                                                  

От това, че (3,4)=1 , то ще търсим остатъците по модул 3 и модул 4                                

 От 23 -1 ( mod 3), то 23100 1 ( mod 3),                                                                                                         

  От 23 -1  ( mod 4), то 23100 1 ( mod 4),                                                                         

Тогава   23100 1 ( mod 12),      





Задача Намерете  остатъка от деление на  878776  с  числото  3 .                            Решение                                                                                                                     

От това,че остатъка от деление на  878  със 3 е равен на остатъка от делението на сбора от цифрите му , то следва,че  8788+7+8 (3), така е базовото сравнение е 87823(mod 3) 2(mod 3).                                                                                                   

 Задачата свеждаме , до  сравнението 8787762776(mod 3),                                                

От 24  1 ( mod 3  ) то,     24.194  1 ( mod 3  ) ,то 2766  1 ( mod 3  ) то, 878776 1 ( mod 3  ) то ,търсеният остатък е 1



Задача Намерете  последната цифра на числото   108108   -  3111 – 2206

·         Базово сравнение   84  6( mod 10)    ,  84.27  627( mod 10) 6( mod 10) 

·          Базово сравнение   33  -1 ( mod 10)  ,   3111  (-1)37  ( mod 10) -1( mod 10)    

·          Базово сравнение   25  2( mod 10) то,250  210( mod 10) 4 ( mod 10)                                  

От  250   ≡4 ( mod 10 )  то,  2100   ≡42 ( mod 10 ) 6 ( mod 10 )                                                

 От  23  -2( mod 10)  и  2100    6 ( mod 10 ) , 2103    -12 ( mod 10 ) 

то, 2103    -2 ( mod 10 ) то, 2206    4( mod 10 )

Следователно  108108   -  3111 – 2206  { 6-(-1)- 4}  ( mod 10 ) 3 ( mod 10 




Задача Докажете,че числото 20n + 37 се дели на  19  за  всяко n                         

Решение                                                                                                                                                                        

От  базовото  сравнение 20 1 ( mod 19),следва ,че   20n 1 ( mod 19), за всяко n                                                        

 От 37 -1 ( mod 19),следва,че 20n + 37  0 ( mod 19),

 






Задача :
:Нека  y  е  цяло число , различно от нула .
Намерете  възможните остатъци  при деление  на  2y4   - 3  с 10   .

От това ,че   y2 може да завършва на 0,1,4,5,6 или 9 ,то                                                                                               
 y4 може да завършва на 0,1,5 или  6

Тогава  2y4 може да завършва на 0 или  2,

Тогава   2y4 -3   ≡-3  ( mod 10) 7  ( mod 10)  

или        2y4 -3   ≡-1  ( mod 10) 9  ( mod 10)

Следователно  числото   2y4   - 3  при  деление   с 10  има два  възможни остатъка 7 или 9




Задача Намерете  всички числа  x  за които    100/  7x4  - 300x  -  100                                                                

  Отговор :  x =10 t                                                                                                                                                                            





Задача Намерете остатъка от делението на    A= 7 + 72 +73  + 74 +....+7103   с числото 4

         От таблицата която разгледахме в началото , следва , че всички възможни остатъци са  1 или  3

Базово сравнение

7 1( mod 4) 

Изходно  сравнение 

Делимост    

Ако  y=4k

  74k 1( mod 4) 

4/ 74k – 1

Ако  y=4k+1

  74k+1 7( mod 4) ≡3( mod 4) 

4/ 74k+1 – 3

Ако  y=4k+2

  74k+2 72( mod 4) ≡1( mod 4) 

4/ 74k+2 – 1

Ако  y=4k+3

74k+3 73( mod 4) ≡3( mod 4) 

4/ 74k+3 – 3

 

              

 

 

 

 

 

 


Тогава  изразът   74 +....+7103  има  сбор  от  остатъците -   на  25 места  с  остатъци  равни на  .(1+3+1+3).

Тогава  74 +....+7103    25.8 ( mod 4)  0 ( mod 4) 

 Следователно остатъкът на  A  ще зависи  от остатъка от делението на 7 + 72 +73  с 4 и той е 3



                                    Задачи  за самостоятелна работа


  Задача  Намерете най-малкото не отрицателно  x , за  което  

a) x   9 ( mod 13),

b) x2 9 ( mod 13),


 Задача Докажете,че   с   5/320001  -  3  

                                                                        

 Задача Докажете,че числото 74000 +  99 се дели на 100 


Задача Намерете  последната цифра на числото   1239320  - 567321 


Задача Докажете,че   числото   5/2101  +  8    

                                                                      

Задача Намерете остатъка от делението  на  61001  с 11


Упътване : 61001 =21001 .31001 


Задача Докажете,че числото 732  - 1 се дели на  6,15 и 48 


 Упътване :  732  - 1 =(716  - 1) .(716  + 1) =(78  - 1) (78  + 1)  .(716  + 1)


Задача Докажете,че  не съществува число естествено число  n , такова ,че  x2 =3n+2

Упътване :Нека x=3k ,x=3k+1  и  x=3k+2 .Покажете,че и в трите случая ,лявата и дясната страна на равенството дават различни остатъци по модул 3


Задача  Да се докаже,че  числото  C=   910 – 220   се дели на  5



Задача Намерете остатъка от делението на    A= 9 - 92 +93  - 94 +....+9103   с 10

 

3.Решаване на сравнения от първа степен с едно неизвестно .Алгоритъм на Ойлер

Задачата  да се  реши  сравнението  ax   b(mod m) се  свежда до  намирането на решенията  на  линейното   диофантово уравнение  ax -b = my .

Решението на  уравнението  ax+ by= c   с  алгоритъма  на Ойлер , ще намерите   на  посочената връзка по-долу .
1
1
1

4.Малка теорема на Ферма Задачи от делимост на числата .

Да разгледаме задачата :Да се намерят всички цели  x , за  които  xn x  (mod n). Всъщност задачата изисква да се намери  общ метод  за решаване  на цели класове от задачи :                                                                                                   

x2x(mod 2)             

 x3x(mod 3).                                                                                                                             

 x4x(mod 4).                                                                                                                         

 x5x(mod 5).                                                                                                                           

  ----------------------                                                                                                                      

   x n x(mod n).                           

                                        Да разгледаме  някои от сравненията :


1)x3x(mod 3).   Тогава  сравнението е вярно  за  всяко цяло число   x , защото                                                           

3/ x3 x  =  x ( x 1)(  x +1 ) , така е :между всеки три последователни числа ,точно едно е кратно на три .


2)   x4x(mod 4). Нека x=3 ,тогава 81 не е сравнимо с  3 по модул 4 .Следователно сравнението ,не винаги е вярно .


3) x5x(mod 5). Ще покажем,че    5/ x5 x  за всяко x 

От  x5 x  = x (  x 1)(  x +1)( x2+x )   следва,че  винаги  съществува клас  от вида  x = 5k x или x = 5k+1  или   x = 5k-1 или   x = 5k+2 или    x = 5k-2   за който 5 да дели  един от множителите .Тогава   сравнението   x5 x(mod 5) е вярно за всяко  x


От разгледаните примери  следва ,че  сравнението x n≡ x(mod n)  не винаги е вярно  .В по-горните класове  ще разгледате  функция на Ойлер ,чрез  която се  дават необходими и достатъчни условия за  да има решение сравнението    

x n≡ x(mod n). 

Ние ще  разгледаме един частен случай  ,тогава когато   n e просто число                   


Едно известно сравнение  носи името на Ферма .В математическата литература  се нарича малка теорема  на  Ферма .Тя е следствие  от  известна теорема на Ойлер.


Малка теорема на Ферма :.
Ако a  е  цяло число , а  p   просто число  , то  аpa(mod p).  
Следствие : Ако a  е  цяло число ,  p   просто число   и   а  не е кратно  на  p , то  аp-1 ≡1(mod p).  
      
        
История
Пиер Ферма формулирал тази теорема без доказателство , около 1636 година . В писмо от 18 октомври  1640 година от  Пиер Ферма  до  френският  математик Бернар Франиклин (Bernard Frénicle de Bessy) се  съдържало следното предположение : p дели a p -1 -1  в случая , когато  p се явява   просто  число и a не се дели на p. Това е  публикувано в посмъртно  издание  на неговите трудове през 1660 година  
       
                                        
 Доказателство :За тези от Вас, за които метода на математическата индукция  е известен , могат да разгледат  предложеното доказателство. 


От  малката теорема  на Ферма  ,следва че :

  • ·                    10003 − 1000  се дели на 3.
  • ·                    (−13)71 − (−13)   се дели на 71.
  • ·                    4107 − 4  се дели на 107.


                      Приложение на малката теорема на Ферма  при решаване  на задачи  от делимост .


Задача  Намерете остатъкът от делението на  5102  с  101  

Решение:От това,че  101 е просто число и  (101,5)=1  , то 5¹ºº ≡ 1 (mod 101). Откъдето   5¹º² ≡ 25  (mod 101).



Задача Докажете,че ако  (a, 11) = 1 , то 11 / a200  − 1, за всяко цяло число a .

Доказателство : От малката теорема на Ферма , следва,че  a 10 ≡1( mod 11) От свойствата на сравненията , следва ,че  a 10.20 ≡1( mod 11)



Задача  Докажете,че ако   целите числа   a  и  b не   се  делят   на   3 и 5  , то    a4000 + b4000  - 2    се дели на  15 



Задача Докажете, че  5006000 – 1 се дели   на 1001                                                    

Решение:  От това,че  1001  не е  просто число  и  1001=   7. 11.13 , то:                                                                             

От малката  теорема на Ферма , 5006 ≡ 1(mod 7), откъдето  5006.1000 ≡ 1(mod 7),                                                                     

От малката  теорема на Ферма , 50010 ≡ 1(mod 11), откъдето  5006.1000 ≡ 1(mod 11),                                                                  

От малката  теорема на Ферма , 50012 ≡ 1(mod 13), откъдето  5006.1000 ≡ 1(mod 13), 

 Тогава от това,че (7,11,13)=1 ,то следва, че  7.11.13  / 5006000 – 1                                                                                                                                                                                                                                                                                                                                                                                                   

                 

Малката теорема на Ферма , не твърди  ,че не съществуват  съставни числа  q , такива ,че ,ако ( q , a) =1 , то q  не дели  aq-1 -1                                                                  

Ф. Саррус в 1820 година  намерил  числото 341 ,което е съставно и за което  2 341-1  -1  се дели на 341.

Докажете  това твърдение .

                


Задача Докажете ,че ако  (a, 7) = 1 ,  то  7 /  a6 a42  + 12  за всяко цяло число  a 


  


Задача Нека  p  е просто число .Докажете,че ако a не е кратно  на p , то числото    ap-1 + p − 1 е съставно .

Доказателство:

От малката теорема на Ферма ,следва ,че  ap-1≡1( mod p) , така е  p/ ap-1- 1, но p/ p тогава  p  дели тяхният сбор .Така е  p/ ap-1+p – 1 Тогава съществува цяло число  k >1 такова ,че 

ap-1+p – 1=k.p.Следователно числото ap-1+p – 1 е съставно .





Задача Докажете,че за всяко просто число p , което не е кратно на 2 и 5  може да се намери естествено  число N, което е   записано  само с  четен брой  девятки  и  което  се  дели   на  p

 

Доказателство :Нека p е произволно  просто число различно от 5 и 2 .Тогава от малката теорема на Ферма  следва,че   10p10 (mod  p) Това означава ,че p/10p-10

Тогава    p/10(10p-1-1) От това,че (p,10)=1 , то следва ,че  , p/10p-1-1  

Получихме,че за всяко просто число p  различно от 2 и 5   можем да намерим число  от вида  10p-1-1  , което е съставено само от ‘четен брой  девятки и което се дели  на  p .

 

Пример:Нека  p =7 , тогава 7 /106-1  = 999999 





Задача .Докажете ,че  за съставното число  561 и цялото   число a,  за които  (a, 561) = 1,  е вярно ,че  a560  1(mod 561). 


Числа, които  притежават  това свойство се наричат числа на   Робърт Кармайкъл , който  през 1910 година открива  ,най-малкото такова число – 561


Доказателство :

561 = 3.11.167  където  3 ,11 и 167 са прости числа                                          

От  това,че a e цяло число , такова ,че:(a, 561) = 1,то е вярно ,че (a, 3) = 1,(a, 11 ) = 1 и (a, 167 ) = 1

 

От  (a, 3) = 1 и 3 просто число ,то , a 2 ≡ 1(mod 3), откъдето  a2.280 ≡ 1(mod 3 ),

От  (a, 11) = 1 и 11 просто число ,то , a 10 ≡ 1(mod 3), откъдето  a10.56 ≡ 1(mod 11 ),

От  (a, 167) = 1 и  167   просто число ,то , a 160 ≡ 1(mod 3), откъдето  a160.4 ≡ 1(mod 3 ),

 

Първите  няколко числа  на Робърт  Карлмайкъл са561, 1105, 1729, 2465.........



Задача .Докажете, че числото  A  =  607999 + 799960  е   съставно.

Упътване :Докажете ,че числото   A се дели на  61




Задача .Нека   p е просто число. Докажете, че  (a + b)p ≡ ap + bp (mod p) за всеки две произволни цели числа  a и b.     

Доказателство :

От  малката теорема на Ферма  следва ,че : a p ≡ a  (mod p).  и   bp ≡  b(mod p). 

Тогава   a + b ≡ ap + bp (mod p).

От друга страна отново от малката теорема на Ферма  следва,че   (a + b)p ≡ (a + b)  (mod p)

.От релацията  транзитивност на сравненията ,следва  че   (a + b)p = ap + bp (mod p) за всеки две  произволни цели числа a  и  b



Задача  Докажете,че ако  сумата  на   целите числа   a, b и c  се  дели  на   30 , то  и   a5 + b5 + c5  също  се дели на  30.

Доказателство :

От малката теорема на Ферма , следва ,че  за всяко цяло x  ,   x5 ≡ x (mod 5).

От свойствата на делимостта  следва,че x5 ≡ x (mod 6),защото  6 / x ( x – 1) (x + 1) (  x2  + 1)  

От това,че  (5,6) са взаимно прости , то  за всяко  цяло  x  ще е вярно,че   x5 ≡ x (mod 30).

Това ще е вярно за всяко  от целите числа   a,   b  и  c .Така е ,ще е изпълнено  a5 ≡ a (mod 30)., b5 ≡  b(mod 30)., c5 ≡  c(mod 30).откъдето следва,че a5+b5  +c5≡ a  + b+   c(mod 30). ≡ 0 (mod 30).  

 



Задача   Нека p  и q са  различни   прости  числа. Докажете, че   pq + qp– p – q   се  дели на   p.q  

Решение  :

От малката теорема на Ферма  следва,че   pq  ≡ p ( mod q ) . Тогава  q / pq  -   p                                                                      

От това ,че p / pq  -p  и  p и q са  различни   прости  числа , то следва,че p. q   / pq - p                                    

Аналогично доказваме,че   p. q   / q p – q Тогава    p. q    дели сбора  pq + qp– p – q   




Задача Нека   n  е  естествено  число, което  не е кратно на 17. Докажете , че  едно от  числата   n8 + 1 и    n8 – 1  се  дели  на 17.



Задача  Докажете,че  за всяко цяло число a , то  a11 - a  се  дели  на 66;     

 



Задача  Докажете,че  за всяко цяло число a , то  a17 - a  се  дели  на 510 ;        

 




Задача Да се докаже,че 2y -5 не се дели на 17

От  това ,че  (2,17)=1 ,от  малката теорема на Ферма, следва ,че   216 1( mod 17) 

Откъдето следва,че   17 / (216 1) = (28 1) .(28 +1) .Тогава   28 1( mod 17) 

Това ни подсказва,че можем да  разбием всички естествени  числа  y на 8 класа според остатъците им при деление на  8  и  от базовото  сравнение 28 1( mod 17)  открием  възможните остатъци  при деление на  2y със 17

Базово сравнение

2 1( mod 17) 

Изходно  сравнение 

Делимост    

Ако  y=8k

  28k 1( mod 17) 

17/  28k -1

Ако  y=8k+1

  28k+1 2( mod 17)  

17/ 28k+1 -2

Ако  y=8k+2

  28k+2 22( mod 17) ≡4( mod 17) 

17/ 28k+3 -  4

Ако  y=8k+3

  28k+3 23( mod 17) ≡8( mod 17) 

17 / 28k+3 -  8

Ако  y=8k+4

  28k+4 24( mod 17) ≡16( mod 17)    

17 /28k+4 - 16

Ако  y=8k+5

  28k+5 25( mod 17) ≡15( mod 17) 

17 /28k+5 -15

Ако  y=8k+6

  28k+6 26( mod 17) ≡13( mod 17) 

17 /28k+6 - 13

Ако  y=8k+7

  28k+7 27( mod 17) ≡9( mod 17) 

17 /28k+7 -  9

  

Извод :Не съществува клас  


при   който 17/ 2y -  5





Задача Намерете  всички  естествени  числа  y  ,такива  , че   11  / 2y -7  

Упътване :От  базовото  сравнение 210 1( mod 11)  намерете  остатъците при деление на  y  с 11  и намерете търсените числа  y .




Задача   Докажете,че уравнението  x4   + 25 =  3y  няма решение в цели числа .                           Решение 

От това,че 3y -25 е четно число за всяко  y , то x4 е четно число .Следователно  x е четно .

Тогава Тогава  x4   0 ( mod 10), или  x4   6 ( mod 10),

Ако  x4   0 ( mod 10 )   , то за да съществува решение  трябва  3y -25   0( mod 10),така е 3y   5( mod 10),  Ще докажем,че това не е възможно .Разбиваме целите  числа  y   на 4 множества ,в зависимост от остатъците им при деление с 4 .Ще покажем,че за всеки клас  3y  не е сравнимо с  5 ( mod 10),  

 

Базово сравнение 34 1 ( mod 10),

 

y= 4k

34k 1 ( mod 10),

 

y= 4k+1

34k+1 3( mod 10),

 

y= 4k+2

34k+2 9 ( mod 10),

 

y= 4k+3

34k+3  27 ( mod 10) 7 ( mod 10),

 

Получихме,че  ако  x4   0 ( mod 10 ) , то уравнението няма решение в цели числа   

   Ако  x4   6 ( mod 10 )   то за да съществува решение  трябва  3y -25   6( mod 10),така е 3y   31 ( mod 10) 1  ( mod 10 )   

Ще докажем,че това не е възможно .Допускаме, че това е възможно . Нека отново разбием числата  y   по модул 4 .Тогава само ако  y= 4k , то 3y    1  ( mod 10 )    и е изпълнено   x4   + 25 =  34k                                             

От x четно , то x= 2z и уравнението е еквивалентно на  16z4   + 25 =  34k      

Следователно     34k    - 16z4 =52  Тогава     (3k - 2z) (3k + 2z) =52      

От     (3k - 2z) < (3k + 2z)  ако  z >0 , то следва ,че  3k - 2z   =1 и   3k + 2z   =25                     

 или  3k - 2z   =-25  и  3k + 2z  =-1 .За получените две системи,получаваме ,че не съществува точно трета степен равна на  13  или  -13 .

 Аналогично от  (3k - 2z) >  (3k + 2z)  ако  z < 0, получаваме, че уравнението няма решение в цели числа .                                                   

 Ако  (3k 2z) = (3k 2z) ,  то  z   = 0 , но      34k   е различно от  52   и уравнението  няма решение в цели числа . 

Източници :
В момента разглеждате олекотената мобилна версия на сайта. Към пълната версия.
Уебсайт в alle.bg