Divisione euclidea in N e in Z

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Divisione euclidea in N e in Z #56006

avt
ciambellaro
Punto
Il teorema della divisione euclidea afferma: siano a,b\in\mathbb{N} con b\neq 0, allora esistono q,r\in\mathbb{N} tali che a=bq + r con 0<= r <b.

Per la definizione è tutto chiaro, ma come faccio a dimostrare che il seguente teorema è valido in \mathbb{N} e anche in \mathbb{Z}?
Non so proprio da dove partire emt in \mathbb{N} avevo pensato di usare il principio di induzione ma mi blocco nel dimostrare che la proposizione è valida per (n+1).

Grazie in anticipo! emt
 
 

Re: Divisione euclidea in N e in Z #56025

avt
Galois
Coamministratore
Ciao ciambellaro emt

Quello che citi è un Teorema famosissimo in Algebra noto, come hai ben detto, col nome di "Teorema delle divisione euclidea" hai però dimenticato una parte fondamentale della tesi. I numeri q ed r sono unici!

A rigor di cronaca l'enunciato completo è:

Siano a,b \in \mathbb{Z} e b \neq 0. Allora esiste un'unica coppia di interi:

q \in \mathbb{Z}, \ r \in \mathbb{N} \cup \{0\}

tali che:

\left\{ \begin{matrix} a=b \cdot q + r \\ 0\leq r < |b|\end{matrix}


__________

La dimostrazione è un "classico" dell'algebra ed è la seguente:

Si considera un insieme S definito in questo modo:

S=\{a-nb | n \in \mathbb{Z}, \ a-nb \geq 0\}

Osserviamo subito che tale insieme è non vuoto, infatti se n=a si ha:

a-nb=a(1-b)

mentre se n=-a

a-nb=a+ab=a(1+b)

ed essendo per ipotesi b \neq 0 uno fra i due è necessariamente maggiore di zero.


Essendo S non vuoto, per una proprietà nota col nome di "Principio del buon ordinamento", l'insieme S ammette minimo. Sia esso r, ovvero poniamo:

r:=min\{S\}

Essendo r il minimo dell'insieme per definizione di minimo esso vi apparterrà, pertanto esisterà un q \in \mathbb{Z} tale che:

r=a-qb

Inoltre essendo r il minimo di tale insieme: r < |b|, infatti se così non fosse, ovvero se:

r \geq |b| allora si avrebbe r':=(r-|b|) \geq 0

ed inoltre:

r'=r-|b|=a-qb-|b| = a - \left(q+\frac{|b|}{b}\right)b

che essendo della forma a-nb appartiene ad S, inoltre è più piccolo di r (in quanto si ottiene da r sottraendo un numero positivo) pertanto siam caduti in un assurdo. Ragion per cui, necessariamente r < |b|

Tutto questo prova la prima parte del Teorema.

Ora rimane da dimostrare l'unicità. E' abbastanza semplice. Basta supporre per assurdo che q ed r non sono unici e cercare di cadere in una contraddizione..

Lo lascio a te.. se hai dubbi sono qua emt


PS: l'enunciato e la dimostrazione data valgono per a,b \in \mathbb{Z} e quindi vale, in particolare, per a,b \in \mathbb{N}

emt
Ringraziano: Omega, Pi Greco, CarFaby
  • Pagina:
  • 1
Os