[N base] MCD

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

Ciao. Una raccolta per i novizi di proprietà dell\'MCD che tornano utili spesso.
 
 d = MCD(a,b) è il massimo comun divisore tra gli interi a e b (supposti diversi da 0), vale a dire quel numero che gode di:
 
 I. d | a; d | b [\"|\" significa \"è sottomultiplo\"] ossia è un divisore comune;
 II. se d\' | a e d\' | b, allora d\' | d, ossia di tutti i divisori comuni, è il massimo;
 III. d è positivo [a rigore, se I e II sono verificate da d, lo sono anche da -d; per convenzione si sceglie come unico valore quello positivo].
 
 A volte si scrive pure (a,b) per intendere MCD(a,b).
 
 Dimostrare che:
 
 i) (a,b) divide a+b, a-b e, in generale, ha + kb (h, k interi)
 ii) (a,b) = (a+b,a) = (a-b,a)
 iii) (a,b,c) = ((a,b),c)
 iv) Se r è il resto della divisione di a per b, allora (a,b) = (b,r)
 
 v) Il seguente algoritmo [detto di Euclide o delle divisioni successive] permette di calcolare il MCD di a e b:
 
 1. Inizio con a0 = a; b0 = b; i = 0.
 
 2. Eseguo la divisione di ai : bi. q è il quoziente e r il resto.
 
 3. Se r = 0, allora MCD(a,b) = bi e l\'algoritmo finisce.
 
 4. Se invece r > 0, pongo ai+1 = bi; bi+1 = r; incremento i di 1 e ricomincio dal passo 2.
 
 Dimostrare che l\'algoritmo (*) finisce in tempo finito e (**) fornisce il risultato corretto.
 
 vi) [Identità di Bézout]
 Esistono interi r e s tali che ra + sb = (a,b).
 
 vii) Di tutti i numeri che possono essere scritti nella forma ra + sb, r e s interi, il più piccolo tra di essi che sia positivo è proprio (a,b).
 
 Altro?...
 
 Ciao. M.
 
 \"We shall see. So many strange things have chanced that to learn the prais of a fair lady under the loving strokes of a Dwarf\'s axe will seem no great wonder.\" [ Questo Messaggio è stato Modificato da: marco il 02-12-2004 17:02 ]

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Sarebbe interessante mettere qualche proprietà che lega MCD e mcm. Forse in un altro thread?

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 i) (a,b) divide a+b, a-b e, in generale, ha + kb (h, k interi)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 MCD(a,b)|a
 MCD(a,b)|b
 quindi, per la definizione stessa di divisibilità
 a=j1*MCD
 b=j2*MCD
 ha+kb=h(j1*MCD)+k(j2*MCD)
 ha+kb=MCD*(hj1+kj2)
 da cui MCD|ha+kb [ Questo Messaggio è stato Modificato da: Boll il 02-12-2004 18:44 ]

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 ii) (a,b) = (a+b,a) = (a-b,a)
 iii) (a,b,c) = ((a,b),c)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 ii) Supponiamo per assurdo che non sia così, allora poichè MCD(a,b)|a+b, bisognerebbe che esistesse un fattore k che è uno zero modulo a, modulo a+b, ma non modulo b. Assurdo
 
 iii) MCD(a,b,c)=d, allora a=d*k1, b=d*k2, c=d*k3 ed MCD(k1,k2,k3)=1 poichè se non fossero coprimi l\'MCD sarebbe maggiore. Avremo quindi che MCD(a,b)=d*j dove j è sicuramente un fattore sia di k1 che di k2, ma un divisore di k1 e k2 non può essere divisore di k3 per osservazione precedente. Quindi MCD((a,b),c)=d [ Questo Messaggio è stato Modificato da: Boll il 02-12-2004 19:01 ]

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 iv) Se r è il resto della divisione di a per b, allora (a,b) = (b,r)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Avremo che b=qa+r
 (a,b)|qa+r
 (a,b)|a
 (a,b)|qa+r-q(a)
 (a,b)|r
 abbiamo che l\'MCD è un sottomultiplo di r, ora dobbiamo dimostrare che è il massimo comune ad a. Supponiamo per assurdo che così non sia, cioè che esista un d che divide r e a, ma non b. Allora, nell\'equazione
 qa+r=b
 avremo che, modulo d, 0+0=/=0, da cui l\'assurdo.

karl · Messaggio da **karl** » 01 gen 1970, 01:33

