Problema sul massimo comun divisore

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
minima.distanza
Messaggi: 131
Iscritto il: 11 giu 2010, 17:56
Località: Milano, in provincia...

Problema sul massimo comun divisore

Messaggio da minima.distanza » 28 giu 2010, 22:15

Innanzitutto buonasera a tutti...

Stavo guardando alcuni video del training olimpico di Massimo Gobbino quando, sentendomi finalmente pronto, mi son deciso ad iniziare a guardare i video delle lezioni di uno stage basic senior (2007).

Stavo guardando il video di Federico Poloni sulle congruenze, quando mi sono accorto che stavo perdendo i pezzi. L'autore, infatti, mettendosi a cercare tutti i possibili massimi comuni divisori tra $ x-y $ e $ x^2 +xy +y^2 $, da un certo punto in poi mi manda in confusione :oops: .

Fino a quando riconduce il problema a trovare $ (x-y,3xy) $ capisco tutto ( o almeno mi sembra, applica semplicemente una "proprietà" del massimo comune divisore....), ma poi ? Da dove tira fuori quei casi ? Qualcuno mi spiegherebbe il problema perfavore, mostrandomi magari "al rallentatore" come si "risolvono" tali tipi di problemi, che non lo capisco molto bene da come lo spiega lui... :oops:

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Re: Problema sul massimo comun divisore

Messaggio da Tibor Gallai » 28 giu 2010, 23:41

minima.distanza ha scritto:Stavo guardando il video di Federico Poloni sulle congruenze, quando mi sono accorto che stavo perdendo i pezzi.
E' un modo gentile per dire che ti sono cascate le palle?
No no, ok.

Comunque, al solito, un link al video come minimo non guasterebbe.
Nessuno ha voglia di andare a scartabellare tra i vari video, e cercare il punto giusto nel video.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

fph
Site Admin
Messaggi: 3804
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 29 giu 2010, 00:36

Uhm, tranquillo, molto probabile che sia l'autore ad aver fatto casino. :oops:
Mi sembra di ricordare che avevo scelto quell'esercizio qualche minuto prima della lezione per illustrare un paio di tecniche (il passaggio x^2+xy+x^2 -> 3xy, e come poi scartare i fattori di quelli che tra poche righe chiamerò a e b), ma poi mi sono reso conto "in diretta" che non veniva immediatamente utilizzando solo quelle. Per far tornare tutto ammodino avrei probabilmente dovuto aggiungere l'ipotesi mcd(x,y)=1. Così l'esercizio si fa, ma è più complicato di quanto avevo pianificato. In ogni caso spero di avere spiegato decentemente le due tecniche, che erano la cosa importante...

Provo a svolgerlo per bene ora --- sperando di non rifare casino...
-nota che se d=mcd(x,y), allora d divide il tuo mcd. Possiamo quindi "semplificare una d" ponendo x=da, y=db, con stavolta mcd(a,b)=1. Il problema diventa quindi trovare d*mcd(a-b,3dab) (occhio alla d che rimane).
-ci serve quindi trovare i fattori "non banali" che può avere g:=mcd(a-b,3dab). Dove vanno cercati? O tra i divisori di a, o tra quelli di b, o tra quelli di 3d.
-se p|a e p|g, allora dev'essere anche p|b (perché?), e questo va contro l'ipotesi che a e b fossero primi tra loro
-restano i primi che dividono 3d. C'è ancora qualcosa che possiamo scartare, o può in generale succedere che tutti i divisori di 3d siano anche fattori di g? Risposta: in generale puoi beccarli tutti -- è possibile trovare esempi in cui quel divisore è un qualunque fattore di 3d (come? possiamo scegliere indipendentemente d, a e b, con l'unico vincolo che a e b siano primi tra loro. Quindi, fissati d e g, basta scegliere b=un primo enorme, e a in modo che b-a=g)
-quindi in generale quell'mcd può essere un qualunque numero w tale che $ d \mid w \mid 3d^2 $.

