Esistenza e unicitร  del Massimo Comune Divisore

Teorema

Siano n,mโˆˆN con n,m non entrambi nulli. Diremo che dโˆˆN,ย dโ‰ฅ1 รจ Massimo Comune Divisore (M.C.D) diย n,m se:

  1. d|mย โˆงย d|n
  2. c|mย โˆงย c|nย โŸนc|d per qualche cโˆˆN

Inoltre, โˆƒx,yโˆˆZ:d=xn+ym, ovvero d รจ esprimibile come combinazione lineare di n,m con x,y.
Se โˆƒMCD tra n,m, รจ unico e lo indicheremo con (n,m).

Dimostrazione

Unicitร 

Poniamo esistano d1,d2 entrambi MCD di n,m. Applicando la proprietร  (1) di d1 e la (2) di d2 otteniamo:

Applicando l'inverso otteniamo che d2|d1โˆงd1|d2โŸนd1=ยฑd2.
Essendo d1,d2โˆˆN, otteniamo che d1=d2.

Esistenza

Sia S:={sโˆˆZย |ย s>0,ย xn+ymย per qualcheย x,yโˆˆZ}.
Osserviamo che Sโ‰ โˆ…, in quanto se x=n e y=m otteniamo s=nn+mm>0โŸนnn+mmโˆˆS.
Grazie al teorema di buon ordinamento dei numeri naturali, S ammette un minimo d, cioรจ d:=minย S. Proviamo che d soddisfa le proprietร  1 e 2.

Verifichiamo che vale 2.
Se cย |ย n e cย |ย m allora n=ck e m=ch, quindi d=nx+mx=ckx+chy=c(kx+hy), ossia cย |ย d.(LEMMA UTILE)

Verifichiamo che d soddisfa la proprietร  1, ovvero dย |ย n e dย |ย m. Dimostriamo che dย |ย n.
Eseguiamo la divisione di n per d, ottenendo il quoziente q e il resto r.

{n=qd+r0โ‰คr<d

Rimane da provare che r=0. Supponiamo che r>0. Osserviamo che:

0<r=nโˆ’qd=nโˆ’q(xn+ym)=nโˆ’qxnโˆ’qym=n(1โˆ’qx)+(โˆ’qy)mโŸนrโˆˆS,ย r<d=minย (S)IMPOSSIBILEโŸนr=0ย ovveroย dย |ย n

Analogalmente si dimostra che dย |ย m.