Algoritmo della divisione euclidea in $\mathbb Z$

Siano $a,b \in \mathbb Z$ con $b \neq 0$, allora $\exist ! q,r \in \mathbb Z: a=qb+r$ con $0 \le r < |b|$

Notazione: $rest(a,b) = r$

Proprietà:

• $rest(a,b) = rest(a,-b)$
• $rest(-a,b)=b-rest(a,b)$ se $rest(a,b)\neq0$, $=0$ se $rest(a,b)=0$

Divisori

Dato $a \in \mathbb Z$, $D(a) = \{x \in \mathbb Z|x|a \}$ è l’insieme dei divisori interi di $a$

Se $D(a)$ è finito, $|D(a) | \ge 4$ perchè $1,-1,a,-a$ dividono tutti $a$

Lemma: dati $x,y,z,k \in \mathbb Z$ tali che $x=yk+z$, si ha $D(x)\cap D(y) = D(z) \cap D(y)$

$p \in \mathbb Z$ è detto primo se $D(p)= \{1,-1,p,-p\}$ ($p \neq \pm 1$)

Massimo comune divisore

Dati $a,b \in \mathbb Z$, $a,b \neq 0$ il numero $d \in \mathbb Z$ è detto massimo comune divisore di $a$ e $b$ se:

• $d|a$ e $d|b$
• $\forall t \in Z, t|a$ e $t|b \Rightarrow t|d$

Lemma: dati $a,b \in \mathbb Z \backslash \{0\}$