Ditemi se ora torna...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 giu 2010, 00:53

[EDIT: oops, tardi! :( ]

Ok, con immane sforzo ho trovato video e problema incriminato.

Mi sa che la confusione nasce perché ad un certo punto si incarta e cambia le ipotesi. Credo che ripulendolo e riordinandolo, si possa riassumere così:

risolvere $ $x^3-y^3 = 2^{27}\cdot 3^{15} $, dove $ $x $ e $ $y $ sono interi coprimi.

Quindi $ $(x-y)\left(x^2+xy+y^2\right)=2^{27}\cdot 3^{15} $. I $ $2 $ e i $ $3 $ si possono distribuire a piacimento tra i due fattori a sinistra? A priori no, perché sono legati da $ $x $ e $ $y $. Calcoliamo il MCD dei due fattori.

$ $\left(x-y,\ x^2+xy+y^2\right) = (x-y,\ 3xy)\ |\ (x-y,\ 3)\cdot (x-y,\ x)\cdot (x-y,\ y) = (x-y,\ 3)\ |\ 3 $.

Nel passaggio centrale ho usato il fatto generale che $ $(a,bc)\ |\ (a,b)\cdot (a,c) $, che puoi facilmente dimostrare.

Quindi il MCD dei due fattori deve dividere $ $3 $, ovvero può essere solo $ $1 $ o $ $3 $. Vale a dire che uno dei due fattori non avrà alcun $ $2 $, ed uno dei due fattori avrà al più un $ $3 $.

Per concludere il problema basta allora esaminare tutti i casi, che sono solo 8 (i fattori negativi non vanno considerati perché $ $x-y>0 $).
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

minima.distanza
Messaggi: 131
Iscritto il: 11 giu 2010, 17:56
Località: Milano, in provincia...

Messaggio da minima.distanza » 29 giu 2010, 12:45

Perfetto ! Mi sembra di aver capito...

@fph: Bel video !
se p|a e p|g, allora dev'essere anche p|b
Questo succede per lo stesso motivo per cui si possoo "abbassare" i numeri in $ 2x^2 +3y^2 = 1998 $ o mi cnfondo ? è la stessa cosa applicata ai massimi comuni divisori...

@tibor gallai:
Scusa, me ne ero dimenticato del link...
Capisco tutto ( o almeno, credo di capire ) fino all'ultimo passaggio... da dove tiro fuori tutti gli otto casi ? cioè... col tuo metodo io tiro fuori delle condizioni entro cui devono stare quei fattori, ma come faccio poi ? Non capisco... ( io, se non l'avessi visto risolvere in questo modo, avrei impstato il sistema notando che $ x-y = 2*3^{n} $( con n che varia tra 0 e 15) e $ x^2 +xy +y^2 = 3^{15-n} $... Mi rendo conto che ciò è contosissimo, ma avrei fatto male ? sembra di sì... Tibor parla di 8 casi, io me ne devo fare 15 :oops: qualcuno mi spiega eprchè non va bene ?)

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 giu 2010, 13:49

