Dimostrazione proprietà del MCD
Non sono sicuro di averla fatta correttamente, mi sembra di aver dimenticato qualcosa 
Qualcuno può dirmi se è accettabile?
Voglio dimostrare che $ MCD(na;nb) = nMCD(a;b) $
Sia $ D = MCD(a;b) rArr (D |a ^^ D |b ) ^^ (AAx//x | b ^^ x | a rArr x | D ) $ per la definizione di MCD.
Siccome $ D|a ^^ D|b rArr nD|na ^^ nD|nb $ ,
e siccome $ (AAx // x|a ^^ x|b rArr x|D ) rArr (AAx // nx|na ^^ nx|nb rArr nx|nD ) $ con $ n geq 1 $.
Quindi $ nD $ soddisfa le condizioni per essere il $ MCD(na;nb) $ .
Ciò che mi chiedo è: è sufficiente quel $ n geq 1 $ per dimostrare che $ nD $ è il maggiore sia tra i divisori comuni ai quattro numeri, sia tra quelli comuni solo a na e nb?
Grazie in anticipo per la pazienza
Qualcuno può dirmi se è accettabile?
Voglio dimostrare che $ MCD(na;nb) = nMCD(a;b) $
Sia $ D = MCD(a;b) rArr (D |a ^^ D |b ) ^^ (AAx//x | b ^^ x | a rArr x | D ) $ per la definizione di MCD.
Siccome $ D|a ^^ D|b rArr nD|na ^^ nD|nb $ ,
e siccome $ (AAx // x|a ^^ x|b rArr x|D ) rArr (AAx // nx|na ^^ nx|nb rArr nx|nD ) $ con $ n geq 1 $.
Quindi $ nD $ soddisfa le condizioni per essere il $ MCD(na;nb) $ .
Ciò che mi chiedo è: è sufficiente quel $ n geq 1 $ per dimostrare che $ nD $ è il maggiore sia tra i divisori comuni ai quattro numeri, sia tra quelli comuni solo a na e nb?
Grazie in anticipo per la pazienza
Risposte
1. Perché usi il simbolo di congiunzione (\wedge) dopo il quantificatore universale?
2. Supponendo che siamo in \(\mathbb{Z}\), perché passi da \(x\) a \(nx\)?
2. Supponendo che siamo in \(\mathbb{Z}\), perché passi da \(x\) a \(nx\)?
"WiZaRd":
1. Perché usi il simbolo di congiunzione (\wedge) dopo il quantificatore universale?
2. Supponendo che siamo in \(\mathbb{Z}\), perché passi da \(x\) a \(nx\)?
1. il quantificatore universale sarebbe "per ogni", no? Se intendi il simbolo in rosso non è roba mia, non ho capito come sia uscito
io volevo scrivere solo "tale che" (e in ogni caso, se intendi quello in rosso, non sarebbe il simbolo di disgiunzione? Il fatto che tu abbia detto congiunzione mi fa pensare che io non abbia capito a quale simbolo tu ti riferisca, per favore spiegami)2. Lì sta proprio la domanda, se posso passare da x a nx. Altrimenti non so come dimostrare che ogni divisore comune tra na e nb sia divisore anche di nD, e quindi l'escamotage di nx mi era sembrato buono, ma non so se è valido.
Per quanto riguarda la questione del connettivo logico, errore mio: chiedo scusa, confusione inopportuna. È il simbolo di disgiunzione quello in rosso ed è a quello che facevo riferimento.
Per quanto riguarda la dimostrazione, va bene anche se mi lascia una sensazione di "vuoto" che al momento non so spiegare. Mi pare imprecisa.
Per quanto riguarda la dimostrazione, va bene anche se mi lascia una sensazione di "vuoto" che al momento non so spiegare. Mi pare imprecisa.
"WiZaRd":
Per quanto riguarda la questione del connettivo logico, errore mio: chiedo scusa, confusione inopportuna. È il simbolo di disgiunzione quello in rosso ed è a quello che facevo riferimento.
Per quanto riguarda la dimostrazione, va bene anche se mi lascia una sensazione di "vuoto" che al momento non so spiegare. Mi pare imprecisa.
Sì, anche a me. Mi pare che ci sia qualcosa che non vada, ma non capisco cosa. Grazie comunque per averla letta, almeno hai confermato il mio dubbio.
Cerco di spiegare il "senso di vuoto".
Tu vuoi provare che se si prende un intero \(x\), di modo che il fatto che \(x \mid a\) e \(x \mid b\) implichi che \(x \mid d\), ove \(d = \gcd (a,b)\), allora questo \(x\) è tale per cui da \(nx \mid na\) ed \(nx \mid nb\) discende che \(nx \mid nd\), vuoi cioè provare che \( \left(x \mid a \land x \mid b \Rightarrow x \mid d\right) \Rightarrow \left(nx \mid na \land nx \mid nb \Rightarrow nx \mid nd\right)\).
Questo è anzitutto banale* ma è anche insufficiente: mettiamo che \(n=6, a=35, b=63\) e cerchiamo il \(\gcd(210, 398)\). Nella ricerca del mio \(\gcd\) dovrò assicurarmi che qualunque intero divida \(210\) e \(398\) divida anche quello che io ritengo essere il \(gcd\). Se, per esempio, prendo \(2\) dovrò assicurarmi che, essendo \(2\) divisore sia di \(210\) che di \(398\), esso risulti anche divisore di \(42\), cioè del mio \(gcd\). Domanda: fissato \(n=6\), come faccio io a tirare fuori, in \(\mathbb{Z}\), \(nx=2\)? Non posso. Questo significa che quello che vuoi provare non contempla il controllo delle divisibilità per tutti i divisori dei numeri tra i quali cerchi il \(gdc\).
Io allora procederei così. Sia \(x \in \mathbb{Z} : x \mid na \land x \mid nb\): allora \(na=\alpha x \land nb=\beta x\). Poiché \(d=gcd(a,b)\), allora \(a=cd \land b=c'd\), quindi \(\alpha x=na=ncd=c(nd) \Rightarrow x \mid nd\) e \(\beta x=nb=nc'd=c'(nd) \Rightarrow x \mid nd\).
_____________________________________________________________________
(*) Infatti \(nx \mid nd \Leftrightarrow x \mid d\), poiché certamente \(n \mid n\), e senz'altro \(x \mid d\), perché, proprio in virtù del fatto che \(n \mid n\), da \(nx \mid na\) (risp. \(nx \mid nb\)) deriva che \(x \mid a\) (risp. \(x \mid b\)) e, stante il fatto che \(x \mid a \land x \mid b \Rightarrow x \mid d\), risulta proprio \(x \mid d\)
Tu vuoi provare che se si prende un intero \(x\), di modo che il fatto che \(x \mid a\) e \(x \mid b\) implichi che \(x \mid d\), ove \(d = \gcd (a,b)\), allora questo \(x\) è tale per cui da \(nx \mid na\) ed \(nx \mid nb\) discende che \(nx \mid nd\), vuoi cioè provare che \( \left(x \mid a \land x \mid b \Rightarrow x \mid d\right) \Rightarrow \left(nx \mid na \land nx \mid nb \Rightarrow nx \mid nd\right)\).
Questo è anzitutto banale* ma è anche insufficiente: mettiamo che \(n=6, a=35, b=63\) e cerchiamo il \(\gcd(210, 398)\). Nella ricerca del mio \(\gcd\) dovrò assicurarmi che qualunque intero divida \(210\) e \(398\) divida anche quello che io ritengo essere il \(gcd\). Se, per esempio, prendo \(2\) dovrò assicurarmi che, essendo \(2\) divisore sia di \(210\) che di \(398\), esso risulti anche divisore di \(42\), cioè del mio \(gcd\). Domanda: fissato \(n=6\), come faccio io a tirare fuori, in \(\mathbb{Z}\), \(nx=2\)? Non posso. Questo significa che quello che vuoi provare non contempla il controllo delle divisibilità per tutti i divisori dei numeri tra i quali cerchi il \(gdc\).
Io allora procederei così. Sia \(x \in \mathbb{Z} : x \mid na \land x \mid nb\): allora \(na=\alpha x \land nb=\beta x\). Poiché \(d=gcd(a,b)\), allora \(a=cd \land b=c'd\), quindi \(\alpha x=na=ncd=c(nd) \Rightarrow x \mid nd\) e \(\beta x=nb=nc'd=c'(nd) \Rightarrow x \mid nd\).
_____________________________________________________________________
(*) Infatti \(nx \mid nd \Leftrightarrow x \mid d\), poiché certamente \(n \mid n\), e senz'altro \(x \mid d\), perché, proprio in virtù del fatto che \(n \mid n\), da \(nx \mid na\) (risp. \(nx \mid nb\)) deriva che \(x \mid a\) (risp. \(x \mid b\)) e, stante il fatto che \(x \mid a \land x \mid b \Rightarrow x \mid d\), risulta proprio \(x \mid d\)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo