Treść zadania

Najlepsze rozwiązanie

• 

  2 0

  antekL1 15.6.2011 (18:01)

  Znasz algorytm Euklidesa?
  Większą liczbę dzieli się przez mniejszą, zapisuje resztę z dzielenia.
  Teraz mniejsza liczba pełni rolę większej a ta reszta - rolę mniejszej.
  I ponownie dzielisz, aż podzieli się bez reszty.
  Wtedy ostatni użyty dzielnik to NWD.
  (Jak nie wyjdzie zero, to liczby są względnie pierwsze, czyli ich NWD to jedynka)
  Zróbmy to:
  
  1)
  2625 : 1323 = 1 reszty 1302. To teraz mniejsza liczba.
  1323 : 1302 = 1 reszty 21
  1302 : 21 = 62 reszty 0.
  Ostatnio użyty dzielnik to 21. NWD(1323,2625) = 21.
  Sprawdźmy:
  2625 = 21 * 5 * 5 * 5
  1323 = 21 * 7 * 3 * 3 - Nie ma nic większego wspólnego poza 21.
  
  2)
  2268 : 1485 = 1 reszty 783
  1485 : 783 = 1 reszty 702
  783 : 702 = 1 reszty 81
  702 : 81 = 8 reszty 54
  81 : 54 = 1 reszty 27
  54 : 27 = 2 reszty 0. Jest: NWD(2268,1485) = 27.
  Sprawdźmy:
  2268 = 27 * 7 * 3 * 2 * 2
  1485 = 27 * 11 * 5
  
  3)
  3675 : 1215 = 3 reszty 30
  1215 : 30 = 40 reszty 15
  30 : 15 = 2 reszty 0. Jest. NWD(1215,3675) =15.
  Sprawdzamy:
  1215 = 15 * 3 * 3 * 3 * 3
  3675 = 15 * 7 * 7 * 5

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie