276062011

Rozdział 1

Podstawy teorii liczb 1.1 Podzielność w Z

Definicja 1.1.1 (podzielność w Z). Niech a, b G Z. Mówimy, że b dzieli a (lub inaczej b jest dzielnikiem a) gdy istnieje c € Z : a = bc.

Oznaczenie: b\a.

Uwaga 1.1.2 (własności podzielności w Z). Niech a, b, c, m, n - liczby całkowite. Wtedy:

(a)    l|a, o|0,

(b)    jeśli 0|a, to a = 0,

(c)    relacja podzielności na Z* jest zwrotna i przechodnia,

(d)    (6|a i a\b) wtedy i tylko wtedy, gdy |a| = |6|,

(e)    jeśli c|a, c\b, to c|(am + nb),

(f)    jeśli a\b i b / 0, to 1 ^ |a| ^ \b\.

Twierdzenie 1.1.3 (algorytm dzielenia z resztą). Niech a, b - liczby całkowite, 6^0. Wtedy istnieje para (q, r) € ZxZ:

(l)a — bq + r, (2)\r\<\b\.

Liczbę q nazywamy wynikiem dzielenia zaś r resztą z dzielenia.

Twierdzenie 1.1.4 (algorytm dzielenia z resztą - wersja B). Niech a, b - liczby całkowite, b 7^ 0. Wtedy:

(•) istnieje dokładnie jedna para (q, r) G Z x Z taka, że:

(1) a = bq + r, (2) 0 ^ r < |6|.

(•) jeśli dodatkowo b\a, to istnieją dokładnie dwie pary (q,r) takie, że (1) a = bq + r, (2)\r\<\b\.

Dowód. Udowodnimy pierwszą część twierdzenia 1.1.4 (wynika z niej natychmiast tw. 1.1.3). Istnienie reszty

Niech S {a —kb, k G Z, a-kb^O}- jest to niepusty podzbiór No, wobec tego ma on element najmniejszy,(??) który oznaczymy jako r. Element ten jest więc postaci r = a — qb dla pewnego q całkowitego i automatycznie spełnia nierówność: 0 ^ r oraz a = qb + r.

1