Treść zadania

Najlepsze rozwiązanie

• 

  1 0

  antekL1 23.10.2011 (11:34)

  Liczbę n^p można zapisać jako a * p + b
  Liczbę n można zapisać jako c * p + d
  gdzie a,b,c,d są całkowite.
  Należy udowodnić, że b = d, to znaczy reszty z dzielenia n^p oraz n przez 'p'
  są jednakowe. Jest to tzw. "małe twierdzenie Fermata" i istnieje indukcyjny dowód:
  
  1) dla n = 1 zachodzi 1^p - 1 = 0. Twierdzenie jest prawdziwe.
  
  2) Zakładam, że jest prawdziwe dla pewnego n. Stosuję poniżej taki zapis:
  
  n^p \equiv n
  
  na oznaczenie, że reszty z dzielenia przez p są jednakowe. Dowodzę dla n+1.
  
  (n+1)^p = n^p + 1 + \sum\limits_{k=1}^{p-1}{n \choose k}n^k
  
  Ale w dwumianie Newtona:
  
  {n \choose k} = \frac{p(p-1)\dots\(p-k+1)}{k!}
  
  dla 0 < k < p żaden z czynników w k! nie jest równy p. Ponieważ dwumian ten jest liczbą całkowitą (dowód w innym zadaniu) to musi być podzielny przez p, bo pierwsze p z licznika się nie skróci z mianownikiem.
  Wobec tego
  
  (n+1)^p \equiv n^p + 1 \equiv n + 1
  
  (ostatnia równość reszt z dzielenia wynika z założenia indukcyjnego).
  Wobec tego twierdzenie jest prawdziwe dla n + 1. Koniec dowodu.
  
  UWAGA: Gdyby p nie było liczbą pierwszą to mogłoby się częściowo skrócić z którymś elementem z k! i nieprawdą byłoby, że dwumian Newtona jest podzielny przez p.

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie