276061997

6 Podstawy teorii liczb

Przedstawienie NWD dwóch liczb za pomocą kombinacji liczb wyjściowych można oczywiście uzyskać "wracając” krok po kroku drogą wykonywanego algorytmu, ale jest to jednak dość żmudna operacja. Możemy uprościć sobie nieco tę procedurę wyrażając w każdym kroku powstałą resztę jako kombinację liczb a i b. Procedurę tę opiszemy na przykładzie:

Przykład 1.3.1. Chcemy wyliczyć NWD(720,546) oraz przedstawić je w postaci Bezouta, (tak nazywać będziemy poszukiwaną kombinację).

Wypiszmy, dla przejrzystości kolejne kroki w tabeli:

	720	546
720	1	0
546	0	1

Wiemy teraz, że 720 = 1 • 546 + 174, mnożymy więc drugi wiersz przez 1 i odejmujemy od pierwszego dostając:

	720	546
546	0	1
174	1	-1

Jak widać dostajemy przedstawienie reszty: 174 = l-720+(—1)-546 w postaci kombinacji wyjściowych liczb. Dalej powtarzamy procedurę zgodnie z algorytmem Euklidesa i wiemy, że 546 = 3 • 174 + 24. Ponownie więc mnożymy drugi wiersz ostatniej tabeli przez 3 i odejmujemy od pierwszego.

	720	546
174	1	-1
24	-3	4

skąd 24 = (-13) • 720 + 4 • 546. Kontynuujemy biorąc pod uwagę, że 174 = 7 • 24 + 6 i otrzymamy:

	720	546
24	-3	4
6	22	-29

Jak widać teraz już po wydzieleniu 24 przez 6 jako resztę otrzymamy zero, wobec tego NWD(720,546) = 6 i otrzymaliśmy też: 6 = 22 ■ 720 + (—29) • 546.

1.4 O liczbach pierwszych i ich własnościach

Zacznijmy od przypomnienia definicji liczby pierwszej - podstawowej "cegiełki” budującej liczbę całkowitą.

Definicja 1.4.1 (liczba pierwsza). Liczbę całkowitą p € Z nazywamy liczbą pierwszą, jeśli (1) p > 1 oraz (2) d\p, d > 0 => d = 1 lub d = p.

Zbiór wszystkich liczb pierwszych oznaczamy dalej przez P.