6161619777

TEORIA LICZB

Niech a i b będą liczbami całkowitymi (a, b e $).

Mówi się, że a dzieli b (a jest dzielnikiem b, a jest czynnikiem b), jeżeli istnieje taka liczba całkowita c, że b = ac, co oznacza się symbolem a I b.

Dla wszystkich a, b, c e ^zachodzi:

•    a I a

•    a\bAb\c=>a\c

•    a\bAa\c=>Vx, y £ $: a\ (bx + cy)

•    a I b Ab I a =pa = +b

Jeżeli a, b £ % , a ponadto b > 1, to zwyczajne dzielenie a przez b, oznaczane jako a / b, daje w rezultacie iloraz q oraz resztę r takie, że:

a = qb + r, gdzie 0 < r <b,

ponadto zaś q i r są wyznaczone jednoznacznie.

Wprowadza się oznaczenia: r = a mod b oraz q = a div b.

a, b £ $ Ab =>a div b = \_a / b\ Aa mod b = a - b \_a / b\

a, b, c e % Ac\a Ac\b =>c jest wspólnym dzielnikiem a i b

Największym wspólnym dzielnikiem (greatest common dirisor) liczb całkowitych a i b jest nieujemna liczba całkowita d = gcd(a, b) taka,

że:

•    djest wspólnym dzielnikiem a i b

•    c I a ac I b =?c I d

(przyjmuje się, że gcd(0, 0) = 0).