Euklidov algoritam

#fax #math #ds1 [deo poglavlja "prirodni brojevi" i "celi brojevi"]

Teorema. Ako je , tada važi
(Napomena: euklidsko deljenje, NZD)

Algoritam


Primena teoreme odogo više puta dok ostatak neće postati 0:






Teorema. Poslednji nenula ostatak u Euklidovom algoritmu je jednak .

Dokaz:
Iz teoreme:

Poslednja jednčina:


Posledica.

Primer

Matrična metoda

Operacije:

  • T1: zamena mesta vrsta
  • T2: množenje vrsta sa -1
  • T3: dodavanje jedne vrste pomnožene celim brojem drugoj vrsti.

Matrica se dobija primenom T1, T2, T3

Teorema. Za važi

Teorema. Za važi


Primenom T1, T2, T3 iz matrice treba dobiti matricu oblika , tada je i
Primer