Esistenza e unicitร  della divisione euclidea

Teorema

Siano n,mโˆˆZ con mโ‰ 0.โŸนโˆƒ!q,rโˆˆZ:

{n=qย m+r0โ‰คr<|m|

Inoltre q,mโˆˆNย seย n,mโˆˆN

Dimostrazione

Esistenza

Ipotizziamo che n,mโˆˆN e procediamo per induzione di seconda forma su n.

n=0 (BASE DELL'INDUZIONE)
รˆ sufficiente porre q,r=0

nโ‰ฅ1,โˆ€k<nโŸนn (PASSO INDUTTIVO)

Supponiamo n>0 e che la tesi sia vera per ogni k<n.

{k=mq+r0โ‰คr<m

Ma allora n=k+m=mq+r+m=(q+1)m+r.

โˆ’n=qm+r,ย 0โ‰คr<|m|โ‡”n=(โˆ’q)mโˆ’r

Se r=0 abbiamo finito, altrimenti continuiamo per ottenere un resto > 0.
Aggiungendo e togliendo m:

n=(โˆ’q)mโˆ’rโˆ’m+m=(โˆ’qโˆ’1)m+(mโˆ’r)

dove mโˆ’r รจ strettamente positivo per definizione.

โŸนโˆƒq,rโˆˆZ:n=(โˆ’mq+r),ย 0โ‰คr<|m|โ‡”n=(โˆ’q)m+r

Unicitร 

Sia

{n=qย m+r0โ‰คr<|m|ย ย ย eย ย ย {n=qโ€ฒย m+rโ€ฒ0โ‰คrโ€ฒ<|m|

Proviamo che q=qโ€ฒ,ย r=rโ€ฒ.
Allora vale:
n=qm+r=qโ€ฒm+rโ€ฒโ‡”qmโˆ’qโ€ฒm=rโ€ฒโˆ’rโ‡”(qโˆ’qโ€ฒ)m=rโ€ฒโˆ’rโ‡”|qโˆ’qโ€ฒ||m|=|rโˆ’rโ€ฒ|

โŸน|qโˆ’qโ€ฒ||m|=|rโˆ’rโ€ฒ|<|m|
โŸน|qโˆ’qโ€ฒ|<1

Concludiamo che qโ€ฒโˆ’q=0โŸนqโ€ฒ=q.
Dall'equazione originale ricaviamo che: mq+r=mqโ€ฒ+rโ€ฒโŸนrโ€ฒ=r.