Questo sembra interessante:
 Teorema di Lame\'
 Il numero delle divisioni occorrenti per la determinazione
 del M.C.D. di due numeri (mediante l\'algoritmo di Euclide)
 e\' non maggiore del quintuplo del numero delle cifre del
 maggiore dei due numeri dati.

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 vi) [Identità di Bézout]
 Esistono interi r e s tali che ra + sb = (a,b).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Lemma 1: Se (a,b)=1 esistono interi r e s per cui ra+sb=1
 Dimostrazione: Prendiamo a>b per simmetria (il fatto che siano coprimi impone che non valga l\'uguaglianza), ora b avrà una data congruenza ,modulo a, poniamo s=bphi(a)-1, per il teorema di Euler-Fermat avremo ora che sb==1 modulo a, quindi uguale a ka+1 per qualchè k appartenente a N, ci basterà ora porre r=-k per verificare la tesi.
 
 Ora facciamo il caso generale, a=(a,b)j, b=(a,b)k, con (j,k)=1 poichè se così non fosse (a,b) non sarebbe l\'MCD di a e b.
 allora
 rj(a,b)+sk(a,b)=(a,b)
 (a,b)(rj+sk)=(a,b)
 per il Lemma 1 esistono interi s e r per cui rj+sk=1, per cui la tesi è dimostrata.

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 vii) Di tutti i numeri che possono essere scritti nella forma ra + sb, r e s interi, il più piccolo tra di essi che sia positivo è proprio (a,b).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 ra+sb=x
 posto a=(a,b)h, b=(a,b)h
 (a,b)(rh+sk)=x
 perchè x sia positivo, poichè (a,b) è positivo per ipotesi, rh+sk dev\'essere positivo, minimizzandolo lo mandiamo a 1 e avremo:
 x=(a,b) per il teorema di Bezuot sappiamo che esiste e ora abbiamo (spero <IMG SRC="images/forum/icons/icon_razz.gif">) dimostrato che è anche minimo.

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 18:29, MindFlyer wrote:
 Sarebbe interessante mettere qualche proprietà che lega MCD e mcm. Forse in un altro thread?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ecco, si potrebbe iniziare dalle identità di Lebesgue, e passare quindi alle formule di Mignosi, per esssempio! Boh, se a qualcuno resta del tempo per dimostrarle, non è che siano da buttar via, in fondo in fondo...
 
 
 \"Mille mila trilioni di bilioni di conti...\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon_eek.gif">

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 19:30, Boll wrote:
 [Sul punto (vi)]
 [...]poniamo s=bphi(a)-1, per il teorema di Euler-Fermat avremo ora che sb==1 modulo a...</BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 E\' tutto giusto e vero. Solo che stiamo sparando con un cannone ad una zanzara. Non so bene quale linea dimostrativa hai in mente per il teorema di Euler q.m., ma di solito, si usa l\'esistenza degli inversi mod a prima di Fermat/Euler, e quindi preferirei qualcosa più terra-terra.
 
 Ce la facciamo a dimostrare lo stesso lemma con tecniche più basilari?
 
 Sulle altre dimostrazioni, tutto ok. Solo una noticina sulla (iv): bastava dire che è un caso particolare della (ii), applicata q volte. [la famosa barzelletta del matematico che si riconduce al caso precedente, avete presente?... <IMG SRC="images/forum/icons/icon_wink.gif"> ]
 
 Il punto (v) non lo dimostra nessuno?
 
 ------
 
 Beh, intanto...
 
 viii) Se a = prodi piAi e b= prodi piBi sono le consuete scomposizioni in fattori primi (alcuni esponenti potrebbero essere zero), allora
 
 (a,b) = prodi pimin(Ai,Bi).
 
 [è l\'algoritmo della scuola media: prodotto dei fattori primi comuni con il minimo esponente]
 
 Ciao. M.
 
 [ Questo Messaggio è stato Modificato da: marco il 03-12-2004 16:17 ] [ Questo Messaggio è stato Modificato da: marco il 03-12-2004 16:23 ]

Melkon · Messaggio da **Melkon** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-03 16:10, marco wrote:
 la famosa barzelletta del matematico che si riconduce al caso precedente, avete presente?... <IMG SRC="images/forum/icons/icon_wink.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 no, in realtà no... ce la racconti anche se è un po\' OT?...

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 viii) Se a = prodi piAi e b= prodi piBi sono le consuete scomposizioni in fattori primi (alcuni esponenti potrebbero essere zero), allora
 
 (a,b) = prodi pimin(Ai,Bi).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Mah, mi smbra talmente un ovvietà che fatico a dimostrarlo, ci provo o stesso.
 
 Se un fattore non è comune, per definizione di massimo comun divisore, non può essere oncsiderato. Se è comune, bisogna considerare la potenza minima a cui è comune poicè è la massima che divide entrambi. Ora per aver il massimo comun divisore dovremo fare il prodotto fra i mssimi divisori primi.
 
 Rimanendo in tema di algoritmi che si fanno da bambini propongo:
 Dimostrare che la prova del 9 è falsa (per chi se la ricorda <IMG SRC="images/forum/icons/icon_biggrin.gif">)

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-03 16:10, marco wrote:
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 19:30, Boll wrote:
 [Sul punto (vi)]
 [...]poniamo s=bphi(a)-1, per il teorema di Euler-Fermat avremo ora che sb==1 modulo a...</BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 E\' tutto giusto e vero. Solo che stiamo sparando con un cannone ad una zanzara. Non so bene quale linea dimostrativa hai in mente per il teorema di Euler q.m., ma di solito, si usa l\'esistenza degli inversi mod a prima di Fermat/Euler, e quindi preferirei qualcosa più terra-terra.
 
 Ce la facciamo a dimostrare lo stesso lemma con tecniche più basilari?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ok ci proviamo...
 Consideriamo tutti i numeri del tipo ax+by con x,y€Z e prendiamo l\'intero positivo minimo tra questi e chiamiamolo d. Diciamo che ax0+by0=d e facciamo la divisione euclidea di a per d:
 a=kd+r
 a=kax0+kby0+r
 r=a(1-kx0)-by0
 Quindi r è della forma ax+by e d>r>=0. Per la minimalità di d abbiamo che r=0 cioè d|a. Simmetricamente d|b. Ora per ogni intero c tale che c|a e c|b allora c|ax+by e in particolare c|ax0+by0 cioè c|d. Quindi d=MCD(a,b) proprio per definizione*.
 
 *La definizione di MCD(a,b) è: MCD(a,b)=d
 (d|a) e (d|b) e (per ogni c t.c. ((c|a) e (c|b)) allora c|d)
 
 P.S.: Se non mi sbaglio la dimostrazione è molto simile a una data da Dvornicich in uno dei suoi libri (quello che danno a Napoli) [ Questo Messaggio è stato Modificato da: Simo_the_wolf il 04-12-2004 18:09 ]

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-04 18:07, Simo_the_wolf wrote:
 *La definizione di MCD(a,b) è: MCD(a,b)=d
 (d|a) e (d|b) e (per ogni c t.c. ((c|a) e (c|b)) allora c|d)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Got it. La definizione era nel primo post del filo. La tua va bene a meno del segno.
 
 Io conosco una dimostrazione alternativa. Peccato che richieda l\'Algoritmo di Euclide, che nessuno si è ancora sognato di dimostrare (p.to (v) della mia lista...)
 
 Ve la racconto con un esempio numerico, perché non ho il tempo di formalizzarla bene:
 
 (96,75) = 3, quindi cerco r e s t.c. 96 s + 75 r = 3
 
 Organizzo l\'algortitmo con tre colonne:
 
 A..............r.............s
 
 96............1.............0
 75............0.............1
 21............1............-1 [riga 1 - riga 2]
 12...........-3.............4 [riga 2 - 3 x riga 3]
 9..............4............-5 [riga 3 - riga 4]
 3.............-7.............9 [riga 4 - riga 5]
 
 E quindi 3 = -7 x 99 + 9 x 75.
 
 [Gasp! Ho fatto i conti giusti al primo colpo....]
 
 Ecco. Formalizzate questa cosa, sfruttate che l\'algortimo di Euclide finisce ed è corretto [passo (v), ancora da risolvere] e che, per ogni riga, succede che A = 96 r + 75 s. Funziona, finisce e dà il risultato corretto.
 
 Alla prossima.
 
 M.[addsig]

what · Messaggio da **what** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 17:01, marco wrote:
 v)Dimostrare che l\'algoritmo (*) finisce in tempo finito e (**) fornisce il risultato corretto.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Come già dimostrato da boll, se b=q1*a+r1 allora (a,b)=(a,r1).
 Reiterando il procedimento, avremo a=q2*r1+r2 , e quindi
 (a,b)=(a,r1)=(r1,r2).
 Continuando così, poichè la successione dei resti è decrescente in N,
 (*)l\'algoritmo ha termine, ed esiterà quindi un ri tale che ri+1=0, (**)e che sarà evidentemente il valore cercato.