Tibor Gallai ha scritto:il MCD dei due fattori deve dividere $ $3 $, ovvero può essere solo $ $1 $ o $ $3 $.
Tibor Gallai ha scritto:i fattori negativi non vanno considerati perché $ $x-y>0 $
$ $\begin{array}{ll} \left\{ \begin{array}{l} x-y=1\\ x^2+xy+y^2=2^{27}\cdot 3^{15} \end{array} \right. & \left\{ \begin{array}{l} x-y=3\\ x^2+xy+y^2=2^{27}\cdot 3^{14} \end{array} \right. \\ \noalign{\bigskip} \left\{ \begin{array}{l} x-y=2^{27}\\ x^2+xy+y^2=3^{15} \end{array} \right. & \left\{ \begin{array}{l} x-y=2^{27}\cdot 3\\ x^2+xy+y^2=3^{14} \end{array} \right. \end{array} $

$ $\begin{array}{ll}\left\{ \begin{array}{l} x-y=3^{14}\\ x^2+xy+y^2=2^{27}\cdot 3 \end{array} \right. & \ \ \,\left\{ \begin{array}{l} x-y=3^{15}\\ x^2+xy+y^2=2^{27} \end{array} \right. \\ \noalign{\bigskip} \left\{ \begin{array}{l} x-y=2^{27}\cdot 3^{14}\\ x^2+xy+y^2=3 \end{array} \right. & \ \ \,\left\{ \begin{array}{l} x-y=2^{27}\cdot 3^{15}\\ x^2+xy+y^2=1 \end{array} \right. \end{array} $
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

minima.distanza
Messaggi: 131
Iscritto il: 11 giu 2010, 17:56
Località: Milano, in provincia...

Messaggio da minima.distanza » 29 giu 2010, 18:26

ah :oops: non me ne ero accorto....
è fantastico insomma ! il procedimento di prima serve solo per escludere a priori dei casi quindi...

è fantastico ! :shock:

Bellissimo, grazie mille, posso andare avanti a guardare il video di fph ora...

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 29 giu 2010, 23:01

minima.distanza ha scritto:Bellissimo, grazie mille, posso andare avanti a guardare il video di fph ora...
Sì, però prima ripulisci la tastiera da tutta quella bava...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

fph
Site Admin
Messaggi: 3804
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 giu 2010, 00:07

minima.distanza ha scritto:@fph: Bel video !
Nah, mica tanto, come hai fatto notare tu mi incasino e non ci si capisce una mazza. Non ti sentire in dovere di complimentarti. :D
se p|a e p|g, allora dev'essere anche p|b
Questo succede per lo stesso motivo per cui si possoo "abbassare" i numeri in $ 2x^2 +3y^2 = 1998 $ o mi cnfondo ? è la stessa cosa applicata ai massimi comuni divisori...
Sì, la ragione è la stessa. Hai g|a-b, quindi p|a-b per transitività. Poiché hai anche p|a, sottraendo i due membri di destra trovi p|b.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

minima.distanza
Messaggi: 131
Iscritto il: 11 giu 2010, 17:56
Località: Milano, in provincia...

Messaggio da minima.distanza » 30 giu 2010, 00:25

I: Non ti ho fatto notare io che ti incasini ( anche se in parte è vero)
II: il fatto che ti incasini e che un è uno stimolo per non soribre passivamente il video come una macchinetta...

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 30 giu 2010, 04:39

Sì, vogliamo poi aggiungere che la scelta del $ $2^{27}\cdot 3^{15} $ è particolarmente infelice, perché si tratta di un cubo? (vedi Ultimo Teorema di Fermat...) :roll:

Ma se si tralasciano tutte le cose tipo $ $n=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} $, la lezione sembra molto ben fatta! :D
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

EvaristeG
Site Admin
Messaggi: 4790
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 30 giu 2010, 10:12

Basta notare la differenza tra $ n $ e $ \phantom{}_n $, che mi sembra evidente ...

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 30 giu 2010, 10:15

Ah, quindi basta porre $ $n \neq \phantom{}_n = \phantom{}^{\phantom{}_n} $. Tutto chiaro.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 30 giu 2010, 22:30

Tibor Gallai ha scritto:
$ (x-y,\ 3xy)\ |\ (x-y,\ 3)\cdot (x-y,\ x)\cdot (x-y,\ y) = (x-y,\ 3)\ |\ 3 $.

.
perchè è uguale al MCD tra (x-y,3) e perchè divide 3? :oops:

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 30 giu 2010, 23:34

Per ipotesi sai che (x,y)=1, quindi puoi dire che (x-y,y)=(x,y)=1, (x-y,x)=(-y,x)=1 e da questo segue che (x-y,3)(x-y,y)(x-y,x)=(x-y,3). Ma se d è il massimo comun divisore tra x-y e 3, per definizione d|x-y e d|3

Rispondi