3360446508

Podstawowe własności liczb całkowitych 13

1.5.2.    Rozwiązując zadanie 1.5.1, można zauważyć, że algorytmu podanego we wstępie nie można zastosować, jeśli n < 0. Zmodyfikuj ten algorytm tak, aby można było go zastosować przy dzieleniu liczby całkowitej m przez liczbę całkowitą n < 0 .

1.5.3.    Uzasadnij, że jeżeli p, n £ N , to wśród wyrazów ciągu 1, 2 , 3 , ... , n jest wielokrotności liczby p .

1.5.4.    Znajdź najmniejsza liczbę naturalna n spełniającą wszystkie poniższe warunki:

-    reszta    z    dzielenia    n    przez 2    jest    równa    1,

-    reszta    z    dzielenia    n    przez 3    jest    równa    2,

-    reszta    z    dzielenia    n    przez 4    jest    równa    3,

-    reszta    z    dzielenia    n    przez 5    jest    równa    4.

1.6. Największy wspólny dzielnik. Niech m i n będą dwiema liczbami całkowitymi, przy czym m ^ 0 lub n^O. Liczbę całkowita d > 1 nazywamy największym wspólnym dzielnikiem liczb m i n (co oznaczamy NWD(m,n)), jeśli

(a)    d dzieli m i d dzieli n;

(b)    jeżeli liczba całkowita c dzieli m oraz n, to c dzieli d. Bezpośrednio z powyższej definicji wynika, że jeżeli m / 0, to

wtedy NWD(m, 0) = |m| . Weźmy teraz dwie liczby całkowite oraz n/0. Uzasadnimy, że z zasady minimum wynika istnienie NWD(m, n). W tym celu rozważmy zbiór

X = {xm + yn > 1 : x,y £ Z} .

Ponieważ m-m+n-n > 1, więc X ^ l. Z zasady minimum wynika, że w zbiorze X istnieje liczba najmniejsza. Niech d = am + bn będzie tą liczbą (a , b £ Z ). Zauważmy, że d\m oraz d\n . Istotnie, jeśli zapiszemy m = dq + r , gdzie 0 < r < d, wtedy mamy

r = m — dq = m — (am + bn)q = m( 1 — aq) + n(—bq).

Gdyby r > 1, to r £ X oraz r < d, co jest sprzeczne z wyborem d . Zatem r = 0, czyli d\m. Analogicznie uzasadniamy, że d\n. Tak więc d spełnia warunek (a) definicji NWD.